Regular expression [ 1 ( 0 1* 0)* 1 ]* DFA

The * at the end can be taken to mean the initial state is accepting and that the automaton returns to this state whenever it accepts anything. Call the initial state q1.

To accept 1(01*0)1 we must first consume a 1 and go to a new state, say q2. From there, we can self-loop on the subexpression 01*0 by going to a new state, q3, on 0, then looping on 1 in q3, then returning to q2 on 0.

From q2, we can return to q0 on 1. Our DFA looks like:

     /--1--\  /--0--\
     |      \ |     |
     V      | V     |
--->(q1)-1->(q2)-0->(q3)-\
     |               ^    \
     0               "https://stackoverflow.com/"               \-1-/
     V
    (q4)-\
     ^    \
     |    /
     \0,1/

Something like that ought to do it.

Browse More Popular Posts

Leave a Comment