Languages, proofs and models of computation

Theory of computation asks three questions that sound simple and turn out to be deep. What can be computed at all? What can be computed efficiently? And what can be computed by machines with limited memory? The answers shape the rest of computing science. They tell a compiler writer which parts of a language a scanner can handle and which need a parser. They tell a software engineer that no tool will ever decide whether an arbitrary program halts, so static analyzers must approximate. They tell a cryptographer which problems are believed hard enough to protect data, and an algorithm designer when to stop looking for a fast exact algorithm and settle for an approximation or a heuristic.

This course builds those answers carefully, with definitions and proofs, because informal intuition is unreliable here. Many plausible claims are false: adding nondeterminism does not make finite automata more powerful, but it does make pushdown automata more powerful; the intersection of two context-free languages need not be context-free; a problem can be recognizable without being decidable. You have already met pieces of this material. CMPUT-272 introduced proofs, induction, sets, functions and countability, including Cantor's diagonal argument. CMPUT-204 analyzed algorithms with asymptotic notation and introduced the idea of NP-completeness. CMPUT-415 used regular expressions, finite automata and context-free grammars as engineering tools in a compiler. Here we study the same objects as mathematics, ask what they can and cannot do, and prove it.

Alphabets, strings and languages

Everything in this course is phrased in terms of strings. An alphabet is a finite, non-empty set of symbols, written \(\Sigma\). Common alphabets are \(\{0, 1\}\), the 26 lowercase letters, or the set of ASCII characters. A string over \(\Sigma\) is a finite sequence of symbols from \(\Sigma\). Its length \(|w|\) is the number of symbols, and the empty string, written \(\varepsilon\), has length 0. Concatenation \(xy\) writes x followed by y, so \(|xy| = |x| + |y|\) and \(\varepsilon\) is the identity: \(\varepsilon w = w \varepsilon = w\). We write \(w^k\) for k copies of w concatenated, \(w^R\) for the reverse of w, and \(\Sigma^*\) for the set of all strings over \(\Sigma\), including \(\varepsilon\).

A language over \(\Sigma\) is any set of strings over \(\Sigma\), that is, any subset of \(\Sigma^*\). Languages may be finite, such as \(\{\varepsilon, 0, 01\}\), or infinite, such as the set of binary strings with an even number of 1s. The empty language \(\emptyset\) contains no strings at all and is different from \(\{\varepsilon\}\), which contains exactly one string, the empty one. Because languages are sets, the set operations apply: union, intersection, complement \(\overline{L} = \Sigma^* \setminus L\) and difference. Two operations are specific to languages. Concatenation \(L_1 L_2 = \{xy : x \in L_1, y \in L_2\}\), and the Kleene star \(L^* = \{w_1 w_2 \cdots w_k : k \ge 0, \text{ each } w_i \in L\}\), the set of all concatenations of zero or more strings from L.

Why strings? Because any finite object a computer handles can be encoded as a string: a number in binary, a graph as a list of edges, a program as its source text, a database as a file. A computational problem then becomes a language. The decision problem 'is this number prime?' is the language \(\text{PRIMES} = \{\langle n \rangle : n \text{ is prime}\}\), where \(\langle n \rangle\) denotes some fixed encoding of n as a string. 'Does this graph have a path from s to t?' becomes the language of encodings of triples \(\langle G, s, t \rangle\) with such a path. Solving the problem means deciding membership in the language. This identification of problems with languages is the single most important modeling step in the subject, and it lets one theory cover arithmetic, graphs, logic and programs alike.

Encodings matter only up to reasonable translation. Writing a number in binary or in decimal changes the string but not which problems are easy or hard, because a machine can convert between them quickly. Writing it in unary, as n copies of a symbol, is different: the string becomes exponentially longer, and an algorithm that is fast in the length of a unary input may be slow in the length of a binary one. We will return to this point with the subset-sum problem in lesson 10. For now, whenever we write \(\langle X \rangle\) we mean any sensible encoding of X, and the results we prove will not depend on which one.

# Strings over {0, 1} in shortlex order: by length, then alphabetically.
# Every string gets a finite position, so the set of all strings is countable.
from itertools import count, product

def shortlex(alphabet):
    for n in count(0):
        for t in product(alphabet, repeat=n):
            yield "".join(t)

gen = shortlex("01")
first = [next(gen) for _ in range(15)]
print("first 15:", ["" if s == "" else s for s in first])
print("position of the empty string:", 0)

def index_of(w, k=2):
    # position of w in shortlex order over a k-letter alphabet {0..k-1}
    shorter = sum(k ** i for i in range(len(w)))
    return shorter + (int(w, k) if w else 0)

for w in ["", "0", "1", "00", "101", "1111", "0000000000"]:
    print(f"{w or 'empty':>10} -> position {index_of(w)}")
print("strings of length at most 20:", sum(2 ** i for i in range(21)))

first 15: ['', '0', '1', '00', '01', '10', '11', '000', '001', '010', '011', '100', '101', '110', '111']
position of the empty string: 0
     empty -> position 0
         0 -> position 1
         1 -> position 2
        00 -> position 3
       101 -> position 12
      1111 -> position 30
0000000000 -> position 1023
strings of length at most 20: 2097151

Machines as language recognizers

A model of computation is a precise definition of a class of machines, together with a rule saying which strings each machine accepts. The set of strings a machine M accepts is its language, \(L(M)\), and we say M recognizes that language. We will study a ladder of models, each more powerful than the last. Finite automata have a fixed, finite amount of memory: their current state. Pushdown automata add an unbounded stack, which can be read only at the top. Turing machines have an unbounded tape they can read and write anywhere. Each model corresponds to a class of languages, and each class has an equivalent description by grammars or expressions. The resulting hierarchy, named after the linguist Noam Chomsky, who described its grammar side in the 1950s, organizes much of the course.

The figure is a map of what is coming. Each inclusion is proper: there is a language in each ring that is not in the ring inside it, and we will prove each separation. The innermost separation, that \(\{a^n b^n : n \ge 0\}\) is context-free but not regular, uses the pumping lemma of lesson 4. The next, that \(\{a^n b^n c^n\}\) is decidable but not context-free, uses the pumping lemma for context-free languages in lesson 6. The halting problem is recognizable but not decidable, which is the central result of lesson 8, and its complement is not even recognizable. Outside the figure lies one more fact worth absorbing now: almost all languages are outside every ring, because there are uncountably many languages but only countably many machines.

Why most languages cannot be recognized

The counting argument needs two facts from CMPUT-272. First, \(\Sigma^*\) is countable: list strings in shortlex order, by length and then alphabetically, and every string appears at a finite position, as the program above shows. Second, the set of all languages, which is the power set \(\mathcal{P}(\Sigma^*)\), is uncountable. The proof is Cantor's diagonal argument. Suppose the languages could be listed as \(L_0, L_1, L_2, \ldots\), and list the strings as \(w_0, w_1, w_2, \ldots\). Define \(D = \{w_i : w_i \notin L_i\}\). For every i, D and \(L_i\) disagree about the string \(w_i\): if \(w_i \in L_i\) then \(w_i \notin D\), and if \(w_i \notin L_i\) then \(w_i \in D\). So D is not \(L_i\) for any i, contradicting the assumption that the list contained every language.

Every machine we will define, whether a finite automaton, a pushdown automaton or a Turing machine, has a finite description, which can be written as a string. So the set of machines of any kind is countable, and so is the set of languages they recognize. A countable set cannot cover an uncountable one. Therefore some languages, in fact almost all of them, are recognized by no machine. This is a non-constructive proof: it shows that unrecognizable languages exist without naming one. In lesson 8 we will run the diagonal argument again, this time on Turing machines themselves, and obtain a specific, natural problem that no machine can decide.

# Diagonalization: no list of languages can contain every language.
# Take any list L0, L1, L2, ... and strings w0, w1, w2, ... in shortlex order.
# Define D = { w_i : w_i is NOT in L_i }. Then D differs from every L_i at w_i.
from itertools import count, product

def shortlex(alphabet="01"):
    for n in count(0):
        for t in product(alphabet, repeat=n):
            yield "".join(t)

languages = [
    ("all strings",            lambda w: True),
    ("no strings",             lambda w: False),
    ("even length",            lambda w: len(w) % 2 == 0),
    ("ends in 1",              lambda w: w.endswith("1")),
    ("more 1s than 0s",        lambda w: w.count("1") > w.count("0")),
    ("palindromes",            lambda w: w == w[::-1]),
    ("binary value divisible by 3", lambda w: w != "" and int(w, 2) % 3 == 0),
    ("contains 00",            lambda w: "00" in w),
]
words = shortlex()
print(f"{'i':>2}  {'w_i':6} {'L_i':28} {'w_i in L_i':10} {'w_i in D'}")
for i, (name, member) in enumerate(languages):
    w = next(words)
    inside = member(w)
    print(f"{i:>2}  {w or 'eps':6} {name:28} {str(inside):10} {not inside}")
print("D disagrees with every listed language on the diagonal, so D is not in the list.")

 i  w_i    L_i                          w_i in L_i w_i in D
 0  eps    all strings                  True       False
 1  0      no strings                   False      True
 2  1      even length                  False      True
 3  00     ends in 1                    False      True
 4  01     more 1s than 0s              False      True
 5  10     palindromes                  False      True
 6  11     binary value divisible by 3  True       False
 7  000    contains 00                  True       False
D disagrees with every listed language on the diagonal, so D is not in the list.

Proof techniques we will use

Results in this course are proved with a small toolkit, most of which you have seen. Construction proves that an object exists by building it: to show that regular languages are closed under intersection we will construct, from two automata, a third that recognizes the intersection. Induction proves statements about all strings or all steps of a computation, typically on the length of the string or the number of steps. Contradiction assumes the opposite of the claim and derives an impossibility, and it is the shape of every pumping-lemma argument. Diagonalization, a special form of contradiction, builds an object that differs from every member of a list. Reduction shows that one problem is at least as hard as another by transforming instances of one into instances of the other, and it will carry most of the weight in the second half of the course.

A good proof in this subject separates two things: the idea and the bookkeeping. The idea of the product construction is one sentence: run both automata in parallel. The bookkeeping is a formal definition of the new states and transitions and an induction showing that after reading any string the product machine is in the pair of states the two machines would be in. You should be able to state the idea quickly and write the bookkeeping when asked. In lectures, worked examples and quizzes we will often give the idea in prose and then sketch the formal steps; on assignments, the expectation is a complete argument at the level of detail used in the worked examples.

Decision problems, recognizers and deciders

We will be precise about what it means to solve a problem. A machine decides a language L if, on every input, it halts and correctly answers whether the input is in L. A machine recognizes L if it halts and accepts exactly the strings in L, but on strings outside L it may either reject or run forever. For finite automata and pushdown automata the distinction does not arise in practice, because they read their input once and stop. For Turing machines it is fundamental. A recognizer for the halting problem is easy: simulate the given program and accept if it halts. A decider is impossible, because a decider would have to say no on programs that run forever, and no finite amount of simulation can confirm that.

Later we will measure not only whether a decider exists but how much time or memory it needs, as a function of the input length n. The resulting complexity classes, P, NP, PSPACE and others, refine the decidable ring of the hierarchy into a detailed landscape. The famous open question, whether \(\text{P} = \text{NP}\), asks whether every problem whose solutions can be checked quickly can also be solved quickly. It has been open since Stephen Cook and Leonid Levin independently framed it in the early 1970s, and it is one of the seven Millennium Prize Problems set by the Clay Mathematics Institute in 2000, with a one-million-US-dollar prize; as of October 2026 it remains unsolved.

How the course is organized

Lessons 2 to 4 study regular languages: finite automata, nondeterminism, regular expressions, closure properties and the tools for proving that a language is not regular. Lessons 5 and 6 study context-free languages: grammars, normal forms, parsing by dynamic programming, pushdown automata and their limits. Lesson 7 introduces Turing machines and the Church–Turing thesis. Lessons 8 and 9 study computability: decidable problems, the halting problem, reductions, Rice's theorem and other undecidable problems. Lessons 10 and 11 study complexity: time classes, NP-completeness, space classes and the hierarchy theorems. Lesson 12 surveys what lies beyond, from randomized and quantum computation to approximation and the practical success of SAT solvers on problems that are hard in theory.

Each lesson includes small Python programs. They are not proofs, but they make definitions concrete and let you test intuitions: simulating an automaton, building a parse table, running a Turing machine, or checking a reduction on a small instance. Use them as a laboratory. When a theorem says that every regular language has a pumping length, run the pumping checker and watch every decomposition fail for a language that is not regular. When a theorem says that SAT reduces to independent set, build the graph for a small formula and confirm that satisfying assignments and independent sets correspond. The code uses only the Python standard library and runs in a fraction of a second.

Worked examples