Search code examples
computer-scienceautomata

How to design NPDA for accepting these languages?

I wanna design the NPDA(non-deterministics pushdown automata) that accepts below two languages. Please explain how to design them.

L(r) where r = abb*aba*
L(r) = {a^nb^2n : n > 0}
Solution

  • The first one might work like this:

    1. read an a in the first state and push an a onto the stack; transition to a new state
    2. read a b in the second state and push a b onto the stack; transition to a new state
    3. read b in the third state forever, pushing b onto the stack each time. if you eventually read an a, transition to a new state and push an a on the stack
    4. read b in the fourth state, pushing b onto the stack; transition to a new state
    5. read a in the fifth state forever, pushing a on the stack; at any point, nondeterministically transition to a new state
    6. in the sixth state, just read nothing and pop stuff off the stack. this state is accepting and the npda accepts the input string iff the input has been read completely and the stack is empty.

    The second one might work like this:

    1. read at least one a and push it on the stack, then transition to a new state
    2. keep reading a forever in the second state, pushing one a onto the stack each time; if you see b, go to a new state
    3. read b in the third state, and pop an a off the stack; go to a new state
    4. read b in the fourth state, and leave the stack alone; go back to the third state
    5. continue reading b in the third and fourth states until you run out of input; if you are in the fourth state, have run out of input and have an empty stack, then and only then does the pda accept the input string

    EDIT: an outline of required transitions.

    First one:

    q0 is initial
(q0, a, Z) -> (q1, aZ)
(q1, b, a) -> (q2, ba)
(q2, b, b) -> (q2, bb)
(q2, a, b) -> (q3, ab)
(q3, b, a) -> (q4, ba)
(q4, a, b) -> (q4, ab)
(q4, a, a) -> (q4, aa)
(q4, e, a) -> (q5, a)
(q4, e, b) -> (q5, b)
q5 is accepting

    Second one:

    q0 is initial
(q0, a, Z) -> (q1, aZ)
(q1, a, a) -> (q1, aa)
(q1, b, a) -> (q2, a)
(q2, b, a) -> (q3, e)
(q3, b, a) -> (q2, a)
q3 is accepting

    Both NPDAs are designed to accept in the accepting state when the stack is empty and the input is exhausted.