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?

Improve this question
$\endgroup$
5
  • $\begingroup$ Maybe try to write something with brackets (, ) and try to use the pumping lemma. $\endgroup$
    – nir shahar
    Jun 8, 2021 at 9:11
  • $\begingroup$ What do you mean try to write something with brackets? $\endgroup$
    – Daniel
    Jun 8, 2021 at 9:12
  • $\begingroup$ Any expression that you want, as long as you put as many brackets as possible. $\endgroup$
    – nir shahar
    Jun 8, 2021 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, 2021 at 9:13
  • $\begingroup$ Your grammar isn't even context free. $\endgroup$
    – vonbrand
    Jun 8, 2021 at 13:12

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Why is $\hat L$ not regular? $\endgroup$
    – Daniel
    Jun 8, 2021 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, 2021 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.