Theory of Computation

Alphabets, strings and languages

The vocabulary of the whole subject: alphabets, strings, the empty string, concatenation and powers, prefixes, suffixes, substrings and subsequences, Sigma-star, languages as sets of strings and the operations on them (union, intersection, complement, concatenation, Kleene star, reversal), the special cases of the empty language and the language of the empty string, and counting.

Deterministic finite automata

The DFA as a five-tuple, its transition function and the extended transition function, acceptance and the language of a DFA, transition tables and state diagrams, complete DFAs and the dead state, how a run proceeds step by step, why a DFA needs only constant memory and time linear in the input, how many DFAs there are, and the standard small examples (ends with 01, even number of a's, divisible by 3).

DFA design patterns and counting states

How to design a DFA by deciding what must be remembered, and how many states the result needs: counting modulo k, remembering the last symbols (ends with, contains, starts with), length conditions, remainders of binary numbers, combining machines by product (intersection, union), and complement; with the exact state counts GATE asks for, each computed by minimisation and confirmed by counting Myhill-Nerode classes.

NFA and epsilon-NFA

Nondeterministic finite automata: the transition function that returns a set of states, epsilon moves and epsilon closure, acceptance as the existence of an accepting computation, simulating an NFA by tracking the set of active states, design by guessing, the epsilon-NFA, how NFAs compare in size with DFAs, and what nondeterminism does and does not add.

Subset construction

Converting an NFA (with or without epsilon moves) into an equivalent DFA: the DFA's states are sets of NFA states, the start set is the epsilon closure of the start state, transitions follow all moves and take closures, a set is accepting if it contains an accepting NFA state; building only the reachable subsets, the dead state, the exponential blow-up (the n-th symbol from the end needs 2^n states), and the fact that the result need not be minimal.

DFA minimisation

Reducing a DFA to the smallest equivalent DFA: remove unreachable states, make the machine complete, merge equivalent states found by partition refinement (Moore) or by the table-filling algorithm, with the distinguishing string of every pair; the minimal DFA is unique up to renaming, the dead state counts, the state counts GATE asks for, and what minimisation does not do (NFAs).

Mealy and Moore machines

Finite automata that produce output: Mealy machines (output on the transitions) and Moore machines (output on the states), what an output string looks like (length n for Mealy, n + 1 for Moore), conversion in both directions and what it does to the number of states, minimisation by partition refinement, shortest input that reaches a given state with a given output, and the standard designs: two's complement, adding one, the serial adder, remainder machines and overlapping sequence detectors.

Regular expressions

Regular expressions as a notation for languages: the inductive definition (empty set, epsilon, symbols, union, concatenation, star), precedence, the language of an expression, derived operators, the algebraic laws that hold and the popular ones that fail, writing expressions for the standard GATE languages, counting strings, and what regular expressions cannot say.

Regex to automata and back

Kleene's theorem in both directions: Thompson's construction turns a regular expression into an epsilon-NFA of linear size (then subset construction and minimisation give the DFA), and state elimination or Arden's rule turns a DFA back into a regular expression; building blocks, state counts, worked conversions and the exponential size of expressions.

Closure properties of regular languages

The operations under which regular languages stay regular (union, intersection, complement, difference, concatenation, star, reversal, homomorphism, inverse homomorphism, quotients, prefixes, suffixes, half) with the construction and the state-count bound of each, the operations that are not closed (infinite union, arbitrary subsets), and how closure is used to prove that a language is not regular.

Pumping lemma for regular languages

The pumping lemma as a necessary condition for regularity: the statement with its quantifiers, the pigeonhole proof from a DFA with p states, the game view used to prove that a language is not regular (a^n b^n, ww, squares, primes, balanced parentheses), the standard mistakes (the lemma never proves regularity, the cut is chosen by the adversary), the pumpable-but-not-regular counterexample, and the DFA tests for emptiness and finiteness.

Myhill-Nerode theorem

The Myhill-Nerode theorem: the equivalence of strings by their possible continuations, why a language is regular exactly when it has finitely many classes, how the classes are the states of the minimal DFA (with its transition table read off the classes), how to prove a language not regular by exhibiting infinitely many pairwise distinguishable strings, how to count the states of a minimal DFA, and how the theorem compares with the pumping lemma.

Context-free grammars and derivations

Context-free grammars as generators of languages: variables, terminals, productions, derivations (leftmost, rightmost, in any order), sentential forms, parse trees and their relation to derivations, the language of a grammar, designing grammars for the standard GATE languages (a^n b^n, palindromes, balanced parentheses, equal counts, i = j or j = k), regular languages as a special case, and the usual wrong grammars.

Ambiguity in grammars

Ambiguity of context-free grammars: a grammar is ambiguous when some string has two parse trees (equivalently two leftmost or two rightmost derivations), counting parse trees by dynamic programming, the Catalan explosion for bracketing grammars, cyclic grammars with infinitely many trees, removing ambiguity by layering (precedence and associativity), unambiguous grammars for the standard languages, inherently ambiguous languages, and undecidability of ambiguity.

Simplification, CNF and GNF

Simplifying context-free grammars (removing epsilon-productions, unit productions and useless symbols, in the right order), Chomsky normal form (every production A -> BC or A -> a) and Greibach normal form (every production A -> a followed by variables), the conversion procedure with a stage-by-stage example, derivation lengths (2n - 1 steps in CNF, n in GNF), and the CYK membership algorithm with its table.

Pushdown automata

Pushdown automata as NFAs with a stack: the formal definition, instantaneous descriptions and moves, acceptance by final state and by empty stack (and the conversions between them), nondeterminism and epsilon-moves, designing PDAs for a^n b^n, ww^R, equal counts, balanced parentheses and i = j or j = k, tracing a computation, and what a PDA cannot do (compare more than one count).

PDA and CFG equivalence

Context-free grammars and pushdown automata define the same languages: the one-state PDA built from a grammar (expand variables on the stack, match terminals), the triple construction [pXq] that turns a PDA with acceptance by empty stack into a grammar, a PDA without epsilon-moves from Greibach normal form, the sizes of both constructions, and traced examples of each direction.

Deterministic versus nondeterministic PDA

Deterministic pushdown automata and the deterministic context-free languages: the definition of determinism (no choice, including epsilon-moves), why a DPDA is strictly weaker than a PDA (ww^R, i = j or j = k), acceptance by empty stack versus final state for DPDAs (prefix property), the examples that are deterministic (a^n b^n, w c w^R, equal counts, balanced parentheses), closure properties of DCFLs, and the link to LR parsing.

Closure properties of CFLs

Which operations keep a language context-free: union, concatenation, star, reversal, homomorphism, inverse homomorphism and intersection with a regular language (with the grammar or product constructions), and which do not: intersection, complement and difference (counterexample a^n b^n c^n); the complement of a^n b^n c^n is nevertheless context-free; using closure to prove that a language is not context-free.

Pumping lemma for CFLs

The pumping lemma for context-free languages (two pumped parts, s = uvxyz with |vxy| at most p and vy not empty), its proof from a repeated variable on a long path of a Chomsky normal form parse tree, the game for proving that a language is not context-free (a^n b^n c^n, ww, a^i b^j c^k with i < j < k, squares, a^i b^j c^k d^l with i = k and j = l), the table of decompositions, and the usual mistakes.

Decision problems for CFLs

Which questions about context-free grammars and pushdown automata can an algorithm answer: membership (CYK), emptiness (generating variables), finiteness (cycle in the reduced grammar), emptiness of the intersection with a regular language and containment in a regular language (product construction); and which cannot: universality, equivalence, containment, disjointness of two grammars, ambiguity and regularity, all by reduction from the Post correspondence problem; the contrast with regular languages and with Turing machines.

Chomsky hierarchy

The four types of grammars (unrestricted, context-sensitive, context-free, regular), the language classes and machines that match them (recursively enumerable and Turing machines, context-sensitive and linear bounded automata, context-free and PDAs, regular and finite automata), the strict inclusions with a witness language for each step, classifying a grammar by the shape of its productions, a context-sensitive grammar for a^n b^n c^n, and the closure and decidability summary.

Turing machines

The Turing machine as a finite control with an infinite tape: the formal definition, configurations and moves, the three possible outcomes (accept, reject, loop), recognising versus deciding, worked machines for a^n b^n and a^n b^n c^n (with move counts that grow with the square of n), a machine that computes a function (binary increment), a recogniser that never halts on some inputs, and the conventions that differ between textbooks.

TM variants and the Church-Turing thesis

Variants of the Turing machine that do not add power (several tapes, a tape infinite in one or two directions, stay moves, nondeterminism, enumerators) and what they cost in time (a quadratic slowdown for several tapes, an exponential one for nondeterminism), encodings of machines and the universal Turing machine, and the Church-Turing thesis as a statement about the informal notion of algorithm rather than a theorem.

Decidable and recognisable languages

Decidable (recursive) and Turing-recognisable (recursively enumerable) languages: definitions, the theorem that a language is decidable exactly when it and its complement are recognisable (run both recognisers in turn), closure properties of both classes, co-recognisable languages, the decidable problems about finite automata and grammars (acceptance, emptiness, equivalence for DFAs; acceptance and emptiness for CFGs) and the undecidable ones, with the Venn picture of all the classes.

Halting problem and reductions

The first undecidable problems: the acceptance problem A_TM and the halting problem for Turing machines, proved undecidable by diagonalisation (and by counting machines against languages), the universal machine showing A_TM is recognisable, mapping reductions and how they transfer undecidability (A_TM to HALT, E_TM, EQ_TM), the unrecognisable complement of A_TM, and a map of which problems are decidable, recognisable, co-recognisable or neither.

Rice's theorem

Rice's theorem: every non-trivial property of the language of a Turing machine is undecidable. The statement (semantic and non-trivial properties), the reduction from A_TM through the machine M_w, how to apply it to properties such as emptiness, finiteness, regularity and universality, which questions are NOT covered (syntactic properties such as the number of states or halting within k moves, and behaviour that is not a property of the language, such as halting on the empty input), and the usual traps.