問題タブ [context-free-language]

言語にアクセスするには、明確な文法を生成する必要がありますL= { a^i b^j c^k | i, j, k ≥ 0 , i = j or i = k }

私がすでに持っているものは次のとおりです。

しかし、この文法はあいまいです。同じ数の a、b、c を持つ文字列を 2 つの異なる方法で認識できます。明確にするためのより良い提案はありますか？

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

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

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

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

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

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

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

MSB を 1 として 5 で割り切れる 2 進数の文法を見つけ、L の反転を見つけるにはどうすればよいですか?

だから、私は..のような数字を生成する文法が必要です.

等々

私は言語 {4^(w⋅g)34^(g)|w,g∈NAT} をアルファベット {0,1} で持っています。

この言語が認識可能か、決定可能か、文脈自由か、規則的か、またはこれらのいずれでもないかを調べる必要があります。

どうすればそれを行うか、知ることができますか？

ありがとう

オートマトン理論に関するメモが 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までのヒントやチュートリアルは大歓迎です。

同じ数の a と b を持つ偶数回文で構成される言語の CFG を構築し、それがその言語を生成することを証明する必要があります。

これは私が得たCFGです：

S→ アバ | バアブ | 腹筋 | バサブ | ε

それを証明するために何をすべきかわからない（論理的にこれを思いついた）...誰かが私を正しい方向に向けることができれば、私はそれを感謝します。ありがとうございました！

以下の機能と同等のCFGを作ろうとしています。B がループ カウンターであることはわかっているので、一連の要素がスタックにプッシュされる可能性があります。ループが完了するたびに、B からの要素がポップされ、B = Epsilon の場合は終了します。while ループの上半分で追加を処理するにはどうすればよいですか?