0
$\begingroup$

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?

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

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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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