Convert the following grammar to a one state PDA.

S → bA |
S → aB |

A → a |
B → b |

A → aS |
B → bS |

A → bAA |
B → aBB |

Use the Pumping Lemma for CFLs to show the following languages are not context free.

L = { a

^{m}b^{m}c^{n}| m < n }L = { ww

^{R}w | w ∈ (a+b)* }

For each of the following languages, specify whether the language is (i) regular, (ii) context-free, but not regular, or (iii) not context free. Justify your answer.

{ w in (a+b)* | each symbol appears the same number of times }

{ w in (a+b+c)* | each symbol appears the same number of times }

{ a

^{m}b^{n}| 5m + 4n = 44 }