The Regular Languages

Fix a finite, nonempty set of symbols $\Sigma$, called the alphabet — for example $\Sigma = \{0,1\}$. A string over $\Sigma$ is a finite sequence of symbols from $\Sigma$, including the empty string $\varepsilon$. Write $\Sigma^*$ for the set of all strings over $\Sigma$, finite or empty, of every possible length. A language is simply any subset $L \subseteq \Sigma^*$ — that is, a language is a rule (or set) that classifies strings as "in" or "out." Note that $\Sigma^*$ is always infinite (once $\Sigma$ is nonempty), so a language is generally an infinite object even though every individual string in it is finite. The class of regular languages is defined as follows: a language $L$ is regular if and only if there exists a finite automaton $M$ (deterministic or nondeterministic) such that $L = L(M)$, the set of strings $M$ accepts. This is a definition by existential recognition: $L$ doesn't need a closed formula or a recursive rule — it merely needs some finite-state machine, with some finite number of states, whose accept/reject behavior matches $L$ exactly, on every string of every length. Three equivalent characterizations exist, and recognizing their equivalence is the first deep theorem of the subject: 1. DFA-recognizable. Some deterministic finite automaton accepts exactly $L$. 2. NFA-recognizable. Some nondeterministic finite automaton (possibly with $\varepsilon$-transitions) accepts exactly $L$. 3. Regular-expression-describable. Some regular expression, built from symbols of $\Sigma$ using union $\cup$, concatenation, and Kleene star $*$, denotes exactly $L$. That these three definitions describe the same class of languages is not obvious from the definitions alone — it is a theorem (due, in essence, to Kleene, 1956), proved by explicit constructions converting each representation into the others. This article takes DFA-recognizability as the primary definition, since it is the one built directly on top of Deterministic Finite Automata, and treats NFA-equivalence as the first structural result about the class.

The mechanism for establishing "$L$ is regular" is always the same two-step pattern, whichever representation you use: 1. Exhibit a finite automaton — states, transitions, start state, accept states — with a fixed, finite description that does not depend on input length. 2. Argue (or prove) that the automaton's accept language equals $L$ — usually via an invariant on what each state "remembers" about the prefix read so far. The heart of the idea is that a DFA's memory is entirely captured by which state it is in, and the number of states is fixed before any input arrives. This forces every regular language to admit a finite summary: no matter how long a prefix is, there are only finitely many "states of knowledge" a DFA can be in about that prefix. Two prefixes that land the machine in the same state are permanently indistinguishable from then on — this idea, called the Myhill–Nerode perspective, foreshadows how one proves languages non-regular later. To make "regular" operational, here is the standard construction that converts a DFA into a regular expression (used to establish direction 1 ⇒ 3 above), via the state elimination method: ``` STATE-ELIMINATION(DFA M = (Q, Σ, δ, q0, F)):

# Convert M into a generalized NFA (GNFA): transitions labeled by

# regular expressions instead of single symbols, exactly one

# start state with no incoming edges, exactly one accept state

# with no outgoing edges, and every other pair of states

# connected by exactly one edge (label ∅ if no transition existed). add new start state s_start, edge s_start --ε--> q0 add new accept state s_accept for each f in F: add edge f --ε--> s_accept convert every δ-transition into a labeled edge (merge parallel edges with '∪') fill in missing edges with label ∅ while GNFA has more than 2 states (start and accept): pick any state q_rip other than s_start, s_accept for every pair (q_in, q_out) with q_in ≠ q_rip ≠ q_out: let R1 = label(q_in -> q_rip) let R2 = label(q_rip -> q_rip) # self-loop, maybe ∅ let R3 = label(q_rip -> q_out) let R4 = label(q_in -> q_out) # existing direct edge new_label = R4 ∪ (R1 (R2) R3) set label(q_in -> q_out) = new_label remove q_rip and all its edges return the single remaining label on edge s_start -> s_accept ``` Symmetrically, the standard construction for turning a regular expression into an NFA (Thompson's construction) builds the automaton by structural induction on the expression: base cases handle $\emptyset$, $\varepsilon$, and single symbols with tiny 1–2 state machines, and the inductive cases wire together the NFAs for subexpressions using $\varepsilon$-transitions to realize union, concatenation, and star. Combined with the standard subset construction that converts any NFA into an equivalent DFA (tracking sets* of NFA states as single DFA states), these three procedures form a triangle of conversions that proves DFAs, NFAs, and regular expressions all define the same class.

Membership testing. Given a DFA $M$ with $n$ states and an input string $w$ of length $m$, deciding whether $w \in L(M)$ takes $O(m)$ time and $O(1)$ extra space beyond the fixed automaton, since each symbol triggers exactly one transition lookup. This is the practical payoff of regularity: a single pass, constant memory algorithm, independent of $n$, decides membership.

NFA-to-DFA conversion (subset construction). An NFA with $n$ states converts to a DFA with at most $2^n$ states, since each DFA state corresponds to a subset of NFA states reachable on some string. This bound is tight in the worst case — there exist $n$-state NFAs whose minimal equivalent DFA genuinely requires $2^n$ states (a classic example: languages requiring the DFA to remember the symbol seen exactly $n$ positions back). So while NFAs and DFAs recognize the same class of languages, converting between them can cost exponential blowup in states — an important honesty point: equivalence of expressive power does not mean equivalence of succinctness.

Regex-to-NFA (Thompson's construction). For a regular expression of length $k$, this produces an NFA with $O(k)$ states and $O(k)$ transitions, since each of the $O(k)$ syntactic subexpressions contributes a constant number of new states. This is linear and efficient — the reason regex engines can compile patterns fast.

DFA-to-regex (state elimination). Each state removal can roughly square the length of edge labels, so the resulting regular expression can have length exponential in the number of DFA states in the worst case. This asymmetry — cheap to go regex → automaton, expensive to go automaton → regex — is why practical tools (compilers, regex engines) always compile expressions into automata rather than the reverse.

Correctness of the definition's coherence (why DFA = NFA = regex). The proof that these three formalisms define the same class rests on invariants preserved by each construction:

• Subset construction invariant: the DFA is in state $S \subseteq Q_{NFA}$ after reading prefix $x$ if and only if $S$ is exactly the set of NFA states reachable from the start state by reading $x$ (closing under $\varepsilon$-moves at each step). Proof by induction on $|x|$: true vacuously for $x = \varepsilon$ (just the $\varepsilon$-closure of the start state), and the inductive step follows directly from how the subset-DFA's transition function is defined (take the union of NFA-transitions from every state in $S$, then $\varepsilon$-close). Since acceptance is defined as $S \cap F_{NFA} \neq \emptyset$, the DFA accepts $x$ iff some accepting run of the NFA exists on $x$.
• Thompson's construction invariant: for each subexpression $R$, the constructed fragment has exactly one start and one accept state, and a string $w$ drives some path from start to accept in the fragment if and only if $w$ matches $R$. Proved by structural induction on the regular expression's syntax tree; each operator's gadget ($\cup$, concatenation, $*$) is checked to preserve the invariant using $\varepsilon$-transitions to compose fragments without altering their individual correctness.
• State elimination invariant: after removing a state, the regular expression labels on all remaining edges collectively still describe exactly the same string-to-string reachability relation as before removal — this holds because the new label $R_4 \cup (R_1 R_2^* R_3)$ exactly captures "go directly" ($R_4$) or "detour through the removed state, possibly looping on its self-edge zero or more times" ($R_1 R_2^* R_3$), which is precisely the set of paths that used to pass through $q_{rip}$.

Together these three invariant-based proofs form a complete cycle of reductions, establishing DFA-recognizable = NFA-recognizable = regex-describable as one single class: the regular languages.

A crucial honesty note. Not every language is regular. Languages requiring unbounded counting — like $\{0^n 1^n : n \geq 0\}$ — cannot be recognized by any finite automaton, because a DFA has only finitely many states and thus can only distinguish finitely many "counts so far" before it must reuse a state, collapsing information it needs later. This observation is the seed of the pumping lemma, which formalizes exactly why finite memory caps expressive power, and it is why the regular languages sit strictly inside the larger class of context-free languages in the Chomsky hierarchy.

Let $\Sigma = \{0, 1\}$ and let

Step 1 — build a DFA. We need to track "how close are we to having just seen `01`." Three states suffice:

• $q_0$: start state, haven't seen anything relevant yet (or last symbol seen was not part of a pending `0`).
• $q_1$: the most recent symbol read was a `0` and we have not yet seen `01`.
• $q_2$: we have already seen `01` somewhere — accept and stay forever.

Step 2 — trace an accepting string, $w = 1001$:

The machine enters $q_2$ the instant it sees the `0` at position 2 followed by the `1` at position 4, and correctly stays accepting for the remainder — matching the fact that $1001$ does contain `01` as a substring.

Step 3 — trace a rejecting string, $w = 1110$:

Final state $q_1$ is not accepting, correctly rejecting $1110$, which indeed never contains `01` (it's all 1's then a single 0).

Step 4 — convert to a regular expression via state elimination, to show the equivalence in action. Rewriting the transition table as edges and eliminating $q_1$ then $q_0$ (adding a start state $s$ and single accept state $a$ with $\varepsilon$-edges from $q_2$) yields, after simplification,

which reads exactly as "any prefix, then a `0` immediately followed by a `1`, then any suffix" — precisely the definition of $L$. This confirms, on a concrete example, that the DFA and the regex describe the same language, illustrating the general theorem from the previous section.

The theory of finite automata and regular languages emerged from the convergence of neuroscience modeling, switching-circuit theory, and mathematical logic in the mid-20th century.

Regular languages are not a museum piece — they are running in software right now. Lexical analyzers in every compiler (the "tokenizer" stage) use regular expressions compiled into DFAs to split source code into identifiers, numbers, and keywords in a single linear pass. Text search tools like `grep`, and the regex engines inside languages such as Python, JavaScript, and Java, compile patterns into automata (or automaton-like backtracking engines) for fast matching. Network intrusion detection systems and packet filters encode signature patterns as regular expressions matched against byte streams in real time, exploiting the $O(1)$-memory, $O(m)$-time guarantee. Hardware controllers — traffic light logic, vending machine logic, protocol handshake state machines (e.g., TCP's state diagram) — are literally finite automata, and the set of valid behavior sequences they permit is, by definition, a regular language. Even spell-checkers and DNA pattern matchers use finite-state techniques for approximate and exact substring search at scale. Understanding the regular languages precisely is the entry point to the entire hierarchy of computability, since every later class (context-free, decidable, recognizable) is defined by relaxing exactly the memory restriction that defines this one.

Ask the tutor: Can you show me why the subset construction never loses information when converting an NFA to a DFA?