# Unambiguous grammar for regular expressions

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^*$
• Ok fade2black so now the grammar $G$ should recognize regular expressions. I wonder if i can use $\epsilon$ instead of $\emptyset$ in the grammar – Jack Nov 3 '17 at 20:03
• $\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. – fade2black Nov 3 '17 at 20:35
• I think your question already answers itself. You're on the right track. – 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.

$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$

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