私は試験のオートマトンと形式言語を勉強しています。言語を認識するPDAを設計する必要があります。
a^n b^m | n<= m <= 3n
私は少し考えがありますが、私はこれで立ち往生しています：
すべての「a」と各「a」が「A」をプッシュする最初の思考プロセス
(q0, a, Z)= (q0, AZ)
(q0, a, A)= (q0, AA)
(q0, b, A)= (q1, A)
(q1, b, A)= (q2, A)
(q2, b, A)= (q3, lambda)
(q3, b, A)= (q1, A)
(q3, lambda, A)= (qf, Z)
(q3, lambda, Z)= (qf, Z)
qf = final state, lambda= delete top of stack, Z= initial symbol of the stack
だから私は解決策を考えました、しかし私は正しくないと思います、私は何か間違ったことをしていますか？
ええ、あなたのオートマトンは文字列ab、またはそのことについては空の文字列を受け入れないので正しくありません。次の一連のマシン状態が得られます。
- q0 Z
a q0 AZ
b q1 AZ
(doesn't accept)
- q0 Z
(doesn't accept)
q1が受け入れていないため、マシンは、記述した言語のabを受け入れられません。
あなたは正しい一般的な考えを持っています：あなたが見るそれぞれのaにAを追加し、次にあなたが見る1、2、または3bのグループごとにAを削除します。この定式化は明らかに非決定性ですが、DPDAが要求されない限り、それで問題ないと想定します。
(q0, a, Z) => (q0, AZ)
(q0, a, A) => (q0, AA)
(q0, -, Z) => (q1, Z)
(q0, -, A) => (q1, A)
これらの遷移はaをカウントし、スタックにAを追加します。aの読み取りが終了したら、次の状態q1に進み、bのカウントとAのポップを開始できます。
(q1, -, A) => (q2, A)
(q1, -, A) => (q3, A)
(q1, -, A) => (q4, A)
これらの遷移により、マシンは特定のAに対して1つ、2つ、または3つのbをカウントするかどうかを非決定的に選択できます。
(q2, b, A) => (q1, -)
(q3, b, A) => (q5, A)
(q5, b, A) => (q1, -)
(q4, b, A) => (q6, A)
(q6, b, A) => (q7, A)
(q7, b, A) => (q1, -)
これらの遷移は、実際には1つ、2つ、または3つのbのカウントとAの削除を処理し、スタックから追加のAを削除できるようにq1に戻ります。
(q1, -, Z) => (qf, Z)
この遷移により、Aのスタックが使い果たされると、PDAは文字列を受け入れることができます。入力にbが残っている場合、遷移が定義されていないため、PDAはqfでクラッシュすることに注意してください。また、クラッシュするため、文字列は受け入れられません（スタックが空で、受け入れ状態でクラッシュした場合でも）。
この問題に対する別のアプローチは、この言語のCFGを作成してから、トップダウンまたはボトムアップのパーサーを作成することです。この言語の簡単なCFGは次のとおりです。
S := aSb | aSbb | aSbbb
DPDAが必要な場合、それはより困難な問題であり、答えは「DPDAが存在しない」である可能性があります。正直なところ、私はこの言語のDPDAの構築については何も考えていません。
これは少し遅いことはわかっていますが、同じ問題が発生し、別の解決策があるかどうかを考えたので、基本的な考え方は、スタックを次のプロパティで3つのパーティションに分割することです。
最上部のパーティション-3番目のパーティション-その目的は、bのカウントが少なくともaのカウント-n-と等しいことを確認することであり、中央のパーティション-2番目のパーティション-は、bのカウントが以下であることを確認することです。 2n、最後のパーティションは、bのカウントが2nを超えないようにすることです。これが基本的な考え方であり、もちろんNPDAです。正確な遷移は次のとおりです。
(q0 , a , #) => (q0 , A#)
(q0 , a , A) => (q0 , AA)
(q0 , a , B) => (q0 , AB)
(q0 , b , A) => (q0 , BA)
(q0 , b , B) => (q0 , BB)
(q0 , lambda , A) => (q0 , AA)
(q0 , lambda , B) => (q0 , AB)
(q0 , lambda , B) => (q0 , BB)
(q0 , lambda , A) => (q0 , BA)
(q0 , b , A) => (q1 , match) >> -match means removing the top of the stack with the current element-
ここで、q1に移動して、bのカウントが少なくともaのカウントと等しいことを確認します。
(q1 , b , A) => (q1 , match)
(q1 , # , B) => (qf , -) >> -this means that i matched equal number of a's and b's and i can halt if there is no more input-
(q1 , b , B) => (q2 , match)
ここで、q2に移動して、bのカウントが2n以下であることを確認します。
(q2 , b , B) => (q2 , match)
(q2 , # , A) => (qf , -)
(q2 , # , B) => (qf , -)