(Non-)Deterministic Finite Automaton

These are conceptual constructs that can be used to validate any input. This is done by defining states and transitions. For every state there are follow up states defined when encountering a character from an Alphabet.

Notation

E= \{ Q, \Sigma , \delta, q_0, F \}

• Q: A non-empty set of states.
• \Sigma: The input Alphabet.
• \delta: A function that describes state transitions by taking in the current state and an input F: Q \times \Sigma \to Q.
• q_0: The starting state (q_0 \in Q).
• F: The set of valid end states (F \subseteq Q).

Non-Deterministic

A automaton is non-deterministic if there are none or multiple possible states for an input.

Method: Subset Construction

Subset construction converts an NFA to an equivalent DFA by treating sets of NFA states as single DFA states. The start state is ε-closure(q₀), and each transition from a DFA state S on symbol a leads to ε-closure(move(S, a)). This is repeated for every newly discovered state set until no new sets emerge, yielding a DFA whose states are subsets of the original NFA's state set.