This assignment constructs a regular expression that describes the language accepted by the DFA M over the alphabet {a, b} given by the diagram

a) Convert M to a GNFA M1 and give its diagram. Omit GNFA arcs labeled with .

b) Rip state 1 out of M1 to produce a reduced GNFA M2.

(sub a) Following the tabular pattern

as demonstrated in class, give the calculations showing how one obtains the labels for each transition in M2. Simplify the result expression by dropping factors from products and terms from sums, but do not reorder terms. Use only the symbols a, b, , and +, using + for union but not as a superscript. Use parentheses as necessary.

(sub b) Draw the transition diagram for M2 using the result labels just calculated.

c). Rip state 2 out of M2 to produce a reduced GNFA M3.

(sub a) Following the tabular pattern, give the calculations showing how one obtains the labels for each transition in M3.

(sub b) Draw the transition diagram for M3 using the result labels just calculated.

d). State the regular expression that describes the language accepted by M.

Qu QR QJ THRU QR DIRECT RESULT