Introduction to Theory of Computation

Theory of Computation asks what problems machines can solve at all, and with how much memory. It studies simple mathematical models of computers (automata), the languages they recognise, and the grammars that generate those languages.

Alphabets, strings and languages

• An alphabet Σ is a finite, non-empty set of symbols, such as Σ = {0, 1} or Σ = {a, b}.
• A string over Σ is a finite sequence of symbols: 0110, abba. The empty string is written ε, and |w| is the length of w (|ε| = 0).
• Σ^k is the set of all strings of length k; there are |Σ|^k of them. Σ* is the set of all strings (including ε), and Σ⁺ = Σ* − {ε}.
• A language is any set of strings over Σ, that is, any subset of Σ*. It can be finite ({ε, 01, 10}) or infinite ({0ⁿ1ⁿ | n ≥ 0}).

Two special languages are easy to confuse: ∅ (no strings at all) and {ε} (exactly one string, the empty one).

For a string w: a prefix is a start of w, a suffix an end, and a substring a contiguous piece. A string of length n has n + 1 prefixes and n + 1 suffixes (counting ε and w itself), and at most n(n + 1)/2 + 1 distinct substrings.

Operations on languages

Note that ∅* = {ε} and ∅L = ∅ for any L, while {ε}L = L.

from itertools import product

def concat(A, B):
    return {x + y for x in A for y in B}

def power(L, k):
    result = {""}
    for _ in range(k):
        result = concat(result, L)
    return result

L1, L2 = {"a", "ab"}, {"b"}
print(sorted(concat(L1, L2)))
print(sorted(power(L1, 2)))
print("strings of length 3 over {0,1}:", len(list(product("01", repeat=3))))
star_up_to_3 = set().union(*(power(L1, k) for k in range(4)))
print("L1* up to 3 factors:", sorted(star_up_to_3, key=lambda s: (len(s), s)))

['ab', 'abb']
['aa', 'aab', 'aba', 'abab']
strings of length 3 over {0,1}: 8
L1* up to 3 factors: ['', 'a', 'aa', 'ab', 'aaa', 'aab', 'aba', 'aaab', 'aaba', 'abaa', 'abab', 'aabab', 'abaab', 'ababa', 'ababab']

The Chomsky hierarchy

Languages are classified by the kind of machine that recognises them, or equivalently the kind of grammar that generates them. Each class strictly contains the one below it.

Typical examples:

• Regular: strings with an even number of 0s; strings ending in 01; aⁿbᵐ.
• Context-free but not regular: aⁿbⁿ; balanced parentheses; palindromes.
• Context-sensitive but not context-free: aⁿbⁿcⁿ; ww (a string followed by a copy of itself).
• Recursively enumerable but not recursive: the halting problem.
• Not even recursively enumerable: the complement of the halting problem.

Recognising and deciding

A machine accepts a language L if it accepts exactly the strings of L. For Turing machines there is an important difference:

• L is recursive (decidable) if some machine accepts every string in L and rejects (halts saying no) every string not in L.
• L is recursively enumerable (semi-decidable) if some machine accepts every string in L, but on strings not in L it may run forever.

Finite automata and PDAs always finish after reading their input, so their languages are all decidable. The later lessons of this track build up the hierarchy from the bottom: finite automata and regular expressions, then context-free grammars and PDAs, then Turing machines and the limits of computation.

Practice questions