Definition

A finite automaton (FA) is an abstract machine with a finite number of states used to recognize strings belonging to a regular language — the mechanism that actually implements a regex in a lexer.

Key Points

• DFA (Deterministic Finite Automaton): exactly one transition per input symbol per state; no ambiguity — directly implementable in code (fast, but can have more states).
• NFA (Non-deterministic Finite Automaton): allows multiple/zero transitions on a symbol, and ε (epsilon) moves; smaller/easier to construct from a regex, but must be converted (subset construction) to a DFA for efficient recognition.
• Kleene's Theorem: proves the equivalence of three formalisms — regular expressions, finite automata (NFA/DFA), and regular grammars all describe exactly the class of regular languages. This equivalence is why a regex can always be mechanically converted into a DFA.
• Conversion pipeline used by real compilers: Regex → NFA (Thompson's construction) → DFA (subset construction) → Minimized DFA.

Example

DFA for (a|b)*abb (strings ending in "abb") is a classic construction question: 4 states, where state 4 is the only accepting state, reached only after seeing exactly a,b,b in sequence.

📌 CSS Frequency: High — DFA construction for a given regex is one of the most repeated numeric questions.

Model Answer (short)

"By Kleene's Theorem, regular expressions, finite automata, and regular grammars are equivalent in expressive power — any regular expression can be converted to an NFA (Thompson's construction), then to an equivalent DFA (subset construction). A DFA has unique transitions per symbol, making it directly usable by a lexical analyzer, while an NFA is easier to construct but not directly executable."