-1
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | | | | |
$\endgroup$

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