SKEDSOFT

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 ⁿ b ^m a ⁿ |m, n ≥1} by empty store.

Solution: 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), z0 is erased. Therefore we have

Therefore we see that a ⁿb^ma ⁿÎ N (PDA).