PDA (プッシュ ダウン オートマトン) の正式な記述についてかなり混乱しています。
L(M) と書くと、これは PDA M が言語 L を認識することを意味しますね。
次に、L(M)* は、PDA M がその L* を認識することを意味しますね。
しかし、L* は何を意味するのでしょうか? PDA は L の無限の組み合わせをどのように認識できますか?
質問する
281 次
1 に答える
2
L(M)* というのは、PDA M が L* を認識するということですよね？
いいえ！これは、PDA M によって認識される言語で有効な任意の数 (0 を含む) の文の連結から構成される言語を意味します。
L(M) が文脈自由であることを考えると、L(M)* も文脈自由であることを証明するのは簡単です。
L(M)* を構成するには、L(M) のすべての文法を取得し、L(M) から開始記号 S を取得し、2 つの新しい生成を追加R -> S RしR -> emptyます。ここで、R は L(M)* の開始記号です。
したがって、L(M)* が文脈自由であることを考えると、それを認識する PDA がいくつかあります。L(M) の PDA を作成できた場合、L(M)* の PDA は簡単に作成できるはずです。
于 2013-02-09T03:49:44.910 に答える