write a program in C++ that converts any NFA-e into an NFA.

Read the instructions in the corresponding directory to set up the input file.

Run my sample solution to determine the output file format.

For every NFA with e-moves, there is a corresponding NFA without e-moves.

Let's show a systematic way to converting NFA-e into NFA.

The idea is to create a "solid" arrow for each path involving e-moves.

M1 is with e-moves (final states are in F1)

M2 is without e-moves (final states are in F2)

We are converting M1 into M2. Make sure you have the e-CLOSURE(q) for every state in M1.

1. Every final state of F1 will still be a final state in F2

2. If q0 => e* => final state of F1,

q0 will also be a final state in F2.

i.e. e-CLOSURE(q0) is a final state of F1, so make q0 a final state in F2.

3. For M1's

For each state-char (q-a) pair, compute Trs(q, e* a e*)

and create arrows in M2 to those states, labeled with a.

e.g. Trs(q0, e* a e*)={q2, q3} so create arrows from q0 to q2 and q0 to q3

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

Example: removing e-moves

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

Given: M1 q0 loop on 0 ------> q1 loop on 1 -----> q2 loop on 2 q2 is final

Final states: F1 has q2 thus,

F2 has q2 and

q0 since e-CLOSURE(q0) contains q2

Go through every state-symbol pair of M1:

M1 - q0 on e* 0 e* -> {q0 q1 q2}

Thus M2: q0 on 0 -> q0 and q1 and q2 (3 arrows)

M1 - q0 on e* 1 e* -> {q1 q2}

Thus M2: q0 on 1-> q1 and q2 (2 arrows)

M1 - q0 on e* 2 e* -> {q2}

Thus M2: q0 on 2 -> q2

M1 - q1 on e* 0 e* is not possible

M1 - q1 on e*1e* -> {q1 q2}

Thus M2: q1 on 1-> q1 and q2 (2 arrows)

M1 - q1 on e*2e* -> {q2}

Thus M2: q1 on 2 -> q2

M1 - q2 on e* 0 e* is not possible

M1 - q2 on e* 1 e* is not possible

M1 - q2 on e*2e* -> {q2}

Thus, M2: q2 on 2-> q2