# Prove that grammar accepting arithmetic expressions is not regular

I created a grammar which accepts all arithmetic expressions consisting of $$+,-,*,/, (, )$$.

I created the following grammar:

$$S \rightarrow M+-M$$

$$+-M \rightarrow +M+-M$$

$$+-M \rightarrow -M+-M$$

$$+-M \rightarrow \epsilon$$

$$M \rightarrow E*/E$$

$$*/E \rightarrow *E*/E$$

$$*/E \rightarrow /E*/E$$

$$*/E \rightarrow \epsilon$$

$$E \rightarrow a$$

$$E \rightarrow (S)$$

Where S is sum and our starting symbol, +,-,*,/,(,),a are terminal symbols and S,M, +-M, E, */E, () are nonterminals.

Now the question is, how do I prove that such grammar can't be regular?

• Maybe try to write something with brackets (, ) and try to use the pumping lemma. Jun 8, 2021 at 9:11
• What do you mean try to write something with brackets? Jun 8, 2021 at 9:12
• Any expression that you want, as long as you put as many brackets as possible. Jun 8, 2021 at 9:13
• The idea is to use the fact that brackets come in pairs to ensure problems when you try to use the pumping lemma Jun 8, 2021 at 9:13
• Your grammar isn't even context free. Jun 8, 2021 at 13:12

Lets call this language $$L$$ and assume towards contradiction that it is regular.

We build the following homomorphism $$h:\Sigma\rightarrow \{0,1\}^*$$ by:

$$h(x)=\cases{0&x=(\\1 &x=)\\\epsilon&otherwise}$$

Since regular languages are closed under homomorphism, then $$h(L)$$ is regular as well. Now, lets take a look at the following language: $$\hat L:=h(L)\cap L(0^*1^*)$$.

Clearly, $$\hat L$$ is regular as the intersection of two regular languages. But also, its not hard to see that $$\hat L=\{0^n1^n|n\in \mathbb{N}\}$$ and we know this language isn't regular.

Hence we got a contradiction, meaning that $$L$$ couldn't have been regular.

• Why is $\hat L$ not regular? Jun 8, 2021 at 9:34
• its a well known language that isnt regular. If you want a simple proof, use the pumping lemma Jun 8, 2021 at 9:39