Skip to main content
added comment
Source Link
Hendrik Jan
  • 31.1k
  • 1
  • 54
  • 108

The answer to the question depends on its precise meaning.

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states?

Yes, when applying the standard construction for DFA constrution the new automaton obtains a state set $2^Q$, the power set of $Q$, containing all subsets of original state set $Q$. This construction will always obtainyield a deterministic automaton of that size even when the original automaton is deterministic.

or if some sub-sets are unreachable then they are not included in it?

That touches on the difference between the "formal" construction and the more "practical implementation" that is usually taken. In the latter version we only take the states that are reached during construction. Technically, we just determine the connected component that includes the initial state (where we start the construction).

NFA to DFA construction

In the figure we see a NFA (with three states) and the DFA using the standard subset construction with eight states (formal interpretation) or four states (omitting the gray states not reached). (PS. I forgot to mark the final states in the gray part)

The answer to the question depends on its precise meaning.

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states?

Yes, when applying the standard construction for DFA constrution the new automaton obtains a state set $2^Q$, the power set of $Q$, containing all subsets of original state set $Q$. This construction will always obtain a deterministic automaton even when the original automaton is deterministic.

or if some sub-sets are unreachable then they are not included in it?

That touches on the difference between the "formal" construction and the more "practical implementation" that is usually taken. In the latter version we only take the states that are reached during construction. Technically, we just determine the connected component that includes the initial state (where we start the construction).

NFA to DFA construction

In the figure we see a NFA (with three states) and the DFA using the standard subset construction with eight states (formal interpretation) or four states (omitting the gray states not reached).

The answer to the question depends on its precise meaning.

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states?

Yes, when applying the standard construction for DFA constrution the new automaton obtains a state set $2^Q$, the power set of $Q$, containing all subsets of original state set $Q$. This construction will always yield a deterministic automaton of that size even when the original automaton is deterministic.

or if some sub-sets are unreachable then they are not included in it?

That touches on the difference between the "formal" construction and the more "practical implementation" that is usually taken. In the latter version we only take the states that are reached during construction. Technically, we just determine the connected component that includes the initial state (where we start the construction).

NFA to DFA construction

In the figure we see a NFA (with three states) and the DFA using the standard subset construction with eight states (formal interpretation) or four states (omitting the gray states not reached). (PS. I forgot to mark the final states in the gray part)

Source Link
Hendrik Jan
  • 31.1k
  • 1
  • 54
  • 108

The answer to the question depends on its precise meaning.

when converting an NFA to DFA, we create sub-sets of states in the NFA. does it mean that every DFA-converted-from-NFA contain 2^Q states?

Yes, when applying the standard construction for DFA constrution the new automaton obtains a state set $2^Q$, the power set of $Q$, containing all subsets of original state set $Q$. This construction will always obtain a deterministic automaton even when the original automaton is deterministic.

or if some sub-sets are unreachable then they are not included in it?

That touches on the difference between the "formal" construction and the more "practical implementation" that is usually taken. In the latter version we only take the states that are reached during construction. Technically, we just determine the connected component that includes the initial state (where we start the construction).

NFA to DFA construction

In the figure we see a NFA (with three states) and the DFA using the standard subset construction with eight states (formal interpretation) or four states (omitting the gray states not reached).