Formal Languages and Automata

Overview

The theory of formal languages and automata is the foundation of computation theory, studying the capabilities and limitations of different computational models. From the simplest finite automata to Turing machines, these models form a strict hierarchy.

1. Chomsky Hierarchy

graph TB
    T3[Type 3: Regular Languages] --> T2[Type 2: Context-Free Languages]
    T2 --> T1[Type 1: Context-Sensitive Languages]
    T1 --> T0[Type 0: Recursively Enumerable Languages]

Type	Language Class	Grammar	Automaton	Production Rules
Type 3	Regular languages	Regular grammar	Finite automaton (FA)	$A \to aB$ or $A \to a$
Type 2	Context-free languages	Context-free grammar (CFG)	Pushdown automaton (PDA)	$A \to \gamma$
Type 1	Context-sensitive languages	Context-sensitive grammar (CSG)	Linear bounded automaton (LBA)	$\alpha A \beta \to \alpha \gamma \beta$
Type 0	Recursively enumerable languages	Unrestricted grammar	Turing machine (TM)	$\alpha \to \beta$

Each level strictly contains the next: $\text{REG} \subsetneq \text{CFL} \subsetneq \text{CSL} \subsetneq \text{RE}$

2. Finite Automata

2.1 Deterministic Finite Automaton (DFA)

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

$Q$: Finite set of states
$\Sigma$: Input alphabet
$\delta: Q \times \Sigma \to Q$: Transition function
$q_0 \in Q$: Initial state
$F \subseteq Q$: Set of accept states

stateDiagram-v2
    direction LR
    [*] --> q0
    q0 --> q0: 0
    q0 --> q1: 1
    q1 --> q0: 0
    q1 --> q1: 1
    q1 --> [*]

The diagram above shows a DFA that recognizes "binary strings ending in 1", with $F = \{q_1\}$.

2.2 Nondeterministic Finite Automaton (NFA)

Definition: An NFA is a 5-tuple $N = (Q, \Sigma, \delta, q_0, F)$

$\delta: Q \times (\Sigma \cup \{\varepsilon\}) \to \mathcal{P}(Q)$: Transition function returns a set of states

Key differences:

Property	DFA	NFA
Transition function	Uniquely determined	Multiple possibilities
$\varepsilon$-transitions	Not allowed	Allowed
Acceptance condition	Unique path reaches accept state	Some path reaches accept state
Implementation	Direct simulation	Requires backtracking or subset construction

2.3 Equivalence of DFA and NFA (Subset Construction)

Theorem: For any NFA $N$, there exists an equivalent DFA $D$ such that $L(N) = L(D)$.

Subset construction:

DFA states are subsets of NFA states: $Q_D = \mathcal{P}(Q_N)$
Initial state: $q_{0,D} = \varepsilon\text{-closure}(\{q_{0,N}\})$
Transition: $\delta_D(S, a) = \varepsilon\text{-closure}\left(\bigcup_{q \in S} \delta_N(q, a)\right)$
Accept states: $F_D = \{S \in Q_D \mid S \cap F_N \neq \emptyset\}$

State Explosion

In the worst case, the subset construction produces a DFA with $2^{|Q_N|}$ states. There exist NFAs for which this upper bound is tight.

2.4 DFA Minimization

Myhill-Nerode theorem: A language $L$ is regular if and only if its Myhill-Nerode equivalence relation has finitely many equivalence classes, and the number of states in the minimal DFA equals the number of equivalence classes.

Equivalence relation: $x \sim_L y \iff \forall z \in \Sigma^*, xz \in L \leftrightarrow yz \in L$

Minimization algorithm (Hopcroft's algorithm):

Initial partition: {F, Q-F}
repeat:
    For each partition block and each symbol a:
        If states in a block transition to different blocks on a:
            Refine that block
until no further changes

3. Regular Expressions

3.1 Definition

Regular expressions are defined recursively:

$\emptyset$, $\varepsilon$, $a$ ($a \in \Sigma$) are regular expressions
If $R_1, R_2$ are regular expressions, then so are $R_1 \cup R_2$, $R_1 \circ R_2$, $R_1^*$

3.2 Equivalence of Regular Expressions and Finite Automata

Kleene's theorem:

\[ \text{Regular Expressions} \iff \text{Finite Automata} \iff \text{Regular Grammars} \]

FA $\to$ RE: State elimination method
RE $\to$ NFA: Thompson's construction

graph LR
    RE[Regular Expression] -->|Thompson's construction| NFA
    NFA -->|Subset construction| DFA
    DFA -->|Minimization| minDFA[Minimal DFA]
    DFA -->|State elimination| RE

4. Pumping Lemma for Regular Languages

4.1 Statement

If $L$ is a regular language, then there exists a constant $p$ (pumping length) such that for any $s \in L$ ($|s| \geq p$), there exists a decomposition $s = xyz$ satisfying:

$|y| > 0$
$|xy| \leq p$
$\forall i \geq 0, xy^iz \in L$

4.2 Application: Proving Non-Regularity

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

Proof: Assume $L$ is regular with pumping length $p$.

Take $s = a^p b^p \in L$, $|s| = 2p \geq p$.

By the pumping lemma, $s = xyz$, $|xy| \leq p$, so $y = a^k$ ($k > 0$).

Take $i = 2$: $xy^2z = a^{p+k}b^p \notin L$ (since $p + k \neq p$). Contradiction. $\square$

5. Pushdown Automata and Context-Free Languages

5.1 Context-Free Grammar (CFG)

Definition: $G = (V, \Sigma, R, S)$

$V$: Set of variables (nonterminals)
$\Sigma$: Set of terminals
$R$: Production rules $A \to \gamma$ ($A \in V$, $\gamma \in (V \cup \Sigma)^*$)
$S \in V$: Start variable

Example: CFG for $\{a^n b^n \mid n \geq 0\}$:

\[ S \to aSb \mid \varepsilon \]

5.2 Chomsky Normal Form (CNF)

Any CFG can be converted to Chomsky normal form:

\[ A \to BC \quad \text{or} \quad A \to a \quad \text{or} \quad S \to \varepsilon \]

CYK algorithm: A dynamic programming parsing algorithm based on CNF, with complexity $O(n^3|G|)$.

5.3 Pushdown Automaton (PDA)

Definition: A PDA is a 6-tuple $(Q, \Sigma, \Gamma, \delta, q_0, F)$

Additional $\Gamma$: Stack alphabet
$\delta: Q \times (\Sigma \cup \{\varepsilon\}) \times (\Gamma \cup \{\varepsilon\}) \to \mathcal{P}(Q \times (\Gamma \cup \{\varepsilon\}))$

Theorem: CFL $=$ the class of languages accepted by PDAs $=$ the class of languages generated by CFGs.

Deterministic PDA

The class of languages recognized by deterministic PDAs (DPDA) -- deterministic context-free languages (DCFL) -- is a proper subset of CFL. The syntax of most programming languages is DCFL.

5.4 Pumping Lemma for Context-Free Languages

If $L$ is a context-free language, then there exists a constant $p$ such that for any $s \in L$ ($|s| \geq p$), there exists a decomposition $s = uvxyz$ satisfying:

$|vy| > 0$
$|vxy| \leq p$
$\forall i \geq 0, uv^ixy^iz \in L$

Application: Prove that $L = \{a^n b^n c^n \mid n \geq 0\}$ is not context-free.

6. Properties of Context-Free Languages

6.1 Closure Properties

Operation	Regular Languages	Context-Free Languages
Union	Closed	Closed
Concatenation	Closed	Closed
Kleene star	Closed	Closed
Intersection	Closed	Not closed
Complement	Closed	Not closed
Intersection with a regular language	—	Closed

6.2 Decision Problems

Problem	Regular Languages	CFL
Membership $w \in L$?	$O(	w
Emptiness $L = \emptyset$?	Decidable	Decidable
Equivalence $L_1 = L_2$?	Decidable	Undecidable

7. Turing Machines

7.1 Definition

Turing machine $M = (Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject})$

$\Gamma$: Tape alphabet ($\Sigma \subsetneq \Gamma$, including blank symbol $\sqcup$)
$\delta: Q \times \Gamma \to Q \times \Gamma \times \{L, R\}$: Transition function (the head can move left or right)

7.2 Turing Machines and Other Models

graph TB
    FA[Finite Automaton] -->|Add stack| PDA[Pushdown Automaton]
    PDA -->|Infinite tape| TM[Turing Machine]
    TM ---|Equivalent| Multi[Multi-tape TM]
    TM ---|Equivalent| NDTM[Nondeterministic TM]
    TM ---|Equivalent| Lambda[Lambda Calculus]
    TM ---|Equivalent| RAM[RAM Model]

Church-Turing thesis: All "reasonable" models of computation are equivalent to Turing machines.

7.3 Turing Machine Variants

Variant	Relationship to Standard TM
Multi-tape TM	Equivalent ($O(t^2)$ simulation)
Nondeterministic TM	Equivalent ($O(2^{t})$ simulation)
Two-way infinite tape	Equivalent
Multi-dimensional tape	Equivalent
Enumerator	Equivalent to recognizer

8. Language Hierarchy Summary

graph TB
    subgraph "Chomsky Hierarchy"
        REG["Regular Languages<br>DFA/NFA/RE"]
        CFL["Context-Free Languages<br>PDA/CFG"]
        CSL["Context-Sensitive Languages<br>LBA"]
        RE["Recursively Enumerable Languages<br>TM"]
        ALL["All Languages"]
    end
    REG --> CFL --> CSL --> RE --> ALL

Key boundary distinctions:

Regular vs CFL: Distinguished by $\{a^n b^n\}$
CFL vs CSL: Distinguished by $\{a^n b^n c^n\}$
Decidable vs RE: Distinguished by the halting problem
RE vs ALL: Existence of unrecognizable languages (diagonalization)

References

Sipser, Introduction to the Theory of Computation (classic textbook)
Hopcroft, Motwani & Ullman, Introduction to Automata Theory, Languages, and Computation

Related sections:

Problem	Regular Languages	CFL
Membership \(w \in L\)?	$O(	w
Emptiness \(L = \emptyset\)?	Decidable	Decidable
Equivalence \(L_1 = L_2\)?	Decidable	Undecidable

Variant	Relationship to Standard TM
Multi-tape TM	Equivalent (\(O(t^2)\) simulation)
Nondeterministic TM	Equivalent (\(O(2^{t})\) simulation)
Two-way infinite tape	Equivalent
Multi-dimensional tape	Equivalent
Enumerator	Equivalent to recognizer