0
$\begingroup$

Why does set of all strings over the alphabet {0,1} is represented by (0+1)*? As per my understanding (0+1) means either 0 and 1 and * means 0 or more occurrence of the given string. Now when we do (0+1)* it looks like we have to select either 0 or 1 and do a * on that so the resulting should be something like

$\{\epsilon,0,1,00,11,000\dots\}$

but why is it following?

$\{\epsilon,0,1,00,01,10,11\dots\}$

$\endgroup$
2
$\begingroup$

It is a Klenee operator and it means all number of $(0 + 1)(0 + 1)\cdots$ with all possible length. As $(0+1)^{10}$ means $(0+1)(0+1)\cdots(0+1)$ for ten times. Hence, All possible combinations of $0$ and $1$ are comming in $(0+1)^*$.

In the other words by the definition, it means the union of all $(0 + 1)^i$ for all $i$ from $0$ to $\infty$.

$\endgroup$

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.