I want to design a context-free grammar that generates words that either both start and end with $c$, or contain the same amount of $a$-s and $b$-s. Here is what I have. The nonterminals are $S,X,Y$, the terminals are $a,b,c$, the start symbol is $S$, and the productions are

\begin{align} &S \to aYS \mid cXc \mid bXS \mid cYc \mid \varepsilon \\ &X \to a \mid bXX \\ &Y \to b \mid aYY \\ \end{align}


1 Answer 1


Your grammar doesn't seem to generate $caac$. Indeed, in order to generate this work, a simple case analysis shows that the derivation must start $$ S \to cYc \to caYYc, $$ at which point it is clear that we cannot generate $caac$.

I assume you know how to generate the language $c\Sigma^*c$, as well as the language of all words with an equal number of $a$-s and $b$-s. Instead of combining them in a complicated way, write grammars for both, and then join them together using a rule of the sort $S \to S_1 \cup S_2$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.