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^*$
  • $\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 '17 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 '17 at 20:35
  • $\begingroup$ I think your question already answers itself. You're on the right track. $\endgroup$ – reinierpost Nov 3 '17 at 20:55

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.


$ E \rightarrow E + T \mid T $

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

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

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

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.