CODEWITHSUNDEEP
automationtheoryformal-languagespushdown-automaton
Madan Raj
Madan Raj

Reputation: 13

What is the PDA for this grammar?

For the grammar given below obtain the corresponding PDA:

S -> aABB | aAA
A -> aBB | a
B -> bBB | A
C -> a

I tried solving it but apparently it was incorrect . If anyone knows how to solve it help me out.

Upvotes: 1

Views: 1258

Answers (1)

Patrick87
Patrick87

Reputation: 28302

We could try to write a nice PDA that accepts the language in an efficient and idiomatic manner, or we could just use the algorithm to produce a PDA from the grammar directly. We'll just do the algorithmic way because the other way is hard.

Our PDA can have transitions which first push the start symbol onto the stack, then proceeds to nondeterministically replace the top-of-stack symbol with the RHS of productions and consuming the input, until either all paths dead-end or the input gets exhausted at the same time as the stack empties, in which case we accept. This PDA looks like this:

q    s    St    q'    S'        comment
q0   -    Z0    q1    SZ0       put the start nonterminal on the stack
q1   -    Sx    q1    aABBx     production S -> aABB
q1   -    Sx    q1    aAAx      production S -> aAA
q1   -    Ax    q1    aBBx      production A -> aBB
q1   -    Ax    q1    ax        production A -> a
q1   -    Bx    q1    bBBx      production B -> bBB
q1   -    Bx    q1    Ax        production B -> A
q1   -    Cx    q1    ax        production C -> a
q1   a    ax    q1    x         consume terminal symbol a
q1   b    bx    q1    x         consume terminal symbol b
q1   -    Z0    q2    Z0        transition to accepting state

Let's see this PDA in action by tracing execution for the string aaaa along a path that will accept it:

q    input    St                comment
q0   aaaa     Z0                initial configuration
q1   aaaa     SZ0               wrote the start nonterminal to the stack
q1   aaaa     aABBZ0            popped S and replaced with RHS of production
q1   aaa      ABBZ0             popped a, consumed input, did not replace
q1   aaa      aBBZ0             popped A and replaced with RHS of production
q1   aa       BBZ0              popped a, consumed input, did not replace
q1   aa       ABZ0              popped B and replaced with RHS of production
q1   aa       aBZ0              popped A and replaced with RHS of production
q1   a        BZ0               popped a, consumed input, did not replace
q1   a        AZ0               popped B and replaced with RHS of production
q1   a        aZ0               popped A and replaced with RHS of production
q1   -        Z0                popped a, consumed input, did not replace
q2   -        Z0                transitioned to accept state

This construction works generally and, while it doesn't produce the nicest or most straightfoward PDA in many cases, it certainly is not a bad PDA by any means.

Upvotes: 1

Related Questions