Let the input alphabet be S = {a b c} and L be the language of all words in which all the a’s come before the b’s and there are the same number of a’s as b’s and arbitrarily many c’s that can be in front, behind, or among the a’s and b’s. Some words in L are abc, caabcb, ccacaabcccbccbc.
(i)Write out all the words in this language with six or fewer letters.
(ii)Show that the language L is not regular.
(iii)Find a PDA that accepts L.

(iv)Find a CFG that generates L.