Regular Languages | Computer Science

flowchart TD
    A[2_Regular Languages] --> B[Key Concepts]
    A --> C[Core Principles]
    A --> D[Practical Applications]
    B --> E[Fundamental definitions]
    C --> F[Design patterns]
    D --> G[Real-world usage]

Regular languages are the simplest class in the Chomsky hierarchy — they describe patterns that can be matched with a finite amount of memory (the states of a finite automaton). Think of a vending machine: it has a fixed number of states, transitions on inputs (coins), and accepts or rejects based on the sequence. It can’t count arbitrary amounts or remember unbounded history.

DFA vs NFA intuition: A DFA is deterministic — given a state and input, there’s exactly one next state. An NFA can “guess” which transition to take, exploring multiple possibilities simultaneously. NFAs are easier to design (you don’t need to track every detail) but DFAs are easier to execute (no guessing needed). The subset construction shows they’re equivalent in power.

Regular expressions intuition: Regex describe the same languages as finite automata. Each regex operator maps directly to an NFA construction: union becomes a choice (fork), concatenation becomes a sequence, and Kleene star becomes a loop. This is why regex are so useful in practice — they’re compact descriptions of regular languages.

A deterministic finite automaton (DFA) is a 5-tuple $M = (Q, \Sigma, \delta, q_0, F)$ where:

• $Q$ is a finite set of states.
• $\Sigma$ is the input alphabet.
• $\delta : Q \times \Sigma \to Q$ is the transition function.
• $q_0 \in Q$ is the start state.
• $F \subseteq Q$ is the set of accepting (final) states.

$M$ accepts a string $w = w_1 w_2 \cdots w_n$ if the sequence of states $q_0, \delta(q_0, w_1), \delta(\delta(q_0, w_1), w_2), \ldots$ ends in a state in $F$.

Example. DFA for strings over $\{0, 1\}$ containing the substring 01:

$M = (\{q_0, q_1, q_2\}, \{0, 1\}, \delta, q_0, \{q_2\})$

A nondeterministic finite automaton (NFA) allows multiple transitions from a state on the same Symbol, and $\varepsilon$-transitions (transitions without consuming input). Formally, $\delta : Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$.

$M$ accepts $w$ if there exists some path of transitions consuming $w$ that ends in a state in $F$.

Theorem 2.1. For every NFA $N$There exists a DFA $D$ such that $L(N) = L(D)$.

Proof (subset construction). Given NFA $N = (Q, \Sigma, \delta, q_0, F)$Construct DFA $D = (Q", \Sigma, \delta', q_0', F')$ where:

• $Q' = \mathcal{P}(Q)$ (each state of $D$ is a subset of states of $N$).
• $q_0' = \varepsilon\mathrm{-closure(\{q_0\})}$.
• $\delta'(S, a) = \varepsilon\mathrm{-closure(\bigcup_{q \in S} \delta(q, a))}$ for $S \subseteq Q$ $a \in \Sigma$.
• $F' = \{S \subseteq Q : S \cap F \neq \emptyset\}$.

Every string accepted by $N$ has some path through $N$‘s states. The subset construction tracks all Possible states $N$ could be in after reading each symbol. $D$ accepts exactly when at least one Possibility in $N$ leads to acceptance. $\blacksquare$

Corollary 2.2. NFA, DFA, and NFA with $\varepsilon$-transitions all recognise exactly the class of Regular languages.

Definition. Regular expressions over $\Sigma$ are defined inductively:

1. $\emptyset$ (empty set), $\varepsilon$ (empty string), and $a$ for each $a \in \Sigma$ are regex.
2. If $R_1$ and $R_2$ are regex, then $(R_1 \cup R_2)$, $(R_1 \cdot R_2)$ And $(R_1^*)$ are regex.
3. Nothing else is a regex.

Shorthand: $R^+$ means $R \cdot R^*$. $R?$ means $(R \cup \varepsilon)$.

Examples:

• $(0 \cup 1)^* 00 (0 \cup 1)^*$: strings containing 00.
• $1^* 01^* 01^*$: strings with exactly two 0S.
• $(0 \cup 1)^*$: all strings over $\{0, 1\}$.
• $\emptyset$: the empty language.

Regex identities. The following algebraic laws hold for regular expressions and can be used To simplify or reason about them:

These identities can be used to prove that two regex describe the same language, analogous to Simplifying algebraic expressions. Two regex $R_1$ and $R_2$ are equivalent (written $R_1 \equiv R_2$) If $L(R_1) = L(R_2)$.

Theorem 2.3 (Kleene). A language is regular if and only if it is described by some regular Expression.

Proof (sketch).

Regex to NFA: Induction on the structure of the regex.

• Base cases: $\emptyset$, $\varepsilon$, $a$ each have trivial NFAs.
• Union: Combine two NFAs with a new start state and $\varepsilon$-transitions to each.
• Concatenation: Connect the accept states of the first NFA to the start state of the second via $\varepsilon$-transitions.
• Kleene star: Add $\varepsilon$-transitions from a new start state to the NFA’s start and from the NFA’s accept states back to the start state.

NFA to regex: State elimination. Systematically eliminate states of the NFA one at a time, Updating the transition labels (which are regex) between remaining states. The final label from start To accept is the equivalent regex. $\blacksquare$

Thompson’s construction. The regex-to-NFA translation can be made fully explicit. For each Sub-expression of the regex, we build a small NFA fragment with exactly one entry and one exit State, connected by $\varepsilon$-transitions. The construction guarantees that the NFA has at most One accept state, no transitions into the start state, and no transitions out of the accept state.

Theorem 2.3a (Thompson’s construction correctness). For every regular expression $R$ over $\Sigma$Thompson’s construction produces an NFA $N_R$ with $L(N_R) = L(R)$ And $N_R$ has $O(|R|)$ States and transitions.

Proof. By structural induction on $R$.

• Base cases:

• $R = \emptyset$: $N_R$ has a start state and an accept state with no transitions. $L(N_R) = \emptyset = L(\emptyset)$.

• $R = \varepsilon$: $N_R$ has a start state, an accept state, and an $\varepsilon$-transition between them. $L(N_R) = \{\varepsilon\} = L(\varepsilon)$.

• $R = a$ for $a \in \Sigma$: $N_R$ has a start state, an accept state, and a transition on $a$. $L(N_R) = \{a\} = L(a)$.

• Inductive cases:

• $R = R_1 \cup R_2$: By IH, $L(N_{R_1}) = L(R_1)$ and $L(N_{R_2}) = L(R_2)$. Thompson adds a new start $s$ and accept $f$ with $\varepsilon$-transitions to the start states of $N_{R_1}$ and $N_{R_2}$ And $\varepsilon$-transitions from their accept states to $f$. Any accepting path goes through exactly one sub-NFA, so $L(N_R) = L(R_1) \cup L(R_2) = L(R)$.

• $R = R_1 \cdot R_2$: Thompson connects the accept state of $N_{R_1}$ to the start state of $N_{R_2}$ via $\varepsilon$-transitions. A string $w \in L(N_R)$ iff $w = w_1 w_2$ where $w_1 \in L(N_{R_1})$ and $w_2 \in L(N_{R_2})$I.e., $w \in L(R_1) \cdot L(R_2) = L(R)$.

• $R = R_1^*$: Thompson adds a new start $s$ and accept $f$With $\varepsilon$-transitions from $s$ to $f$ (allowing zero repetitions) and from $s$ to the start of $N_{R_1}$ And from the accept of $N_{R_1}$ back to $s$. Any accepting path corresponds to zero or more traversals of $N_{R_1}$ So $L(N_R) = L(R_1)^* = L(R)$.

In all cases, the number of states added is a constant per operator, so $|N_R| = O(|R|)$. $\blacksquare$

Theorem 2.4 (Myhill-Nerode). The following are equivalent for a language $L$:

1. $L$ is regular.
2. The Myhill-Nerode equivalence relation has finitely many equivalence classes.
3. $L$ is the union of some of the equivalence classes.

Definition. Two strings $x, y$ are distinguishable with respect to $L$ if there exists $z$ Such that exactly one of $xz, yz$ is in $L$. The Myhill-Nerode equivalence $\equiv_L$ is: $x \equiv_L y$ iff $x$ and $y$ are not distinguishable.

Proof of Theorem 2.4.

(1) $\Rightarrow$ (2): Let $D = (Q, \Sigma, \delta, q_0, F)$ be a DFA for $L$. Define $x \sim y$ iff $\delta^*(q_0, x) = \delta^*(q_0, y)$ (i.e., $D$ reaches the same state on $x$ and $y$). Then $\sim$ has at most $|Q|$ equivalence classes. We show $\sim = \equiv_L$. If $x \sim y$ Then for All $z$, $\delta^*(q_0, xz) = \delta^*(q_0, yz)$ So $xz \in L$ iff $yz \in L$Meaning $x \equiv_L y$. Conversely, if $x \not\equiv_L y$There exists $z$ with $xz \in L$ and $yz \notin L$ (or vice versa), so $\delta^*(q_0, xz) \neq \delta^*(q_0, yz)$Hence $x \not\sim y$.

(2) $\Rightarrow$ (3): Trivial, since $L$ consists of all strings whose equivalence class is one That contains at least one string in $L$.

(3) $\Rightarrow$ (1): Suppose $\equiv_L$ has finitely many equivalence classes $C_1, \ldots, C_k$. Construct a DFA with one state per equivalence class, start state $[x]_{\equiv_L}$ for $x = \varepsilon$ Transition $\delta'([x], a) = [xa]$ And accept states = those classes contained in $L$. This DFA is Well-defined because $\equiv_L$ is a right congruence: if $x \equiv_L y$ Then $xa \equiv_L ya$ for all $a \in \Sigma$. $\blacksquare$

Corollary 2.5. The minimum-state DFA for $L$ has exactly as many states as there are Equivalence classes of $\equiv_L$.

Minimisation algorithm:

1. Start with two partitions: F (accepting states) and Q \ F (non-accepting).
2. Repeatedly refine: for each pair (p, q) in the same partition,
   if delta(p, a) and delta(q, a) are in different partitions for some a,
   split p and q into different partitions.
3. Repeat until no further splitting occurs.
4. Each partition becomes a state in the minimised DFA.

This algorithm runs in $O(n^2 k)$ time where $n$ is the number of states and $k = |\Sigma|$.

Theorem 2.6 (Pumping Lemma). If $L$ is regular, then there exists a constant $p$ (the pumping Length) such that for every string $w \in L$ with $|w| \geq p$, $w$ can be decomposed as $w = xyz$ satisfying:

1. $|y| \gt 0$ (the pumped part is non-empty).
2. $|xy| \leq p$ (the pumpable part is within the first $p$ symbols).
3. $xy^iz \in L$ for all $i \geq 0$.

Proof. Let $D$ be a DFA for $L$ with $n$ states. Set $p = n$. For any string $w$ of length $\geq n$ The path through $D$ visits at least $n + 1$ states, so by the pigeonhole principle, some state is Visited twice within the first $p$ symbols. The substring $y$ between the two visits can be repeated Or removed ($xy^iz$) without affecting acceptance. $\blacksquare$

Using the pumping lemma to prove non-regularity. To show $L$ is not regular, assume it is, let $p$ Be the pumping length, and exhibit a string $w \in L$ with $|w| \geq p$ such that every Decomposition $w = xyz$ satisfying (1) and (2) has some $i$ with $xy^iz \notin L$.

Example. $L = \{0^n 1^n : n \geq 0\}$ is not regular.

Proof. Assume $L$ is regular with pumping length $p$. Let $w = 0^p 1^p \in L$. By (2), $|xy| \leq p$ So $y$ consists only of 0S. Let $|y| = k \gt 0$. Then $xy^0 z = 0^{p-k} 1^p \notin L$ (since $p - k \neq p$). Contradiction. $\blacksquare$

Example. $L = \{ww : w \in \{0,1\}^*\}$ is not regular.

Proof. Assume pumping length $p$. Let $w = 0^p 1 0^p 1 \in L$. Since $|xy| \leq p$, $y = 0^k$ for Some $k \gt 0$. Then $xy^0 z = 0^{p-k} 1 0^p 1 \notin L$ (the two halves have different lengths). $\blacksquare$

Example. $L = \{0^n 1^m : n \neq m\}$ is not regular.

Proof. Assume $L$ is regular with pumping length $p$. Since regular languages are closed under Complement, $\overline{L} = \{0^n 1^m : n = m\} \cup \{w : w \notin 0^* 1^*\}$ would also be regular. Then $\overline{L} \cap 0^* 1^* = \{0^n 1^n : n \geq 0\}$ would be regular (since $0^* 1^*$ is regular And regular languages are closed under intersection). But $\{0^n 1^n : n \geq 0\}$ is not regular — Contradiction. $\blacksquare$

• Context-Free Languages — Regular languages are a subset of context-free languages, forming the simplest level of the Chomsky hierarchy.

• Turing Machines — Finite automata that recognise regular languages are the simplest computational model in the hierarchy.

• Propositional Logic — Boolean algebra underpins both propositional logic and the transition functions of finite automata.

• Discrete Mathematics

• Algorithm Implementation

1. Confusing NFAs with DFAs in terms of expressive power. NFAs and DFAs recognise exactly the same class of languages (regular languages). An NFA is not “more powerful” — it is directly more convenient to construct. The subset construction converts any NFA to an equivalent DFA, though potentially with exponentially many states.

2. Misapplying the pumping lemma by pumping to zero. The pumping lemma states $|xy| \leq p$ and $|y| \geq 1$, so $y$ cannot be empty. Students often pump $y$ to zero characters, which is invalid. The lemma guarantees a non-empty substring can be pumped, not that any substring can be removed.

3. Assuming closure under intersection implies closure under complement. Regular languages are closed under both intersection and complement independently. However, context-free languages are closed under neither complement nor intersection as a rule. Knowing one closure property does not automatically give you the others.

4. Forgetting that regular expressions and finite automata are equivalent. Regular expressions, DFAs, NFAs, and regular grammars all describe exactly the regular languages. A common mistake is assuming regular expressions are “weaker” because they lack features like backreferences, which actually push beyond regular languages into context-free territory.

5. Confusing the language of a DFA with its state graph. A DFA accepts a language — a set of strings. The state graph is a representation, not the language itself. Two different DFA state graphs can accept the same language. When proving properties, reason about the language, not the specific graph structure.