Search code examples
pushdown-automatonautomaton

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

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?

Solution

  • 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.