I have stumbled on this question:

Which of the following languages over the alphabet ${a,b,c,d}$ are context-free and which not ?

a) $L_{1} = \{wa^{3n+1}b^nw^{R} \mid w\in \{c,d\}^*,\ n>0\}$;

b) $L_{2} = \{a^{3n+1}wb^nw^{R} \mid w\in \{c,d\}^*,\ n>0\}$.

For a) I think this grammar solves it :

\begin{align*} S&\to cMc \mid dMd \mid M\\ M&\to aN\\ N&\to aaaTb \mid\varepsilon\\ T&\to \varepsilon \end{align*}

b) doesn't look so nice so I think that we might prove it with the pumping lemma,any suggestions what word to pick?


closed as unclear what you're asking by David Richerby, Evil, Discrete lizard, Yuval Filmus, Thomas Klimpel Jun 10 '18 at 21:07

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ Pay attention to the difference between {c,d}* and {c,d}. Your proposed solution for (a) restricts w to {c,d}. $\endgroup$ – Draconis May 30 '18 at 19:32
  • $\begingroup$ Thank you ,i think i have fixed it any suggestions for the second part? $\endgroup$ – Karmen May 30 '18 at 20:01
  • $\begingroup$ Still not quite: now it'll accept {c,d}? = {c,d,ε} rather than {c,d}*. $\endgroup$ – Draconis May 30 '18 at 20:26
  • 2
    $\begingroup$ Do you have any question about your answer to a)? This site isn't well-suited to "please check my answer" because it's only interesting to you and tends to degenerate into "OK, I fixed that problem. Now is it right?" and Stack Exchange can't handle discussions. $\endgroup$ – David Richerby May 30 '18 at 21:06

I think you could use the Pumping Lemma for Contextfree languages to prove that the language (b) is not contextfree. Have a look at the word $a^{3n+1}cdb^ndc$, given n as the Pumping Length.


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