## Description

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