Question

Let M be defined as follows: M = ({q0, q1, q2, q3}, Σ = {a, b}, ∆, s = q0, F = {q2}) and ∆ = {(q0, a, q1), (q1, b, q0), (q1, b, q2), (q2, a, q0)}

1. (2pts) Draw the diagram of M

2. (13pts) Evaluate all relevant steps of the general method of transformation the NDFA M defined above into an equivalent DFA M0 . Do it in the following STAGES. STAGE 1 (3pts) For all q ∈ K, evaluate E(q) and evaluate the initial state s 0 and some final states STAGE 2 (10pts) Evaluate δ 0 (Q, σ) only for relevant Q ∈ 2 K , i.e. follow the steps below Step 1: Evaluate δ 0 (s 0 , σ) for all σ ∈ Σ, i.e. all states directly reachable from s 0 . Step (n+1): Evaluate δ 0 on all states that result from the Step n, i.e. on all states already reachable from s 0 . The process terminates when all δ 0 (Q, σ) has been found for all relevant Q ∈ 2 K . REMINDER: E(q) = {p ∈ K : (q, e) ∗,M 7−→ (p, e)} and δ(Q, σ) = S {E(p) : ∃q ∈ Q, (q, σ, p) ∈ ∆}. 8

3. (3pts) DRAW the final DIAGRAM of the Relevant Part of M

Answer 1

Note: Plzzz don' t give dislike.....Plzzz comment if u have any problem i will try to resolve it.......