言語を認識する「プッシュダウンオートマトン」の設計：a^n b^m | N <= M <= 3nの

Question

私は私の試験のオートマトンと形式言語のために勉強して、私は言語を認識PDA設計する必要があります：

a^n b^m | n<= m <= 3n 

を、私は若干のアイデアを持っているが、私はこだわっています

最初の思考プロセスは、すべての「」と、それぞれ「」押し「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 

だから私は解決策を考えたが、私が間違っている、私は何かをやっていると思う：これで違う？

Answer 1

ええ、あなたのオートマトンは、文字列abを受け入れないので正しくない、または空文字列を受け入れます。

- q0 Z 
a q0 AZ 
b q1 AZ 
(doesn't accept) 

- q0 Z 
(doesn't accept) 

q1は受け付けていませんので、あなたのマシンはあなたが記述言語であるABを、受け入れることができない：あなたは、マシンの状態を、以下の配列を取得します。

適切な一般的な考え方があります。表示されているそれぞれにAを追加し、表示されている1,2、または3つのbのグループごとにAを削除します。この策定は明らかに非決定論的ですが、DPDAに求められていなければOKです。

(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) 

これらの遷移は、マシンが非決定的に

(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.のために1、2、または3のBさんをカウントするかどうかを選択することを可能にし、 Aを除去し、q1に戻り、スタックから追加のAを除去することができる。

(q1, -, Z) => (qf, Z) 

この移行により、Aのスタックが使い尽くされた後にPDAが文字列を受け入れることができます。入力にbが残っていると、そこに遷移が定義されていないため、PDAはqfでクラッシュすることに注意してください。クラッシュするので、文字列は受け入れられません（スタックが空で受け入れ状態でクラッシュしても）。

この問題のもう1つのアプローチは、この言語用のCFGを構築し、次にトップダウンまたはボトムアップパーサを構築することです。この言語のための簡単なCFGは次のとおりです。

S := aSb | aSbb | aSbbb 

DPDAを希望する場合、それは難しい問題と答えは「何もDPDAが存在しない」とすることができる：1です。正直言って、私はこの言語のためのDPDAの構築を何ら考えていません。基本的な考え方は、次のプロパティを持つ3つのパーティションにあなたのスタックを分割することをあるよう

Answer 2

、私はこれは少し遅れているけど、私はクロスに同じ問題を持って、別の解決策場合、私は思った

• 最初のパーティション（サイズ= N、文字= 'A'）
• 第二パーティション（サイズ= 2N、文字= 'B'）
• 第3仕切：（サイズ= N、文字= 'A'）

ほとんどの上部のパーティション - 第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- 

は、我々はBの数が少なくともAの数に等しいことを確認するために、第1四半期に行きます

(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) 

は、今、私たちはBの数を2N以下であることを確認するために、第2四半期に行く：

(q2 , b , B) => (q2 , match) 
(q2 , # , A) => (qf , -) 
(q2 , # , B) => (qf , -)