CODEWITHSUNDEEP
dfanfaautomaton
ArdianH101
ArdianH101

Reputation: 55

Is this transformation from a NFA to a DFA correct?

I am studying for an exam and came up to this task in the picture

usually the transformation from a NFA to a DFA is easy to me. I create a transition table from the NFA and for every "new" combined state, i create a new column and so on (looking at my try explains it better)

enter image description here

enter image description here

Somehow I am skeptical with the single state of q3. Since no state can reach single q3, does this even make sense?

Upvotes: 3

Views: 278

Answers (1)

Patrick87
Patrick87

Reputation: 28312

Your DFA is correct. It contains an unnecessary and unreachable state q3, but this is perfectly fine; not all states need to be reachable. Unreachable states would be removed during minimization, but the subset construction does not attempt to guarantee that the resulting DFA will be minimal.

The way I run the subset construction, I only include states corresponding to subsets that can be reached; but it would not be incorrect to simply include all possible subsets. It's just a stylistic choice, and even my method does not yield minimal DFAs, only ones without unreachable states.

Upvotes: 1

Related Questions