My Explanation On The Automata Assignment

Here is my homework for Automata Theory.
Pardon me for not being able to use MSPaint efficiently. ^^

As far as I can remember, the homework was to convert an NFA diagram to a DFA diagram.

Here's the NFA diagram:


Using subset construction, I am able to determine the states and state transitions.

δD({q0},a) = δN(q0,a) = {q1}

δD({q0},b) = δN(q0,b) = {q2}

δD({q1},a) = δN(q1,a) = {q3}

δD({q1},b) = δN(q1,b) = {}

δD({q2},a) = δN(q2,a) = {}

δD({q2},b) = δN(q2,b) = {q4}

δD({q3},a) = δN(q3,a) = {q3} U {q6} = {q3,q6}

δD({q3},b) = δN(q3,b) = {q3}

δD({q4},a) = δN(q4,a) = {q4} U {q6} = {q4,q6}

δD({q4},b) = δN(q4,b) = {q4}

δD({q3,q6},a) = δN(q3,a) ∪ δN(q6,a) = {q3,q6} ∪ {} = {q3,q6}

δD({q3,q6},b) = δN(q3,b) ∪ δN(q6,b) = {q3} ∪ {} = {q3}

δD({q4,q6},a) = δN(q4,a) ∪ δN(q6,a) = {q4,q6} ∪ {} = {q4,q6}

δD({q4,q6},b) = δN(q4,b) ∪ δN(q6,b) = {q4} ∪ {} = {q4}

δD({},a) = {}, δD({},b) = {}

From the subsets above we can produce this DFA:


However, we can still simplify the DFA (above). I'm not sure about the rules in simplifying DFAs yet, so I hope this will suffice for now:


Please leave your comments if I'm wrong or if I had broken some rules.

0 comments: