Question

Construct an NPDA that accepts the language defined by the given grammar and give the language in a formal expression (including a regular expression).

S -> AA|a, A-> SA|ab

Answer 1

Here from the given grammar first of all ,we must find the language accepted. For that we must find the various strings accepted to provide a formal expression language.

From the possible strings that can be formed, we get

L(G)= {a,abab,ababab,a^2ba^2b,...}
Therefore, L={a^m b^n/m>=n,n>=0}

Now let us construct the corresponding NDPA.

Logic:

In each string there are 'm' number of a's and 'n' number of b's. The number of b's is either equal to the number of a's or less than the number of a's.Thus we need a stack along with the state diagram.The count of a's and b's are maintained by the stack. We will take two stack alphabets.

T={a,z} where T= set of all the stack alphabets and z= stack start symbol.

Approach used in construction of NDPA:

Whenever 'a' comes, push it in to the stack and if 'a' comes again do the same. When 'b' comes then pop one 'a' from the stack.

So that the stack either becomes empty or will have 'a' only left out. If stack is empty or have some left out a's we can say that the string is accepted by the NPDA.

The stack transition function and transition diagram are attached as handwritten copy as the symbols used in keyboard may bring you confusions regarding the symbols.