Theory of Computation – Key Topics Summary (Sipser)

Regular Expressions and Finite Automata

Regular languages are those that can be described by a regular expression or equivalently recognized by a finite automaton. A regular expression (RE) is a formula that defines a language over an alphabet using union (alternative choices), concatenation, and Kleene star (repetition) operations. For example, 0(0|1)*1 is an RE describing all binary strings starting with 0 and ending with 1. The class of languages definable by REs is exactly the class of languages recognized by finite automata (CS 4810 » Lecture 8: Regular Expressions vs Finite Automata).

• Deterministic Finite Automaton (DFA): A DFA is a 5-tuple (Q, Σ, δ, q₀, F) consisting of a finite set of states Q, an input alphabet Σ, a transition function δ: Q × Σ → Q, a start state q₀, and a set of accept states F. A DFA processes an input string symbol by symbol, moving between states according to δ. It accepts the string if it ends in an accept state, otherwise it rejects (Deterministic finite automaton – Wikipedia) (Deterministic finite automaton – Wikipedia). Every DFA recognizes some regular language, and every regular language has a DFA that recognizes it.
• Nondeterministic Finite Automaton (NFA): An NFA is similar to a DFA but allows nondeterministic moves: from a state on a given input symbol (or ε, the empty string) it may transition to multiple possible next states (including none). Formally, δ for an NFA is defined as δ: Q × (Σ ∪ {ε}) → P(Q) (giving a set of possible next states). An NFA accepts if any sequence of choices leads to an accept state. NFAs recognize the same class of languages as DFAs – for every NFA there is an equivalent DFA (subset construction) recognizing the same language. This means nondeterminism does not increase the power of finite automata (every NFA-recognizable language is regular).
• Key Equivalence (Kleene’s Theorem): A language is regular if and only if some regular expression describes it and if and only if some finite automaton (DFA/NFA) recognizes it (CS 4810 » Lecture 8: Regular Expressions vs Finite Automata). In practice, one can convert between these formalisms: an RE can be converted to an NFA (e.g. via Thompson’s construction), and a DFA can be converted to an equivalent RE (e.g. via state elimination).

Regular languages are also closed under boolean operations like union, intersection, and complement (Regular operations) (Regular operations), making them robust. A common technique in proofs is the pumping lemma (see below), which is used to show certain languages are not regular.

Context-Free Grammars and Pushdown Automata

Context-free grammars (CFGs) and pushdown automata (PDAs) define the broader class of context-free languages. A CFG is a collection of recursive rewriting rules (productions) that generate strings in the language, and a PDA is an automaton with a stack that recognizes the same class of languages. Context-free languages (CFLs) include many non-regular languages that require a form of memory, such as balanced parentheses or nested structures.

• Context-Free Grammar (CFG): A CFG is a 4-tuple (V, Σ, R, S) where V is a finite set of variables (nonterminals), Σ is the alphabet of terminals, R is a set of production rules of the form A → α (with A ∈ V and α being a string of symbols from V ∪ Σ), and S ∈ V is the start symbol. The grammar defines a language by starting from S and repeatedly applying rules to derive strings of terminals. For example, a simple grammar for balanced parentheses is:
  • Variables: S
  • Terminals: (, )
  • Rules: S → ( S ) | ε.
    This grammar generates "" (empty string), "()", "(())", "()()", etc. Each context-free rule has a single nonterminal on the left side, meaning substitutions do not depend on surrounding context (hence “context-free”).
• Pushdown Automaton (PDA): A PDA is a 6-tuple (Q, Σ, Γ, δ, q₀, F) where Q is a finite set of states, Σ is the input alphabet, Γ is the stack alphabet, q₀ is the start state, F is the set of accept states, and δ: Q × (Σ ∪ {ε}) × (Γ ∪ {ε}) → P(Q × Γ*) is the transition function. A PDA is essentially an NFA equipped with a stack for memory. On each transition, it can read an input symbol (or ε), optionally pop the top of the stack, and push a string of stack symbols. The stack allows PDAs to recognize patterns with nested or unbounded dependencies (like the equal numbers of a’s and b’s in aⁿbⁿ). A PDA may accept by entering an accept state (after reading the entire input and possibly emptying its stack).
• Key Equivalence: A language is context-free if and only if it can be generated by some CFG, or equivalently, recognized by some PDA (CFG = PDA). In other words, CFGs and PDAs have equal expressive power for languages. Every CFG can be converted into an equivalent PDA (LL or LR parsing construction), and every PDA can be converted into a CFG that generates the same language. This fundamental result connects grammars (used in compilers and language definitions) with automata (machines).

Context-free languages are closed under union, concatenation, and Kleene star (like regular languages), but notably not closed under intersection or complement in general. For example, the language L = {aⁿbⁿcⁿ | n ≥ 0} is not context-free (proof by pumping lemma or other methods), and indeed no PDA or CFG can recognize that equal three-way balance. Deterministic context-free languages (recognized by deterministic PDAs) form a strict subset of CFLs, with important applications in deterministic parsing.

Regular & Context-Free Languages – Pumping Lemmas

The pumping lemmas provide an essential property that all regular and all context-free languages must satisfy. They are commonly used to prove that certain languages do not belong to these classes by contradiction. Each lemma guarantees that long enough strings in the language can be “pumped” (part of the string repeated) and still remain in the language.

• Pumping Lemma for Regular Languages: If L is an infinite regular language, then there exists some integer p (the pumping length) such that any string s in L with length at least p can be split into three parts s = xyz satisfying: (1) |xy| ≤ p, (2) |y| ≥ 1, and (3) for all integers i ≥ 0, the string x y^i z is in L. Intuitively, for any long string accepted by a finite automaton, some state must repeat during the reading (by the pigeonhole principle), and the loop between repeats can be pumped. The substring y (the part corresponding to the loop) can be repeated arbitrarily many times or removed, and the resulting string will still be accepted by the automaton (Pumping Lemma in Theory of Computation – GeeksforGeeks). If a candidate language fails this property (i.e. one can find a long string that cannot be pumped without leaving the language), then it cannot be regular. For example, one can show L = {0^n1^n | n ≥ 0} is not regular by assuming it is and pumping the string 0^p1^p, leading to a contradiction (pumping breaks the equal 0/1 count) (Pumping Lemma in Theory of Computation – GeeksforGeeks).
• Pumping Lemma for Context-Free Languages: Similarly, if L is an infinite context-free language, then there exists an integer p such that any string s in L of length ≥ p can be decomposed into five parts s = u v w x y with conditions: (1) |vwx| ≤ p, (2) |vx| ≥ 1, and (3) for all i ≥ 0, the string u v^i w x^i y is in L. Here two middle sections v and x can be pumped in tandem. This lemma follows from the fact that in any parse (derivation) tree of a sufficiently long string, some nonterminal repeats along a path from the root to a leaf (by the pigeonhole principle), creating a section of the string that the grammar generates in a loop. Pumping those two sections corresponds to repeating that portion of the parse tree. As with the regular case, if we find a long string in a language that cannot be pumped according to these rules, we conclude the language is not context-free. For instance, for L = {0^n1^n2^n | n ≥ 0}, any decomposition of the string 0^p1^p2^p will fail the pumping lemma conditions, proving L is not context-free (Pumping Lemma in Theory of Computation – GeeksforGeeks) (Pumping Lemma in Theory of Computation – GeeksforGeeks).

It’s important to note that the pumping lemmas provide a necessary condition for regularity or context-freeness, but not a sufficient condition. In other words, if a language does satisfy the pumping property, that does not guarantee it is regular/CFL (the lemmas can’t be used to prove a language is regular or CFL). They are purely used as a proof-by-contradiction tool to show languages are outside the regular or context-free families.

Turing Machines and Undecidability

A Turing machine (TM) is a theoretical model of computation that is as powerful as any real-world computer (per Church–Turing Thesis). It extends finite automata with an infinite tape memory that can be read from and written to. Formally, a (deterministic) TM can be defined as a 7-tuple M = (Q, Σ, Γ, δ, q₀, q_accept, q_reject), where Q is a finite set of states, Σ is the input alphabet, Γ is the tape alphabet (Σ plus a blank symbol), q₀ is the start state, and q_accept / q_reject are the two halting states (accept and reject) (Turing Machines). The transition function δ: Q × Γ → Q × Γ × {L,R} dictates, for each state and tape symbol, what the machine does: which state to go to next, what symbol to write on the tape (allowing it to modify data), and which direction to move the tape head (Left or Right). A TM starts with the input string on its tape and the head at the leftmost symbol, and if it reaches q_accept we say it accepts the input; if it reaches q_reject, it rejects the input. (If it never halts, the machine neither accepts nor rejects.)

Turing machines can implement any algorithmic procedure and thus define the class of computable (decidable) problems. In language terms:

• A language L is Turing-recognizable (also known as recursively enumerable) if there exists a TM that accepts exactly the strings in L (and either rejects or loops forever on strings not in L). Such a TM may not halt for non-members, but it will halt and accept for members of the language.
• A language L is decidable (or Turing-decidable, also called recursive) if there exists a TM that decides it – meaning the TM halts on every input, accepting strings in L and rejecting strings not in L. Decidable languages are exactly those problems for which an algorithm can always give an answer “yes or no” in finite time () (). Every decidable language is Turing-recognizable (by definition), but the converse is not always true.

Undecidability refers to decision problems that no Turing machine can solve algorithmically (i.e. no TM that always halts can decide the language). A classic example is the Halting Problem: determine whether an arbitrary TM M halts on a given input w. This problem can be framed as a language HALT = {⟨M, w⟩ | M is a TM that halts on input w} (where ⟨M, w⟩ is an encoding of the machine and input). Turing’s theorem (1936) shows that HALT is undecidable – there is no general algorithm to solve it for all possible program-input pairs (Halting problem – Wikipedia). Informally, any supposed decider for HALT can be shown to lead to a logical contradiction (by constructing a machine that diagonalizes against it). This means there are fundamental limits to computation: some well-defined problems cannot be solved by any algorithm. Another way to see this is via a diagonalization argument: since the set of TMs is countable but the power set of inputs is uncountable, there are languages that no TM recognizes.

Once an initial undecidable problem like the halting problem is known, we can prove other problems undecidable by reductions. A reduction transforms instances of a known undecidable problem into instances of another problem. If such a transformation can be done computably, then a decider for the second problem could be used to decide the first – implying if the first is undecidable, the second must be as well. Using reductions, many other problems in logic, mathematics, and computer science have been shown undecidable (e.g. Post’s Correspondence Problem, certain questions about context-free grammars, and so on).

In summary, Turing machines represent the ultimate model of computation in Sipser’s framework: they capture all algorithmically solvable problems (decidable languages). Undecidability highlights the existence of languages beyond this reach. Decidability and reducibility are key concepts for classifying problems in computability theory, and they draw a clear boundary between what can be computed in principle and what cannot.