Theory of Computation Basics — Alphabets, Strings, Languages and the Chomsky Hierarchy

Theory of Computation asks two big questions: what problems can a computer solve at all, and how much power does a machine need to solve them? The answers explain why regex can't match nested brackets, why compilers have a lexer and a parser, and why no program can detect every infinite loop. It's also a guaranteed GATE topic.

1. Alphabets, strings, languages

Operations on strings: concatenation (ab · ba = abba), reverse (abbᴿ = bba), substring/prefix/suffix.

A language can be finite ({a, ab}) or infinite (all palindromes). Most interesting ones are infinite — so we need a finite description of an infinite set: a machine or a grammar.

from itertools import product

sigma = "01"
def strings_up_to(n):
    for k in range(n + 1):
        for t in product(sigma, repeat=k):
            yield "".join(t)

all_strings = list(strings_up_to(3))
print("Σ* up to length 3:", ["ε" if s == "" else s for s in all_strings])
print("count:", len(all_strings), "= 1 + 2 + 4 + 8")

ends_in_1 = [s for s in all_strings if s.endswith("1")]
palindromes = [s for s in all_strings if s == s[::-1] and s]
print("L1 = ends in 1:", ends_in_1)
print("L2 = palindromes:", palindromes)

Σ* up to length 3: ['ε', '0', '1', '00', '01', '10', '11', '000', '001', '010', '011', '100', '101', '110', '111']
count: 15 = 1 + 2 + 4 + 8
L1 = ends in 1: ['1', '01', '11', '001', '011', '101', '111']
L2 = palindromes: ['0', '1', '00', '11', '000', '010', '101', '111']

2. Operations on languages

For languages L₁, L₂:

• Union L₁ ∪ L₂, intersection, complement (Σ* − L)
• Concatenation L₁L₂ = {xy | x ∈ L₁, y ∈ L₂}
• Kleene star L* = ε ∪ L ∪ LL ∪ LLL ∪ … (zero or more pieces from L)

Example: L = {ab} → L* = {ε, ab, abab, ababab, …}.

3. Problems as languages

TOC turns every yes/no question into membership in a language:

• "Is this number prime?" → is the binary string in L = {binary representations of primes}?
• "Is this Java program syntactically valid?" → is it in L = {valid Java programs}?
• "Does this program halt?" → is ⟨program, input⟩ in L_HALT?

A machine accepts (or recognises) a language if it says "yes" exactly for the strings in it. Different machine types have different power.

4. The Chomsky hierarchy

Each class strictly contains the one above it: every regular language is context-free, but aⁿbⁿ is context-free and not regular; aⁿbⁿcⁿ is context-sensitive and not context-free.

The rest of this track climbs the hierarchy: finite automata (lessons 2–5), context-free grammars and PDAs (lesson 6), Turing machines (lesson 7), and the limits of computation (lesson 8).

5. Why programmers should care

• Regex engines are finite automata — they can't match arbitrarily nested structures like ((())) or HTML. Use a parser.
• Compilers: the lexer uses regular languages (tokens), the parser uses context-free grammars (syntax).
• Validation and protocols: state machines model login flows, order status, network protocols.
• Limits: some problems (halting) are unsolvable by any program — knowing that saves you from attempting them.

Common mistakes

• Confusing ε (the empty string) with ∅ (the empty language, which contains no strings at all).
• Forgetting that Σ* includes ε.
• Thinking a "language" must be a programming language — in TOC it's just a set of strings.

Quick recap

• Alphabet Σ (finite symbols) → strings → Σ* (all strings, incl. ε) → a language is any subset of Σ*.
• Language operations: union, intersection, complement, concatenation, Kleene star.
• Every decision problem = a language membership question.
• Chomsky hierarchy: regular (FA) ⊂ context-free (PDA) ⊂ context-sensitive (LBA) ⊂ recursively enumerable (TM).