Compilers - eNFA-to-DFA conversion and dead states

You are viewing an archived Text-only version of the thread. To view this thread in it's original format and/or if you want to reply to this thread please [click here]

Author

eNFA-to-DFA conversion and dead states

Paul J. Lucas

2004-08-16, 3:57 am

In "Introduction to Automata Theory, Languages, and
Computation," 2nd ed., section 2.5.5, "Eliminating
e-Transitions," it says in part on p. 78:

On + and -, q1 goes nowhere in Fig. 2.18, while
q0 goes to q1.

I was under the impression that all FSAs had transitions on
every symbol in their alphabets from every state. In the case
of Fig. 2.18, there are the implied/elided transitions from q1
on + and - to a dead state (as well as other elided transitions
from other states to the dead state).

Yet the quoted statement above "goes nowhere" makes it sound as
though transitions to the dead state are not to be considered
for eNFA-to-DFA conversion. Is this so?

- Paul

Sponsored Links