Prove that grammar accepting arithmetic expressions is not regular

Question

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?

Answer 1

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.