2
$\begingroup$

How to define a non ambiguous grammar for regular expressions on the $\Sigma = \{a,b\}$ alphabet?

Given that:

If $\Theta = \{+, ^*, (,),\cdot, \emptyset\}$ is a set of symbols

A regular expression on $\Sigma$ is a string such that one of the following condition applies

  1. $r = \emptyset$
  2. $r \in \Sigma $
  3. $r = (s+t)$ or $ r = (s\cdot t)$ or $r = s^*$
$\endgroup$
4
  • $\begingroup$ Ok fade2black so now the grammar $G$ should recognize regular expressions. I wonder if i can use $\epsilon$ instead of $\emptyset$ in the grammar $\endgroup$
    – Jack
    Nov 3, 2017 at 20:03
  • $\begingroup$ $\epsilon$ cannot be used instead of $\emptyset$ since they have different meanings in regular expressions. The first one corresponds to a regular set with a single element $\epsilon$, the empty string, while the other is just an empty set containing no strings. $\endgroup$
    – fade2black
    Nov 3, 2017 at 20:35
  • $\begingroup$ I think your question already answers itself. You're on the right track. $\endgroup$ Nov 3, 2017 at 20:55
  • $\begingroup$ What are r, s, and t ? $\endgroup$
    – babou
    Nov 16, 2021 at 18:40

1 Answer 1

3
$\begingroup$

I need to define a context free grammar to recognize regular expression. I know also that CF grammars are used to recognize mathematical expressions. so the grammar $G$ should recognize regular expressions.

$G:$

$ E \rightarrow E + T \mid T $

$ T \rightarrow T \cdot F \mid F $

$ F \rightarrow(E) \mid E^* \mid a\mid b\mid\emptyset$

$\endgroup$
6
  • 1
    $\begingroup$ $F^*$, not $E^*$ $\endgroup$
    – rici
    Nov 3, 2017 at 22:53
  • $\begingroup$ @rici $F^*$ or $E^*$, the grammar will generate the same set, won't it? $\endgroup$
    – fade2black
    Nov 3, 2017 at 23:01
  • $\begingroup$ @fade yes, but only one of them is unambiguous. $\endgroup$
    – rici
    Nov 3, 2017 at 23:09
  • $\begingroup$ @rici did you find a string having two different leftmost derivations? Could you share it? $\endgroup$
    – fade2black
    Nov 3, 2017 at 23:22
  • $\begingroup$ @fade: I didn't look very hard :-). Try $a+b^*$ $\endgroup$
    – rici
    Nov 3, 2017 at 23:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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