Finite State Automata for (0+11+01)*(0)*(01)*

Question

This is my homework problem and I am struggling hard for it. Can anyone please help me out? I need to find out finite state automata for (0+11+01) * (0) * (01)*. Also, if anyone can please tell me the general principle for designing of finite state automata easily.

Answer 1

First you should be able to convert the regular expression into a graph like this:

Then processing an input corresponds to following a path along this graph, so after each input character we "are" at one of the red dots. However, we may sometimes be at several red dots at the same time because it is usually not clear which path is the "right" one until later in the input. Thus a state really corresponds to a set of red dots (instead of a single dot).

For example, the initial state is "the three top red dots". From this state we land in "the second red dot on the left" if the input is "1", weheras we land in "the three top dots and the third on the left and the second on the right" if the input is "0". All in all this example gives us up to 64 states from the six red dots (where the empty state means as much as "irreparably inacceptable" and is reached for example for input startiung "10"). The accepting states are precisely those containing the top-right dot.