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:
Post a Comment