computation-theory

What will be the DFA for (0+1)*?

I have drawn this diagram below. But i want to be sure of the answer as + and the * operator are confusing.

     _  
    | \
--> q_|- 0,1,E

Here my DFA has only one state q. Both 0,1,empty are redirected to q itself.

Solution

  • (0+1) means you can select a 0 or 1 but not both. The + is analogous to OR. The star means that you can do this selection Zero or more times.

    Hence, (0+1)* will include any String of 0s and 1s including the empty string.