If you have a question saying "draw the NFA for the following language" what difference does it makes if the language is $(0^* \cup1^*)$ vs $(0 \cup1)^*$ in otherwords what difference does it make for the diagram if the star is on the inside or outside of the brackets?
0
$\begingroup$
$\endgroup$
4
$\begingroup$
$\endgroup$
Let "$\rightarrow$" stand for "denotes". Then we have
- $0\cup 1\rightarrow \{0, 1\}$, so
- $(0\cup 1)^*\rightarrow \{\epsilon, 0, 1, 00, 01, 10, 11, 000,\dotsc\}$, i.e., all words that can be made by concatenating any number of $0$s and $1$s.
- $0^*\rightarrow \{\epsilon, 0, 00, 000, 0000, \dotsc\}$, all words that can be made of just $0$s.
- $1^*\rightarrow \{\epsilon, 1, 11, 111, 1111, \dotsc\}$, all words that can be made of just $1$s, so
- $(0^*\cup 1^*)$, the union of the two sets above $\rightarrow \{\epsilon, 0, 1, 00, 11, 000, 111, 0000, 1111, \dotsc\}$.
So in particular $(0^*\cup 1^*)$ will never contain strings with both $0$s and $1$s, whereas $(0\cup1)^*$ will contain all of $(0^*\cup1^*)$ along with lots of other words.
answered Dec 6 '15 at 18:48
-
$\begingroup$ Thanks. And just to confirm, in this stuff "U" union "," comma and the word "or" all mean the same thing right? $\endgroup$ – Celeritas Dec 6 '15 at 21:31
-
$\begingroup$ If you're talking about regular expressions, then yes, your understanding is correct (though I've never seen the word "or" in a regular expression). $\endgroup$ – Rick Decker Dec 7 '15 at 15:01
2
$\begingroup$
$\endgroup$
Exactly the same as the difference between $x^2+y^2$ and $(x+y)^2$. You apply the ${}^*$ to the thing the notation says you apply it to.
answered Dec 6 '15 at 0:51
-
$\begingroup$ Can you draw a picture of the two? Or is there a tool I can use to check my answer? $\endgroup$ – Celeritas Dec 6 '15 at 0:59
0
$\begingroup$
$\endgroup$
- = kleene star (with containing null i.e lamda its sign like ^)
= kleene star (not containing null)
- (Null) * (NULL)= NULL
- (NuLL) * a = a a * null = a
we use this formula inside or outside the DFA
-
$\begingroup$ Please proof-read your answer. I don't think it came out the way you intended (due to how Markdown interprets characters like
*). Also, I don't see how this answers the question. Perhaps it might help to expand the answer and explain how it connects to the question. $\endgroup$ – D.W.♦ Dec 7 '15 at 17:03
