CODEWITHSUNDEEP
computation-theory
Nivetha
Nivetha

Reputation: 708

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.

Upvotes: -1

Views: 4414

Answers (3)

Cuza
Cuza

Reputation: 1

Trick is whenever you see * means Kleene closure so epsilon will enter And . When you see + send a and b sting differently not in series but parallel And where you see concat . Send the string in series

Upvotes: 0

henry434
henry434

Reputation: 107

5 years late but heres what I got:

Start at A. A is also an end state.

From A: Input 0 goes to B. B is an end state.
        Input 1 goes to C. C is an end state.

From B: Input 0 goes to B.
        Input 1 goes to C.

From C: Input 0 goes to B.
        Input 1 goes to C.

I'm pretty sure this is right (studying for an exam atm)...

It may be hard to visualise from that but if you draw a diagram from my instructions it should be more clear.

Hope this helps anyone looking this up.

Upvotes: 0

Ishaan
Ishaan

Reputation: 886

(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.

Upvotes: 1

Related Questions