Question

Let M be defined as follows M = (K, Σ, s, ∆, F ) for K = {q0, q1, q2, q3, }, s = q0, Σ = {a, b, c}, F = {q0, q2, q3} and ∆ = {(q0, abc, q0), (q0, a, q1), (q0, e, q3), (q1, bc, q1), (q1, b, q2), (q2, a, q2), (q2, b, q3), (q3, a, q3)}.

1. (1pts) Draw the diagram of M

2. (6pts ) DRAW a diagram of an automata M0 such that M0 ≡ M and M0 and M0 is defined by the BOOK definition.

3. (3pts) List all components of M0 = (K 0 , Σ 0 , s 0 , ∆, 0 F 0 )

Answer 1

M = (K, Σ, s, ∆, F ) for

K = {q0, q1, q2, q3, } (Set of all states )

s = q0 (Starting state)

Σ = {a, b, c} (Set of inputs )

F = {q0, q2, q3} (Set of final states )

∆ = {(q0, abc, q0), (q0, a, q1), (q0, e, q3), (q1, bc, q1), (q1, b, q2), (q2, a, q2), (q2, b, q3), (q3, a, q3)}

(Transition function that a state on getting certain input goes to which state )

It is a NFA by seeing the transition function we can see that q1 on getting a goes to no where it implies it is NFA

1) So Diagram on the basis of above information is :->

2) Finding M0 (DFA) that is equivalent to M (NFA) as you have not provided what M0 is So i am considering it as DFA which will be equivalent to given NFA

Below Snaps shows you how to convert NFA to its euivalent DFA