設計下推自動機來算的字符數

的字母：A，B，C 我試圖確定它接受設計下推自動機來算的字符數

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

我想有些會被接受的字符串是一個PDA：＃ABC＃; ＃爲aabbcc＃; ＃aaabbbccc＃; ＃abbccc＃; ＃aaabbc＃etc a，b和c的數量不一定相等。

在最右邊的黑色空間開始下推自動機的頭部。

通常我寫我的掌上電腦在列：

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

等等...

來源

2010-11-13 Bobby S

a^n b^n c^n - 你說的沒錯。＃cab＃是不可接受的 – 2010-11-13 17:11:11

我誤解了這個，或者'm'是'k'的一個不必要的別名？ – jball 2010-11-13 17:38:35

不，我相信你正在閱讀那個正確的 – 2010-11-13 17:43:30

我想你所描述的語言不是上下文無關，因此不能與PDA認可。問題是你需要強制執行一個跨越任意長的子字符串的限制（n + p = 2m），但不允許「泵」（當試圖使用上下文無關語言的抽象引理來構造一個證明）。

來源

2010-11-13 17:39:17

謝謝，我同意你的看法。我將通過抽象引理顯示這不是上下文無關的。 – 2010-11-13 17:44:00

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-21 20:14:57

設計下推自動機來算的字符數

回答

相關問題