• \( Q_N \): Set of NFA states.

• \( \Sigma \): Input alphabet.

• \( \delta_N \): Transition function \( \delta_N: Q_N \times \Sigma \rightarrow 2^{Q_N} \).

• \( q_{0N} \): Initial state.

• \( F_N \): Set of accepting (final) states.

• \( Q_D \): Set of DFA states (each state is a subset of \( Q_N \)).

• \( \delta_D \): Transition function \( \delta_D: Q_D \times \Sigma \rightarrow Q_D \).

• \( q_{0D} \): Initial state (subset of \( Q_N \)).

• \( F_D \): Set of accepting states.

1. Initialize the DFA
• Initial State: Start with the initial state \( q_{0D} \) of the DFA, which is the epsilon-closure of the NFA's initial state \( q_{0N} \): \[ q_{0D} = \epsilon\text{-closure}(\{q_{0N}\}) \]
• Epsilon-Closure: The epsilon-closure of a set of states \( S \) is the set of states reachable from any state in \( S \) via epsilon (empty string) transitions, including \( S \) itself.

2. Construct the DFA States and Transitions
• Worklist Algorithm: Use a queue or stack to keep track of unprocessed DFA states.
• Initialize: Add \( q_{0D} \) to the worklist and \( Q_D \).
• Process States:
• While the worklist is not empty:
• Remove a state \( T \) from the worklist.
• For each input symbol \( a \in \Sigma \):
• Compute the set of NFA states \( U \) reachable from \( T \) on input \( a \): \[ U = \epsilon\text{-closure}\left( \bigcup_{q \in T} \delta_N(q, a) \right) \]
• Add New State:
• If \( U \) is not already in \( Q_D \):
• Add \( U \) to \( Q_D \).
• Add \( U \) to the worklist.
• Define Transition:
• Set \( \delta_D(T, a) = U \).

3. Define Accepting States
• Accepting States: A DFA state \( T \) is accepting if it contains at least one accepting state of the NFA: \[ F_D = \{ T \in Q_D \mid T \cap F_N \neq \emptyset \} \]

1. Number of DFA States
• Theoretical Upper Bound: The number of possible subsets of \( Q_N \) is \( 2^n \). Therefore, \( |Q_D| \leq 2^n \).
• Practical Observation: Not all subsets are reachable from the initial state, so the actual number of DFA states may be less.

2. Processing Each DFA State
• For each DFA state \( T \) and input symbol \( a \), we compute the set \( U \) as described.
• Computational Steps:
• Transition Retrieval:
• For each state \( q \in T \), retrieve \( \delta_N(q, a) \).
• Set Union:
• Combine the resulting sets for all \( q \in T \).
• Epsilon-Closure:
• Compute the epsilon-closure of the combined set.
• Time per Transition:
• Retrieving transitions: \( O(n) \) (since \( |T| \leq n \)).
• Epsilon-closure computation: \( O(n^2) \) in the worst case (if the NFA has epsilon transitions forming a connected graph).
• Total per transition: \( O(n^2) \).

3. Total Time Complexity
• Total Number of Transitions:
• Up to \( |Q_D| \times m \).
• In the worst case: \( 2^n \times m \).
• Total Computation Time:
• Time per transition \( \times \) total number of transitions.
• \( O(2^n \times m \times n^2) \).
• Simplified Complexity:
• \( O(m n^2 2^n) \).

4. Space Complexity
• DFA States Storage:
• Up to \( 2^n \) states, each storing a subset of \( Q_N \).
• Transition Table:
• Up to \( 2^n \times m \) transitions.
• Total Space:
• \( O(2^n \times n) \) (for states) \( + \) \( O(2^n \times m) \) (for transitions).
• Combined: \( O(2^n (n + m)) \).

• Time Complexity: Exponential in the number of NFA states (\( O(2^n) \)).

• Space Complexity: Exponential in the number of NFA states (\( O(2^n) \)).

1. Initialization:
• Start with the epsilon-closure of the NFA's initial state.
• Initialize the DFA states and worklist.

2. State Processing Loop:
• For each DFA state and input symbol:
• Compute the move and epsilon-closure to find the new DFA state.
• Add new DFA states to the worklist.

3. Defining Accepting States:
• Any DFA state containing an NFA accepting state becomes an accepting state.

4. Time Complexity:
• Exponential due to the potential \( 2^n \) number of DFA states.

• Optimizations:
• In practice, many of the possible subsets are unreachable, so the actual number of DFA states may be much less than \( 2^n \).
• Techniques like memoization and state minimization can help reduce the number of states and transitions.

• Applications:
• Essential in lexical analysis, where regular expressions are converted to NFAs and then to DFAs for efficient pattern matching.

• Limitations:
• For NFAs with a large number of states, the subset construction may become computationally infeasible due to resource constraints.

• Automata Theory: The study of abstract machines and problems they can solve.

• Powerset Construction: Method of converting NFAs to DFAs by representing each DFA state as a set of NFA states.

2023小测

2021年小测

2020年小测

2017年小测1

2017年小测2