友人からプッシュダウン オートマトンについて質問されました。アバカ。私はいくつかの同様の問題を見ていますが、すべての問題には 0^a 1^a のような偶数が含まれていますが、現在は 3 つの値があります。その例を見つけましたが、質問をこれに変換できません。
aabbabcc:
read a push 1
read a push 1
read b pop 1
read b pop 1
stack is empty so push 0
read a push 1
read b pop 1
top of stack is 0 so push 0
read c pop 0
read c pop 0
どうすれば abacaa を変換できますか?
私はこれがしばらくここにあったことを知っていますが、誰かが同様の質問を探している場合に備えて...なぜこれを再ハッシュするのですか?
基本的な考え方は次のとおりです。プッシュダウン オートマトンにはスタックがあります。したがって、必要な数の a を読み込み、毎回追加の "a" をスタックにプッシュします。次に、b を読み取り、次の状態に進みます。
ここで、もう一度必要な数の a を読み取り、すべての a を再びスタックにプッシュします。次に、ac を読み取り、次の状態に進みます。
ここで、スタックの一番上にある 'a' を見ている限り、a's を読み取ります。スタックの一番下のシンボルを見ているときは、最終的な受け入れ状態に移行します。
それ以上の a がある場合、遷移はなく、文字列は受け入れられません (読み終わっておらず、どこにも行けないため、マシンを「クラッシュ」させます)。そうしないと、前の状態で a を使い果たした場合、最終状態に到達することはなく、文字列は受け入れられません。最初の 2 回と同じ数の a を読み取った場合にのみ、読み取る入力がなくなる受け入れ状態になり、文字列が受け入れられます。