Theory of Computation – Core Concepts (GATE‑CS)
Goal: Provide a self‑contained, exam‑oriented study guide that covers the fundamental ideas, formal definitions, key theorems, proofs, and pitfalls needed for the GATE Computer Science/Information Technology exam.
1. Overview
| Concept | What it models | Key properties | Typical questions |
|---|---|---|---|
| Finite Automata (FA) | Deterministic (DFA) / Nondeterministic (NFA) machines that accept regular languages. | Closure under union, intersection, complement, concatenation, Kleene star. | Convert NFA → DFA, minimization, state elimination. |
| Regular expressions | Algebraic syntax for regular languages. | Equivalent to DFA/NFA. | Convert RE → NFA, NFA → RE. |
| Pumping Lemma (Regular) | Tool to prove non‑regularity. | Requires existence of pumping length p. | Show language not regular. |
| Myhill–Nerode | Characterizes regular languages via equivalence classes. | Gives minimal DFA size. | State minimization. |
| Pushdown Automata (PDA) | Accepts context‑free languages (CFL). | Deterministic PDA (DPDA) vs. Nondeterministic PDA (NPDA). | Convert CFG → PDA, PDA → CFG. |
| Pumping Lemma (CFL) | Tool to prove CFL non‑membership. | Requires two pumping lengths p, q. | Show language not CFL. |
| Turing Machines (TM) | Models general computation. | Decidability, recognizability, halting problem. | Reduce problems, prove undecidability. |
| Decidability / Recognizability | Decidable = TM halts on all inputs; Recognizable = TM halts on accepted inputs. | Closure under many operations; undecidability of many problems. | |
| Complexity Classes | P, NP, PSPACE, EXPTIME, etc. | Reductions, NP‑completeness, Cook’s theorem. | Prove NP‑completeness of a language. |
2. Finite Automata (FA)
2.1 Formal Definition
A Deterministic Finite Automaton (DFA) is a 5‑tuple
[
\mathcal{M}= (Q, \Sigma, \delta, q_0, F)
]
- (Q): finite set of states
- (\Sigma): finite input alphabet
- (\delta: Q\times \Sigma \to Q): transition function
- (q_0\in Q): start state
- (F\subseteq Q): set of accepting (final) states
For a word (w = a_1a_2\ldots a_n), the extended transition function (\hat\delta) is defined recursively: [ \hat\delta(q,\varepsilon)=q,\qquad \hat\delta(q, a_1a_2\ldots a_n)=\hat\delta(\delta(q,a_1), a_2\ldots a_n). ]
A word (w) is accepted iff (\hat\delta(q_0,w)\in F).
An NFA is defined similarly but (\delta: Q\times \Sigma \to 2^Q).
An ε‑NFA allows (\delta: Q\times (\Sigma\cup{\varepsilon})\to 2^Q).
2.2 Equivalence of DFA, NFA, ε‑NFA, Regular Expressions
- Subset construction: Any NFA can be converted to an equivalent DFA (exponential blow‑up).
- State elimination / Arden’s lemma: DFA → Regular Expression.
- Myhill–Nerode theorem: A language is regular iff it has finitely many equivalence classes under the relation
[ x \equiv_L y \iff \forall z\in\Sigma^*,,xz\in L \Leftrightarrow yz\in L. ]
2.3 Closure Properties
| Operation | Regular | Proof Idea |
|---|---|---|
| Union | ✅ | DFA for (L_1\cup L_2): product construction with OR on accept states. |
| Intersection | ✅ | Product construction with AND on accept states. |
| Complement | ✅ | Swap accepting/non‑accepting states of DFA. |
| Concatenation | ✅ | Create ε‑transitions from final states of (L_1) to start of (L_2). |
| Kleene Star | ✅ | ε‑transition from final states to start plus new start that is accepting. |
| Reversal | ✅ | Reverse all edges and swap start / final. |
| Substitution (homomorphism) | ✅ | Replace each symbol by a regular language; closure follows from product construction. |
Tricky point: Complement only works for DFAs, not for NFAs directly; one must first determinize.
2.4 Minimal DFA
- Hopcroft’s algorithm (O(|Q| log |Q|)) partitions states into distinguishable vs. indistinguishable classes.
- Key step: Two states are distinguishable iff there exists a word distinguishing them.
Formula: If a DFA has (n) states, then its minimal DFA has at most (n) states.