automata - プッシュダウン オートマトンの定義

Question

PDA (プッシュ ダウン オートマトン) の正式な記述についてかなり混乱しています。

L(M) と書くと、これは PDA M が言語 L を認識することを意味しますね。

次に、L(M)* は、PDA M がその L* を認識することを意味しますね。

しかし、L* は何を意味するのでしょうか? PDA は L の無限の組み合わせをどのように認識できますか?

Answer 1

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 は簡単に作成できるはずです。