A regular expression that defines a language

491 Views Asked by At

I am reading a chapter about regular expressions and there is the following example present in the book :

Let $\sum =\left \{ 0,1 \right \}$. Find regular expressions over $\sum$ that define the following language.

The language consisting of all strings of 0’s and 1’s that do not contain two consecutive 1’s

Their answer is $\left ( 0\mid 10 \right )^{*}\left ( \epsilon \mid 1 \right )$

I thought that it would be $\left ( 10 \right )^{*}$ . Why is my answer not correct?

Or why $\left ( 0\mid 10 \right )^{*}1$ is not correct either?

2

There are 2 best solutions below

2
On BEST ANSWER

$0 \in L$, but not in your language $(10)^*$.

Further $$ (0|10)^*(\epsilon | 1) = (0|10)^* \epsilon \,|\, (0|10)^* 1 = (0|10)^* \,|\, (0|10)^* 1 $$ E.g. $10 \in (0|10)^*$, which is in $L$ but not in your $(0|10)^*1$.

0
On

The string "$00$" matches the requirements but your answers doesn't permit that to happen.