Prentice-Hall     Addision-Wesley

Copyright © 2007 Gradiance Corporation.

 

Gradiance Online Accelerated Learning

 

 

 

 

 

     

Nondeterministic Finite Automata

 

 

 

1.  

Here is a nondeterministic finite automaton:

http://www.gradiance.com/phmu/pictures/gradiance_nfa112205.gif

Convert this NFA to a DFA, using the "lazy" version of the subset construction described in Section 2.3.5 (p. 60), so only the accessible states are constructed. Which of the following sets of NFA states becomes a state of the DFA constructed in this manner?

 

 

 

 a) 

{A,B,C}

 

 b) 

The empty set

 

 c) 

{B}

 

 d) 

{B,D}

 

 

 

 

 

2.  

Convert the following nondeterministic finite automaton:

http://www.gradiance.com/phmu/pictures/ullman_nfa3.gif

to a DFA, including the dead state, if necessary. Which of the following sets of NFA states is not a state of the DFA that is accessible from the start state of the DFA?

 

 

 

 a) 

{A,B}

 

 b) 

{A,C}

 

 c) 

{A}

 

 d) 

{A,B,C}

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

3.  

The following nondeterministic finite automaton:

http://www.gradiance.com/phmu/pictures/ullman_nfa3.gif

accepts which of the following strings?

 

 

 

 a) 

1011101

 

 b) 

10001010

 

 c) 

00010111

 

 d) 

010111

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

4.  

Here is a nondeterministic finite automaton:

http://www.gradiance.com/phmu/pictures/gradiance_nfa112205.gif

Some input strings lead to more than one state. Find, in the list below, a string that leads from the start state A to three different states (possibly including A).

 

 

 

 a) 

00100

 

 b) 

0110

 

 c) 

100010

 

 d) 

1110