私は試験のオートマトンと正式な言語について勉強しています。言語を認識する PDA を設計する必要があります。
a ^ib ^2i i>= 1
解決策は次のようになると思いました：
テープから読み取った "a" ごとに 2 つの X をスタックします。次に、テープに "b" があり、スタックの一番上に X がある場合、スタックから 1 つの X をポップします。テープ、および Zo (スタック マーカーの下部) があり、文字列は受け入れられます。私の質問は: 1 つの計算ステップで 2 つの連続する X を積み重ねることができますか?
1 つのステップで 2 つの X を押す必要はありません。1 つの X を押すだけで、テープから何も消費せずに別の X を押す状態に移行します。遷移関数は sigma UNION {epsilon} であるため、入力を消費せずにスタックをいじることができることに注意してください。
簡単な答え: スタックに対して N 個のことをしたいですか? N 個の状態を作成します。Nが事前にわかっていることを確認してください:)
1 つの計算ステップで 2 つの連続する X をスタックできますか?
「プッシュダウン オートマトン」をどのように定義しているか、具体的には遷移関数をどのように定義しているかによって異なります。一度に文字列全体をプッシュできるように PDA を定義することは確かに可能です。そのようなことがコースで許可されるかどうかを確認するには、コースのテキストを確認するか、教授に確認する必要があります。