Theory of Computing

Give NFA-e for the following REs.

Show component machines first and then show all steps of connecting these machines.

Hand-drawing is OK (just insert into this file). [2pts per machine]

Do not use any simplification. Having many e-moves is what we want.

The following is for b(a|bb)^*

No state numbers are needed.

M1 for b:

M2 for a:

M3 for bb by connecting M1s:

Start combining them now (show all states).

M4 for (a|bb) combining M2 and M3:

M5 for (a|bb)^* modifying M4:

The whole thing for b(a|bb)^*:

HINT: Put M1 in front of M5 and then give state numbers

(make sure state numbers are unique)