Regular Languages

Definition

A language $L \subseteq \Sigma^*$ is regular if it is recognized by:

• A DFA, or equivalently
• An NFA, or equivalently
• A regular expression

Closure Properties

Regular languages are closed under these operations:

Boolean Operations

Operation	If $L_1, L_2$ regular	Result
Union	$L_1 \cup L_2$	Regular
Intersection	$L_1 \cap L_2$	Regular
Complement	$\overline{L}$	Regular
Difference	$L_1 - L_2$	Regular

Construction Methods

Union: NFA with $\epsilon$-transitions to both machines.

Intersection: Product construction DFA. $\delta_{A \times B}((p, q), a) = (\delta_A(p, a), \delta_B(q, a))$ Accept if both components accept.

Complement: Swap accept and non-accept states in DFA. (Must be complete DFA — every state has transitions for all symbols.)

String Operations

Operation	Result
Concatenation $L_1 L_2$	Regular
Kleene star $L^*$	Regular
Reversal $L^R$	Regular
Homomorphism $h(L)$	Regular
Inverse homomorphism $h^{-1}(L)$	Regular

Pumping Lemma

Statement

If $L$ is regular, then there exists $p \geq 1$ (pumping length) such that:

For any string $w \in L$ with $|w| \geq p$, we can write $w = xyz$ where:

1. $|xy| \leq p$
2. $|y| \geq 1$ (y is non-empty)
3. For all $i \geq 0$: $xy^i z \in L$

Using the Pumping Lemma

To prove $L$ is not regular:

1. Assume $L$ is regular with pumping length $p$
2. Choose a string $w \in L$ with $|w| \geq p$
3. For any valid division $w = xyz$, show pumping fails
4. Contradiction → $L$ is not regular

Example: $L = \{a^n b^n \mid n \geq 0\}$ is not regular

Proof:

1. Assume $L$ is regular with pumping length $p$
2. Choose $w = a^p b^p$ (clearly in $L$)
3. Any division $w = xyz$ with $|xy| \leq p$ has $y = a^k$ for some $k \geq 1$
4. Pump up: $xy^2z = a^{p+k} b^p \notin L$ (unequal a's and b's)
5. Contradiction! $L$ is not regular. $\square$

Common Non-Regular Languages

Language	Why not regular
$\{a^n b^n\}$	Can't count to match
$\{ww \mid w \in \Sigma^*\}$	Can't remember first half
$\{a^{n^2}\}$	Can't count squares
$\{a^p \mid p \text{ prime}\}$	Primes not periodic

Myhill-Nerode Theorem

Distinguishability

Strings $x$ and $y$ are distinguishable by $L$ if: $\exists z: (xz \in L \land yz \notin L) \text{ or } (xz \notin L \land yz \in L)$

Equivalence Relation

Define $x \equiv_L y$ iff $x$ and $y$ are indistinguishable.

This is an equivalence relation with equivalence classes.

Theorem

$L$ is regular if and only if $\equiv_L$ has finitely many equivalence classes.

Moreover, the number of classes equals the number of states in the minimal DFA.

Application: Proving Non-Regularity

Find infinitely many pairwise distinguishable strings.

Example: For $L = \{a^n b^n\}$:

• Strings $a, a^2, a^3, \ldots$ are pairwise distinguishable
• $a^i$ and $a^j$ distinguished by $b^i$ (if $i \neq j$)
• Infinitely many classes → not regular

Decision Problems

Decidable for Regular Languages

Problem	Question	Complexity
Membership	Is $w \in L$?	$O(
Emptiness	Is $L = \emptyset$?	$O(
Finiteness	Is $L$ finite?	$O(
Equivalence	Is $L_1 = L_2$?	$O(n \log n)$
Inclusion	Is $L_1 \subseteq L_2$?	PSPACE-complete

Emptiness Test

Check if any accept state is reachable from start state.

Equivalence Test

Minimize both DFAs and check isomorphism.

Regular vs. Non-Regular

Regular: Can be Recognized With

• Finite memory (constant)
• No stack
• No counting beyond a constant

Non-Regular: Requires

• Unbounded memory
• Counting
• Matching/balancing
• Remembering arbitrary patterns

Hierarchy

$\text{Regular} \subset \text{Context-Free} \subset \text{Context-Sensitive} \subset \text{Recursive} \subset \text{RE}$

Regular languages are the simplest class in the Chomsky hierarchy.