1

LBA（線形有界オートマトン）を勉強しています。いくつかの演習を解決する方法を理解しようとしています。

そこで、状況依存文法を与えられた LBA を簡単に作成する方法があるのだろうかと思います。

これは、LR 文法から DFA (決定論的有限オートマトン) に移行する方法のようなものです。

前もって感謝します

4

1 に答える 1

0

文脈依存文法には縮約的な生成規則がないため、徹底的な検索を使用できます。

文字列から始めて、元に戻すプロダクションを非決定論的に選択できます。これにより、入力の長さを増やすことはできません。空の文字列に到達する (この場合は受け入れる) か、作成を元に戻せなくなる (この場合は拒否する) まで繰り返します。

これはスケッチですが、詳細を記入するのは簡単です。

于 2011-07-06T00:17:33.187 に答える