Question

Consider the context-free grammar G = ( {S}, {a, b}, S, P) where P = { S -> aaSb | aab }.

Construct a NPDA M that such that L(M) = L(G).

I would like the transition graph for this NPDA please.

Answer 1

Given CFG is

G = ( {S}, {a, b}, S, P) where P = { S -> aaSb | aab }

Here {S} are the non terminals

{a,b} are the terminals

S is start symbol

P contains the set of productions or rules

From the productions we get the idea that the language contains set of strings of a and b which even number of a's concatenated with half the number of b's as of a's

L(G)=a²ⁿbⁿ

For constructing a NPDA we can push b's for every 2 a's read and we can construct accept condition using empty stack condition

so, using the abode idea the NPDA formed can be represented by the below diagram

Here the NPDA is represented by

M = ({Q0,Q1,Q2,Q3}, {a,b}, {b,z}, ,Q0, z, Q3)

Where {Q0,Q1,Q2,Q3} are the set of states

{a,b} are the set of terminals

{b,z} are the set of stack alphabets

Q0 is start state

z is the initial stack alphabet

Q3 is the final state

is the transition function given by the following table

	a	b
Q0	(a,z/z),(a,b/bb)
Q1	(a,z/bz),(a,b/b)	(b,b/)
Q2		(b,b/)
Q3	(,z/z)	(,z/z)

Where a,z/z means on seeing input a and top of the stack is z then keep the top of the stack as it is

and a,b/bb means on seeing input a and top of the stack is b then push b onto the stack.

b,b/ means we pop the stack on seeing input b and top of the stack is also b.

In the above NPDA we push b onto the stack whenever we read 2 a's and keep popping b's until the stack is empty

Note:if the top of the stack is z then it is considered to be empty