• California State University, San Marcos

• CS 421

CS421 - Krell - HW 2C (based week 5-6) RE to DFA Automatic Process

=====================================================================

DUE: Week 7 Friday before midnight (11:55)

TOTAL: 30 pts

** Name: *Alfredo Juarez*

Use my EC demo programs to verify your answers!!!

-------------------------------------------------------------------------------------

Problem 1: RE -> NFA-e (From week5a) [2pts per machine = 12 pts]

------------------------------------------------------------------------------------

Give NFA-e for the following REs.

Show component machines first

and then show all steps of connecting these machines using the methods

described in week6a notes.

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 for components.

· M1 for b:

· M2 for a:

· M3 for bb by connecting M1’s with an arrow :

Start combining them now (show all states).

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

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