This question already has an answer here:

Consider the language defined by the following grammar: $$ \begin{align*} &S \rightarrow E \\ &S \rightarrow \epsilon \\ &E \rightarrow E+E \\ &E \rightarrow E-E \\ &E \rightarrow \mathsf{STRING} \mid \mathsf{LOCTRAN}(E , \mathsf{DIGITS}) \end{align*} $$ How can I prove that this language is not regular using the pumping lemma? I don't know which string to use.


marked as duplicate by fade2black, Evil, David Richerby, Raphael Sep 20 '17 at 17:27

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.


A basic example that is context-free but nonregular is the language $\{ a^nb^n \mid n\ge 0\}$.

Here this structure is hidden inside the language. You can find it using the recursive productions

$$E \rightarrow \mathsf{STRING} \mid \mathsf{LOCTRAN}(E , \mathsf{DIGITS})$$


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