Theory of Computation: Core Concepts (CS example) Notes for GATE

Theory of Computation – Core Concepts (GATE CS)

Audience – Students preparing for the GATE CS exam.
Goal – Build a quick‑reference sheet that covers the essentials of the theory of computation: automata, languages, grammars, machines, and complexity.

1. Simple Explanation

Concept	What it is	Why it matters
Finite Automaton (FA)	A mathematical model with a finite set of states, input symbols, transition function, start state, and accept states.	Recognizes regular languages; forms the basis for lexical analysis.
Deterministic FA (DFA)	Each state has at most one transition for each symbol.	Easy to implement; guarantees a single computation path.
Nondeterministic FA (NFA)	A state can have multiple transitions for the same symbol or ε‑transitions.	Easier to design; equivalent to DFA in power.
Regular Language	Set of strings accepted by some FA or described by a regular expression.	Most programming languages’ token sets are regular.
Context‑Free Grammar (CFG)	Production rules of the form `A → α` where `A` is a non‑terminal and `α` is a string of terminals and/or non‑terminals.	Generates languages that require a stack (e.g., matched parentheses).
Pushdown Automaton (PDA)	FA + a stack; accepts context‑free languages.	Models recursive function calls and nested structures.
Turing Machine (TM)	FA + infinite tape + read/write head.	Universal model of computation; can simulate any algorithm.
Decidability	Whether a problem can be algorithmically answered yes/no.	Fundamental in understanding what can be computed.
Complexity Classes	`P`, `NP`, `PSPACE`, `EXPTIME`, etc.	Classify problems by resource usage (time, space).

2. Key Points

2.1 Finite Automata

Formal definition: M = (Q, Σ, δ, q₀, F)
- Q – finite set of states
- Σ – finite alphabet
- δ : Q × Σ → Q (or δ : Q × (Σ∪{ε}) → 𝒫(Q) for NFA/ε‑NFA)
- q₀ ∈ Q – start state
- F ⊆ Q – accepting states
Equivalence:
- DFA ⇔ NFA ⇔ ε‑NFA
- All recognize exactly the regular languages.
Conversion:
1. NFA → ε‑NFA (add ε‑transitions)
2. ε‑NFA → DFA (subset construction)

2.2 Regular Languages

Closure properties: union, concatenation, Kleene star, intersection, complement, difference.
Regular expressions: operators |, concatenation, *, +, ?, parentheses.
Pumping Lemma (regular): For any regular language L, ∃ pumping length p s.t. every string s ∈ L with |s| ≥ p can be split s = xyz satisfying:
1. |xy| ≤ p
2. |y| ≥ 1
3. xyⁱz ∈ L for all i ≥ 0

2.3 Context‑Free Grammars (CFG)

Production rule: A → α where A ∈ V (non‑terminals) and α ∈ (V ∪ Σ)*.
Language generated: set of terminal strings derivable from start symbol S.
Chomsky Normal Form (CNF): every rule is A → BC or A → a.
Normal Forms: CNF, Greibach Normal Form (GNF).
Ambiguity: a CFG is ambiguous if a string has more than one parse tree.

2.4 Pushdown Automata (PDA)

Formal definition: M = (Q, Σ, Γ, δ, q₀, Z₀, F)
- Γ – stack alphabet
- δ : Q × (Σ∪{ε}) × Γ → 𝒫(Q × Γ*)
- Z₀ – initial stack symbol
Acceptance: by final state or empty stack.
Equivalence: CFG ⇔ PDA (recognize exactly CFLs).
Deterministic PDA (DPDA): accept a strict subset of CFLs (deterministic CFLs).

2.5 Pumping Lemma (CFL)

For any CFL L, ∃ pumping length p such that any string s ∈ L with |s| ≥ p can be expressed s = uvwxy satisfying:

|vwx| ≤ p 2