Regular Expression of alternative 0's and 1's?

9.2k Views Asked by At

Let $L$ be the language of $0$'s and $1$'s in alternate positions, where
$$ L = \{ \epsilon, 0, 1, 01, 10, 01010,\ldots\}. $$

Is $(0)*$ + $(1)*$ a valid regular expression that represents this language? Why not?

1

There are 1 best solutions below

4
On BEST ANSWER

The expression $0^*+1^*$ denotes the union of $0^*$ and $1^*$. The first one denotes the set of words $\{\epsilon,0,00,000,0000,\dots\}$ and $1^*$ denotes $\{\epsilon,1,11,111,1111,\dots\}$. The expression does not do what you want.

What you want is, for example, $(01)^*+(10)^*+(01)^*0+(10)^*1$. Can you see why this works?