Cpt S 317 Homework #4
Please print your name!
1. Translate the following NFA M into a DFA M0
such that L(M0
) = L(M),
and provide a regular expression for L(M).
1
1
1
0
0
q0
q1
q2
2. A C-program is deterministic. But I can easily expand it to be a nondeterministic program. For instance, consider the following program:
Char c;
1. Read(c);
2. if c== ‘a’ or c== ‘b’ then
goto 1 or goto 3;
3. if c== ‘a’
goto 1;
4. if c != ’b’
Abort;
5. Halt.
Tell me the regular expression for all the input sequences of characters that
will make the program enter the last statement Halt.
1
