的字母: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 #
等等...
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