Mathematical Foundation of Computer Science

DHARM

NON-REGULAR GRAMMARS 297

[While other moves like δ (q 2 , a, Z 0 ) → Ø and δ (q 2 , b, Z 0 ) → Ø where state Ø signifies that
automaton crashes if it reaches to this state]
Hence PDA will be an deterministic PDA.
To verify that above moves are correct we assume a string w = a b a c a b a , then trace
the transitions over w, i.e.,

(q 1 , a b a c a b a, Z 0 )  (q 1 , b a c a b a, AZ 0 )  (q 1 , a c a b a, BAZ 0 )  (q 1 , c a b a,

ABAZ 0 )  (q 2 , a b a, ABAZ 0 )  (q 2 , b a, BAZ 0 )  (q 2 , a, AZ 0 )  (q 2 , ∈, Z 0 )  (q 2 , ∈, ∈)

[Accepted]

Example 11.17. Construct a PDA for the language L = {w ∈ {a, b}* / w wR}.

Sol. From the exercise 11.11 we found that language L is a context free language so an equiva-

lent PDA can be constructed for it. Since we assume that language L is the language accepted

by the PDA having empty stack mechanism i.e., L = N(M), where M be a PDA where,

M = ({q 1 , q 2 }, {a, b}, {Z 0 , A, B), δ, q 1 , Z 0 , Ø)

where δ’s are constructed as follows,

• Since ∈ is in the language L so, δ (q 1 , ∈, Z 0 ) → {(q 1 , ∈)}


• For the first occurrence of input symbol a or b corresponding stack symbol A or B will
  be pumped, i.e.
  δ (q 1 , a, Z 0 ) → {(q 1 , AZ 0 )}
  δ (q 1 , b, Z 0 ) → {(q 1 , BZ 0 )}


• For the next occurrences of consecutive a’s or consecutive b’s, there are two possible
  moves such that either stack symbol will be popped or corresponding symbol A or B
  will be pushed, i.e.
  δ (q 1 , a, A) → {(q 2 , ∈), (q 1 , AA)}
  δ (q 1 , b, B) → {(q 2 , ∈), (q 1 , BB)}


• For alternate occurrences of symbols a and b corresponding stack symbol A or B will
  be pumped, i.e.
  δ(q 1 , a, B) → {(q 1 , AB)}
  δ(q 1 , b, A) → {(q 1 , BA)}


• During cross checking of occurrences of input symbols (from state q 2 ) corresponding
  stack symbols will be popped, i.e.
  δ (q 2 , a, A) → {(q 2 , ∈)}
  δ (q 2 , b, B) → {(q 2 , ∈)}


• Finally, δ (q 2 , ∈, Z 0 ) → {(q 2 , ∈)} Accepted
  To verify above moves consider an string w = a a b b a a (∈ L), and then trace the moves, i.e.,

(q 1 , a a b b a a, Z 0 )  (q 1 , a b b a a, AZ 0 )  {(q 2 , b b a a, Z 0 ), (q 1 , b b a a, AAZ 0 )}
III
Trace the moves from ID I and from ID II separately, i.e.
I. (q 2 , b b a a, Z 0 )  (q 2 , b a a, ∈) ×
Since stack becomes empty without reading of complete input string so automaton crashes
through this path.