eNFA-to-DFA conversion and dead states

pauljlucas@mac.com (Paul J. Lucas)
15 Aug 2004 22:22:15 -0400

          From comp.compilers

Related articles
eNFA-to-DFA conversion and dead states pauljlucas@mac.com (2004-08-15)
| List of all articles for this month |

From: pauljlucas@mac.com (Paul J. Lucas)
Newsgroups: comp.compilers
Date: 15 Aug 2004 22:22:15 -0400
Organization: SBC http://yahoo.sbc.com
Keywords: theory, question
Posted-Date: 15 Aug 2004 22:22:15 EDT

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

Post a followup to this message

Return to the comp.compilers page.
Search the comp.compilers archives again.