1
$\begingroup$

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:

Diagram of Procedure

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

$\endgroup$
  • $\begingroup$ I've moved your answer from the question to an actual answer post. If you want to “take ownership” of it and possibly earn reputation from it, feel free to repost it, and flag my copy for removal. $\endgroup$ – Gilles 'SO- stop being evil' Dec 19 '13 at 15:37
2
$\begingroup$

[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. First Removal

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

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

  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. enter image description here

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

  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.

Final

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.