Theory of Computing

Remove e-moves from the following:

e q2 --- a --- q3 --------------- e -------------------

q0- e - q1 q8 - e ((q9))

e q4 --- b ---- q5 --- e --- q6 ---- b ---- q7 - e -----

i.e.

Trs(q0,e) = q1

Trs(q1,e) = q2

Trs(q1,e) = q4

Trs(q2,a) = q3

Trs(q3,e) = q8

Trs(q4,b) = q5

Trs(q5,e) = q6

Trs(q6,b) = q7

Trs(q7,e) = q8

Trs(q8,e) = q9 final

1) Please compute Trs-e for each state-symbol pair: [8pts]

Trs-e(q0,e*ae*) = { }

Trs-e(q0,e*be*) = { }

Trs-e(q1,e*ae*) = { }

Trs-e(q1,e*be*) = { }

Trs-e(q2,e*ae*) = { }

Trs-e(q2,e*be*) = { }

etc. Continue for all state-symbol pairs.

2) Then draw the NFA based on the above (hand-drawing is OK but insert here):[4pts]