我正在为我的考试自动机和正式语言学习，我必须设计一个识别语言的 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
所以我想到了解决方案，但我认为是不正确的，我做错了什么？
Yeah, your automaton isn't right since it doesn't accept the string ab, or the empty string for that matter. You get the following sequences of machine states:
- q0 Z
a q0 AZ
b q1 AZ
(doesn't accept)
- q0 Z
(doesn't accept)
Since q1 isn't accepting, your machine fails to accept ab, which is in the language you describe.
You have the right general idea: add an A for each a you see, and then remove an A for each group of 1, 2, or 3 b's you see. This formulation is clearly nondeterministic, but we'll assume that's OK unless a DPDA is asked for.
(q0, a, Z) => (q0, AZ)
(q0, a, A) => (q0, AA)
(q0, -, Z) => (q1, Z)
(q0, -, A) => (q1, A)
These transitions count a's and add A's to the stack. When you're done reading a's, we can go to the next state, q1, and start counting b's and popping A's.
(q1, -, A) => (q2, A)
(q1, -, A) => (q3, A)
(q1, -, A) => (q4, A)
These transitions allow the machine to nondeterministically choose whether to count one, two, or three b's for a particular 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, -)
These transitions actually handle counting the one, two or three b's and removing the A, returning to q1 to allow for the removal of additional A's from the stack.
(q1, -, Z) => (qf, Z)
This transition allows the PDA to accept strings once the stack of A's has been exhausted. Note that if there are any b's remaining on the input, the PDA will crash in qf since no transitions are defined there; and since it crashes, the string is not accepted (even though the stack is empty and it crashes in the accepting state).
Another approach to this problem is to construct a CFG for this language, and then construct a top-down or bottom-up parser. An easy CFG for this language is:
S := aSb | aSbb | aSbbb
If a DPDA is desired, that is a harder problem and one to which the answer may be "no DPDA exists". To be honest, I haven't given the construction of a DPDA for this language any thought.
我知道这有点晚了，但我遇到了同样的问题，我想如果有不同的解决方案，所以基本的想法是你将堆栈分成 3 个具有以下属性的分区
最上分区-第三个-其目的是确保b的计数至少等于a的计数-n-，中间分区-第二个-是确保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 , -)