Execution Of Npda

Execution of NPDA: Assume that someone is in the middle of stepping through a string with a DFA, and we need to take over and finish the job. There are two things that are required to be known:

1. the state of the DFA is in, and
2. what the remaining input is.

But if the automaton is an NPDA we need to know one more viz., contents of the stack.

Instantaneous Description of a PDA: The Instantaneous description of a PDA is a triplet (q, w, u), where q = current state of the autom aton

w = unread part of the input string

u = stack con tents (writ ten as a string, with the leftmost symbol at the top of the stack).

Let the symbol “|–” denote a move of the NPDA, and suppose that

d(q1 , a, x) {(q2 , y), }, = K then the following is possible:

(q1 , aW, xz) |– (q2 ,W, yz)

where W indicates the rest of the string following ‘a’ and Z indicates the rest of the stack contents underneath the x. This notation tells that in moving from state q1 to state q2, an ‘a’ is consumed from the input string aW, and the x at the top (left) of the stack xZ is replaced with y, leaving yZ on the stack.

Accepting Strings with an NPDA: Assume that you have the NPDA given by

• M = (Q, S,G,d, q , z, F ).
• To recognize string w, begin with the instantaneous assumption
• (q0 , w, z)
• where
• q0 = start state
• w = entire string to be processed, and
• z = start stack symbol.

Starting with this instantaneous description, make zero or more moves, just as is done with an NFA.

There are two kinds of moves that can be made:

(a) l-Transitions: If you are in state q1, x is the top (leftmost) symbol in the stack, and

d(q1 , l, x)={(q2 , w2 ),. . . . . }  

then you can replace the symbol x with the stringw2 and move to q2.

(b) Nonempty transitions:If you are in the state q1, ‘a’ is the next unconsumed input symbol, x is the top (leftmost) symbol in the stack, and

d(q1 , a, x) = {(q2 , w2 ),. . . . . }  

then you can remove the ‘a’ from the input string, replace the symbol x with the string w2, and move to state q2.

If you are in the final  state when you reach the end of the string (and may be make some l-transition after reaching the end), then the string is accepted by the NPDA. It does not matter what is on the stack.

An Example of NPDA Execution

Let us consider the NPDA given by

It is possible for us to recognize the string “aaabbb” using the following sequence of “Moves”: