I am reading a book example on regular expressions and I have a trouble to get why the asnwer is correct.
"Write a regular expression for the regular language that contains all the strings by 0's and 1's , in which the digits next to 1's , are always 0's"
So , basically , we just need to create a regular expression , that "abandons" '11's (two 1's net to each other)
THe answer in the book is:
$(\epsilon|1)((101)^*|0)^*(1|\epsilon)$
after the suggestion of an aswer below we could simply write: $((\epsilon|1)((101)^*|0)^*$
I don't get it.
$((101)^* | 0)^*$ can create a term $(101)(101)$ which is forbidden , can't it??
or maybe we have $1(101)$ by this regular expression, can't we?
I am thinking it should be something like:
$(1|\epsilon)((01)^*|0)^*$
$\left((101)^*\mid 0\right)^*$ cannot create $(101)(101)$, since it cannot create any parentheses, but it can create $101101$ and $1101$, which, as you say, are not in the language. Your suggestion of $(\epsilon\mid 10)(1\mid\epsilon)\left((01)^*\mid 0\right)^*(01\mid\epsilon)$ works but is more complicated than necessary: $(\epsilon\mid 1)\left(01\mid 0\right)^*$ does the job.