Design of a “Push Down Automata” that recognizes the language: a^n b^m | n<= m <= 3n

Question

I'm studying for my exam automata and formal languages, I have to design a PDA that recognizes the language:

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

I have a slight idea, but I'm stuck with this:

first thought process all the "a" and each "a" push an "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

So I thought the solution, but I think is not correct, I'm doing something wrong?

Answer 1

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.

Answer 2

i know this is a bit late , but i got a cross the same problem and i thought if a different solution , so the basic idea is that you partition your stack into 3 partitions with the following properties

• first partition : (size = n , character = 'A')
• second partition: (size = 2n , character = 'B')
• third partition : (size = n , character = 'A')

the most upper partition -the third one- its purpose is to make sure that the b's count at least equals the a's count -n- , the middle partition -second one- is to make sure that the b's count is less than or equal to 2n , the last partition is to make sure that the b's count does not exceed 2n ; so this is the basic idea , and of course it is an NPDA , here is the exact transitions :

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

now we go to q1 to make sure that the b's count at least equals the a's count :

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

now we go to q2 to make sure that the b's count is less than or equal to 2n :

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