# Execution Of Npda

**Accepting Strings with NPDA (Formal Version)**

The notation “|–” is used to indicate a single move of an NPDA.

“|–* ” is used to indicate a sequence of zero or more moves.

“|– ” is used to indicate a sequence of one or more moves.

If *M *= (*Q*, S,G,d, *q *,Z, *F *) 0 is an NPDA, then the language accepted by M, L(M), is given by

*L***( M) **

**=**

**{**∈ Σ

*w******

**: (**

*q*,*w*,*z*) |–*****

**(**∈

*p*, ,*u*),*p*

*F***,**∈

*u***Γ**

*****

**}**

**0**λ

**.**

**Example 1: **Construct a Push Down Automata (PDA) accepting

{*a *^{n }*b *^{m }*a *^{n }|*m*, *n *≥1} by empty store.

S**olution**: The PDA which will accept

Therefore we can see that we start storing *a*’s till *b *occurs ((1) and (2)). When the current input symbol is *b*, the state changes, but no change in PDS occurs ((3)). Once all the *b*’s in the input string acts over ((4)), the remaining *a*’s are erased ((5)).

Using (6), *z*0 is erased. Therefore we have

Therefore we see that *a *^{n}*b*^{m}*a ** ^{n}*Î

*N*(PDA).