Difference in having * inside vs outside of brackets for NFA

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?

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.

• Thanks. And just to confirm, in this stuff "U" union "," comma and the word "or" all mean the same thing right? – Celeritas Dec 6 '15 at 21:31
• 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). – Rick Decker Dec 7 '15 at 15:01

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.

• Can you draw a picture of the two? Or is there a tool I can use to check my answer? – Celeritas Dec 6 '15 at 0:59
• = kleene star (with containing null i.e lamda its sign like ^)
• = kleene star (not containing null)

1. (Null) * (NULL)= NULL
2. (NuLL) * a = a a * null = a

we use this formula inside or outside the DFA

• 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. – D.W. Dec 7 '15 at 17:03