Purpose. These notes are my own write-up of the lecture material from the course Automata, Language Theory, and Complexity. I adapted the technical content into a blog-friendly format while preserving the formal detail, worked examples, and connections to broader computational theory. All images and examples are reconstructed based on my understanding of the use cases.
1. Introduction
Automata theory forms the foundation of computer science. It begins with finite automata for regular languages, extends to context-free grammars and pushdown automata, and culminates with Turing machines and the limits of computation. Finally, complexity theory introduces classes such as P and NP and the notion of NP-completeness.
2. Finite Automata and Regular Languages
2.1 Deterministic Finite Automata (DFA)
Definition.
A DFA is a 5-tuple $(Q, \Sigma, \delta, q_0, F)$ where
- $Q$: finite set of states,
- $\Sigma$: alphabet,
- $\delta: Q \times \Sigma \to Q$: transition function,
- $q_0$: start state,
- $F$: accepting states.
2.2 Worked Example: DFA for divisibility by 3
Problem. Build a DFA over ${0,1}$ that accepts binary strings whose value is divisible by 3.
Solution.
- States $q_0, q_1, q_2$ represent remainder mod 3.
- Start $q_0$, accepting $q_0$.
- Transition: on input $b$, new state = $(2 \cdot r + b) \bmod 3$.
So “110” = 6, ends in $q_0$, accepted.
3. Regular Expressions and Properties
3.1 Equivalence of Regular Expressions and Automata
Every regex corresponds to an NFA; NFAs and DFAs are equivalent.
3.2 Pumping Lemma
Lemma.
If $L$ is regular, $\exists p$ such that for $w \in L$ with $|w|\geq p$, $w=xyz$, $|xy|\leq p$, $|y|\geq1$, and $xy^iz \in L$ $\forall i \geq 0$.
Worked Example: Non-regularity
Problem. Show $L={a^n b^n \mid n \geq 0}$ is not regular.
Solution.
- Assume $L$ is regular, pumping length $p$.
- Choose $w=a^p b^p$.
- $y$ lies in $a$’s; pumping $y$ changes # of $a$’s.
- Resulting string has more $a$’s than $b$’s, not in $L$. Contradiction.
4. Context-Free Grammars (CFGs)
4.1 Definition
A CFG is $(V, \Sigma, R, S)$ with variables $V$, terminals $\Sigma$, rules $R$, and start $S$.
4.2 Worked Example: Balanced Parentheses
Grammar. $S \to SS \mid (S) \mid \epsilon$
Example derivation. $(()())$:
$S \Rightarrow (S) \Rightarrow (SS) \Rightarrow (S(S)) \Rightarrow (()())$.
4.3 Ambiguity Example
Grammar $E \to E+E \mid EE \mid a$.
The string $a+aa$ has two parse trees, showing ambiguity.
5. Pushdown Automata (PDA)
5.1 Definition
PDA = $(Q, \Sigma, \Gamma, \delta, q_0, Z_0, F)$ with stack alphabet $\Gamma$.
5.2 Worked Example: PDA for ${a^n b^n}$
- On $a$: push $A$.
- On $b$: pop $A$.
- Accept if stack empty at end.
Trace on “aaabbb”: stack pushes 3 $A$, then pops 3, accept.
6. Advanced Context-Free Language Properties
- Normal forms: CNF, GNF.
- Pumping lemma for CFLs.
Worked Example: Not Context-Free
$L={a^n b^n c^n \mid n\geq0}$.
Suppose pumping length $p$. Take $w=a^p b^p c^p$.
By lemma, pumped substring affects at most 2 of the 3 segments.
Resulting string unbalanced → contradiction.
So $L$ not context-free.
7. Turing Machines and Computability
7.1 Definition
TM = $(Q, \Sigma, \Gamma, \delta, q_0, q_{\text{accept}}, q_{\text{reject}})$.
7.2 Worked Example: Palindrome TM
Algorithm:
- Mark first symbol, scan right to last symbol.
- Compare, erase both.
- Repeat.
- Accept if string fully erased.
8. Decidability and Undecidability
8.1 Halting Problem
Given TM $M$ and input $w$, no decider exists for “does $M$ halt on $w$?” Proof by diagonalization.
8.2 Worked Example: Reduction
Show CFG intersection emptiness undecidable.
Reduce from halting problem: encode TM into CFGs $G_1, G_2$ such that $L(G_1)\cap L(G_2)\neq \emptyset$ iff TM halts.
9. Complexity Theory
9.1 P and NP
$P$: languages decidable in polynomial time.
$NP$: languages verifiable in polynomial time.
9.2 NP-Completeness
$L$ is NP-complete if $L\in NP$ and every $L’\in NP$ polytime reduces to $L$.
Worked Example: Reduction 3SAT → Independent Set
- Clause with 3 literals → 3 vertices forming triangle.
- Connect contradictory literals.
- Graph has independent set of size = #clauses iff formula satisfiable.
Thus Independent Set is NP-complete.
10. Advanced Topics (Optional)
- PSPACE, PSPACE-completeness.
- Randomized complexity (RP, BPP).
- Connections to verification/model checking.
References
- Hopcroft, J. E., Motwani, R., Ullman, J. D. Introduction to Automata Theory, Languages, and Computation. 3rd Edition, Addison-Wesley, 2006.
- Sipser, M. Introduction to the Theory of Computation. 3rd Edition, Cengage, 2012.
- MIT OpenCourseWare: Automata, Computability, and Complexity (6.045J).
- Stanford Online: Automata Theory (Jeff Ullman).