問題タブ [pushdown-automaton]

I know the Y is left recursive but why is the Z not left recursive?

For Y i got

Then factoring

Where 'e' is empty

言語のプッシュダウン オートマトンの設計について質問があります。

つまり、 の の数は、bの2 倍と の 3 倍のw"間"です。aa

私はこの質問について混乱しています: 私は (願わくば!) の数がの数の 2 倍または の数の 3 倍にb等しい場合に言語を受け入れるように PDA を設計する方法を知っています (できれば!) 。aa

この言語はそれらの交差点のようですが、交差点を使用して PDA を作成する簡単な方法はないと思います。数値が 2 つの値の間にある可能性があるという事実をどのように組み込むことができるでしょうか。

どんな助けでも大歓迎です...

PS文脈自由文法（および説明）も提供していただけると、非常に役立ちます。

PPS: また、文脈自由文法を段階的に構築する方法を示すリンクを誰かが提供できる場合は、本当に必要です。（正規表現の通常の文法へのリンクを見つけましたが、文脈自由文法の場合、変数をたどろうとして、ある変数がそれ自体に行くか、別の変数に行き、それが最初の変数に戻るのを見ると、私は本当に混乱します。）

オートマトン理論に関するメモが 1 つあります。

次の言語を検討してください。

L={xy : x,y in {a,b}*}

次の制約を考慮してください。

1) x=y

2) x != y

3) x=(y)逆

4) x の数が y の数と等しくない

制約 2,3,4 は文脈自由である言語を読みました。1から3までのヒントやチュートリアルは大歓迎です。

プッシュ ダウン オートマトン スタックが他のすべての状態と共有されているかどうかを知りたいですか?

等しい数の 01 と 10 を含む集合 L が正則であることを示します。[ヒント: L = {'', 0,00..,1,11…,010,101,…}、2 つの分岐を考えます。1 つは 0 で始まり、もう 1 つは 1 で始まります。] L の CFG と PDA を書きます。