0

I'm taking the Edx Stanford compiler course and it shows

$0*$ + $1*$ = $(0^i | i >= 0)$ u $(1^i | i >= 0)$

Sorry screen readers but in case my mathjax is illegible.

enter image description here

In the second line it shows what $1*$, ie. the iteration of 1 looks like:

"", 1, 11, 111, 1111, 11111, ...

So the union between the iteration of 0 and 1 looks like?

"""", 01, 0011, 000111, 00001111, 0000011111, ...

or

"""", 01, 0101, 010101, 01010101, ....
mLstudent33
  • 224

1 Answers1

1

I think that if you check the definition of the $+$ operation on regular expressions (which corresponds to the union operation on regular sets) in the begining of your course, you'll see that the union in this context is the same union operation as usuall on sets.
So $1^* + 0^*$ is neither of your two propositions but instead, it corresponds the set of the words written only with 0s, the words written only with 1s and the empty word.

Your first proposition corresponds to the concatenation operation $0^* \cdot 1^* = \lbrace \epsilon, 1, 11, \ldots, 0, 01, 011, \ldots , 00, 001, 0011, \ldots\rbrace$.
The second would be $(1^* + 0^*)^*$ which can be simplified to $(1+0)^*$, the set of all the words written with 0s and 1s.

Zag
  • 977