プッシュダウンオートマトン、2つの言語が可能です（または条件）
宿題では、2つの言語のプッシュダウンオートマトンを作成する必要がありましたが、私の意見では、これらはオートマトンが両方で同じである2つの演習です。
私が理解しているように、非決定性プッシュダウンオートマトンを構築でき、文字aを読み取るたびに、オートマトンの「裁量」で1つまたは2つのAを挿入できます。
次に、文字bの状態が作成され、Aを読み取るたびに、スタックから引き出します。このように、オートマトンは、aの量がbの量に等しい両方の言語と、aのようにbの量の2倍である言語の両方を処理する方法を知っています。
私は正しいですか？それとも私は何かが足りないのですか？
そうでない場合は、最初の演習で「または」状態に対処する方法を理解したいと思います。
ありがとうございました。
回答
以来 $L_2\ne L_3$、それらは明らかに同じプッシュダウンオートマトンでは受け入れられません。認識できるオートマトンを念頭に置いているようですね$L_3$。おそらく認識できるように設計する最も簡単な方法$L_2$、2つの決定性プッシュダウンオートマトンを設計することです。 $\{a^nb^n:n\in\Bbb N\}$ と1つ $\{a^{2n}b^n:n\in\Bbb N\}$。次に、それらを組み合わせて、トランジションを持つ単一のプッシュダウンオートマトンにします$\langle q_0,\varepsilon,Z,q_1,Z\rangle$ そして $\langle q_0,\varepsilon,Z,q_2,Z\rangle$、 どこ $q_0$ 結合されたPDAの初期状態です。 $Z$ は最初のスタックシンボルであり、 $q_1$ そして $q_2$2つの補助的なプッシュダウンオートマトンの初期状態です。言い換えれば、結合されたPDAが最初に行うことは、タイプの単語を探すかどうかを「選択」することです。$a^nb^n$ またはタイプの単語 $a^{2n}b^n$、そしてそれは決定論的にその選択を追求します。