DHARM296 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE•δ (q 1 , b, X) → {(q 2 , ∈)} [If next input alphabet is b then pop the stack symbol]
•δ (q 2 , b, X) → {(q 2 , ∈)} [For the consecutive occurrences of b’s, stack symbol
will be poped again]
•δ (q 2 , ∈, Z 0 ) → {(q 2 , ∈)} [If there is no input symbol left and stack also left with
start symbol Z 0 only then this symbol is also poped]
And the machine stops.
Here we show only the accepted moves of the PDA and 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 we define L as,
L = L (N) = {x / (q 1 , x, Z 0 ) (q 2 , ∈, ∈)}
To verify that above moves are correct we assume a string x = a a a b b b ∈ L, then trace
the transitions over x, i.e.,
(q 1 , a a a b b b, Z 0 ) (q 1 , a a b b b, XZ 0 ) (q1, a b b b, XXZ 0 ) (q 1 , b b b, XXXZ 0 )
(q 2 , b b, XXZ 0 ) (q 2 , b, XZ 0 ) (q 2 , ∈, Z 0 ) (q 2 , ∈, ∈) [Accepted]
Example 11.16. Construct a PDA for the language L = {w c wR / w ∈ {a, b}}.
Sol. Since language L is a context free language so an equivalent PDA can be constructed. Also
assume L = N(M), where assume PDA M will be,
M = ({q 1 , q 2 }, {a, b, c}, {Z 0 , A, B), δ, q 1 , Z 0 , Ø)
Where δ are as follows,
•δ (q 1 , a, Z 0 ) → {(q 1 , AZ 0 )} [If the first input alphabet is a, then symbol A will
be pushed into the stack];
δ (q 1 , b, Z 0 ) → {(q 1 , BZ 0 )} [If the first input alphabet is b, then symbol B will
be pushed into the stack];
δ (q 1 , c, Z 0 ) → {(q 2 , Z 0 )} [If input alphabet is c then stack remains un-
changed];
•δ (q 1 , a, A) → {(q 1 , AA)} [For the next occurrence of a’s, stack symbols A’s
will be pumped];
δ (q 1 , b, A) → {(q 1 , BA)} [For the next occurrence of b’s, stack symbols B’s
will be pumped];
δ (q 1 , c, A) → {(q 2 , A)} [For the next occurrence of c, stack remains un-
changed];
Similarly,
•δ (q 1 , a, B) → {(q 1 , AB)};
δ (q 1 , b, B) → {(q 1 , BB)};
δ (q 1 , c, B) → {(q 2 , B)};
For the matching of substring lies left side of symbol c with the substring lies right side
of c, following are the moves
•δ (q 2 , a, A) → {(q 2 , ∈)}
•δ (q 2 , b, B) → {(q 2 , ∈)}
Finally,
•δ (q 2 , ∈, Z 0 ) → {(q 2 , ∈)} Accepted