Construct a Pushdown Automata PDA that accepts the language

Construct a Pushdown Automata (PDA) that accepts the language generated by the following Context-Free Grammar (CFG):

S XaaX

X aX | bX |

Solution

We create a PDA which has only three states s1, s2 and s3. The rules are:

(s,,) -> (s1,$)

(s1, a, ) -> (s1,1)

(s1, b, 1) -> (s1,)

(s1,b,$) -> (s1,$)

(s1, a, 1) -> (s2,)

(s2,,)->(s2,)