2

アルファベット：a、b、c私は受け入れるPDAを定義しようとしています

 a^n b^m c^p : n + p = 2k for some integer k, m = k, and n, m, p, k >= 0

受け入れられる文字列は次のとおりです。＃abc＃; ＃aabbcc＃; ＃aaabbbccc＃; ＃abbccc＃; ＃aaabbc＃などa、b、cの数は必ずしも同じではありません。

一番右の黒いスペースでプッシュダウンオートマトンの頭を開始します。

通常、私はPDAを列に書き込みます。

State:    Symbol Read:    Next State:    Head Instruction:    
s         #               r1             Left
r1        c               r2             #

等々...

4

2 に答える 2

2

あなたが説明した言語は文脈自由ではないため、PDA では認識できないと思います。問題は、任意の長さの部分文字列にまたがる制約 (n+p = 2m) を強制する必要があることですが、「ポンピング」することは許可されていません (文脈自由言語のポンピング補題を使用して証明を構築しようとする場合)。

于 2010-11-13T17:39:17.143 に答える
2 
M=(K, E, q0, F, delta, stack_alphabet)
K={q0,q1,q2}
E={a,b,c,z}
F={q2}
stack_alphabet={a,b,z}
delta=
{
 *pop*     *push*
(q0, e, e)(q1, z)
(q1, a, e)(q1, a)
(q1, b, a)(q1, e)
(q1, b, z)(q1, bz)
(q1, c, b)(q2, e)
(q2, c, b)(q2, e)
}
于 2010-12-21T20:14:57.960 に答える