PPT Slide

Note that each DFA is (effectively) an NFA — just one where there is always exactly one possiblenext state. Hence every DFA-recognizable languageis NFA-recognizable.

Theorem 1.2.2: Each NFA-recognizable language is DFA-recognizable.

Previous slide

Next slide

Back to first slide

View graphic version