Finite Automata
A finite automaton (FA) is the simplest computational model. It consists of a finite number of states, transitions between those states based on input symbols, a designated start state, and one or more accept (final) states. The name "finite" refers to the finite number of states — the machine has limited memory.
Think of a finite automaton as a very simple robot moving through rooms (states). Each room has doors (transitions) labeled with symbols. The robot starts in one specific room and moves through doors based on the input it reads. If the robot ends up in an accept room after reading the entire input, the string is accepted.
Formal Definition
A finite automaton is defined as a 5-tuple (Q, Σ, δ, q0, F), where:
Q is a finite set of states. Σ is the input alphabet. δ is the transition function (Q × Σ → Q for DFA, or Q × (Σ ∪ {ε}) → P(Q) for NFA). q0 is the start state (q0 ∈ Q). F is the set of accept states (F ⊆ Q).
Formal notation:
M = (Q, Σ, δ, q0, F)
Example — DFA accepting strings over {0,1} ending in "1":
Q = {q0, q1}
Σ = {0, 1}
q0 = q0 (start)
F = {q1}
δ:
δ(q0, 0) = q0
δ(q0, 1) = q1
δ(q1, 0) = q0
δ(q1, 1) = q1How It Works
The machine starts at q0. For each symbol in the input, it follows the corresponding transition. After consuming all input, if the machine is in an accept state, the string is accepted. Otherwise, it is rejected.
For example, processing the string "01" in the DFA above: start at q0, read 0 → stay at q0, read 1 → move to q1. Since q1 is an accept state, "01" is accepted. Processing "00": start at q0, read 0 → stay at q0, read 0 → stay at q0. Since q0 is not an accept state, "00" is rejected.
DFA vs NFA
There are two main types of finite automata. A Deterministic Finite Automaton (DFA) has exactly one transition for each symbol from each state. A Nondeterministic Finite Automaton (NFA) can have zero, one, or multiple transitions for a symbol, and can even include epsilon (ε) transitions that move without consuming input.
Despite the extra flexibility of NFAs, both DFA and NFA recognize exactly the same class of languages — the regular languages. Every NFA can be converted to an equivalent DFA, though the DFA may have more states.