# Proving that a language given by a CFG is not regular [duplicate]

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

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})$$