0
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\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$

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.

$\endgroup$
  • $\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$
  • = 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

$\endgroup$
  • $\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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.