Redundant States During Removal of Null-Moves (Regular Expression to DFA)

Question

I've had this little doubt bothering me since four semesters now, so I've come here to resolve it. Theoretical CS was probably not the right place to ask.

Coming to the question, my old coursebook (Theory of Computer Science - Automata, Languages and Computation (Eastern Economy Edition) by KLP Mishra) details the conversion of the regular expression -:

$(0 + 1)^* (00 + 11)(0+1)^*$

to a finite automaton. The book details the process as follows:

I am able to grasp the process uptil step (d). I do not understand how (e) was obtained, and there is no explanation given. I tried to convert (d) to (e) by removing null-moves, but I am not able to get (e) - I obtain a bunch of redundant states (extra initial and final states).

It is not possible to use the DFA minimization procedure to obtain (e) after the null-moves are deleted, simply because this isn't a DFA yet - it's still an NFA. Note that I've not shown the NFA to DFA conversion procedure, which was on the next page. Could someone point me in the right direction?

There are no steps given to obtain (e) from (d). That's what's confusing - I know I have to remove the null-moves but not how to get the neat and 'minimized' transition system given by (e).

Answer 1

[answer by UncleDolan originally embedded in the question post]

I believe I just solved the problem on trying it again. The strategy was to remove the nulls in the right sequence, not follow a random sequence of null-deletion. Following that, I had to remove unreachable and redundant states.

First, I state the algorithm used to remove null-moves as given in my coursebook.

For two vertices A and B with a null link from A to B,

1. Duplicate all the edges which are going outside from B, from A.
2. If A is an initial state, make B an initial state.
3. If B is a final state, make A a final state.
4. Remove the null link.

Now I'll go step-wise through the solution. I generated the images using Graphviz on Ubuntu.

1. First, I removed the null link between q5 and q1. q0-q5 and q2-q6 are risky at this time because I would be inadvertently duplicating the null links from q5-q1 and q6-qf.

2. Second, I removed the null link between q6 and qf. qf now becomes unreachable.

3. Third, I removed the null link between q2 and q6. q6 evidently becomes redundant.

4. Fourth, I removed the last null link between q0 and q5. q0 becomes redundant as we now have two initial states, both having (almost) the same moves.

5. I remove q0, q1 and qf for being either unreachable or redundant. The end result looks very close to (e) in the question.

6. I find that q2 could do q6's job without making any changes to the language. q6 is redundant as well. This is the final result.