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

Source: https://skills101.in/learn/theory-of-computation/toc-basics-languages — Skills101 free tutorial (Theory of Computation (TOC)). Updated 2026-11-09.

**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

| Term | Meaning | Example |
|---|---|---|
| **Alphabet Σ** | a finite set of symbols | Σ = {0, 1}, or {a, b} |
| **String** | a finite sequence of symbols | `0110`, `abba` |
| **Length \|w\|** | number of symbols | \|0110\| = 4 |
| **Empty string ε** | the string of length 0 | \|ε\| = 0 |
| **Σ*** (Kleene star) | **all** strings over Σ, including ε | {ε, 0, 1, 00, 01, …} |
| **Σ⁺** | all non-empty strings | Σ* minus ε |
| **Language L** | **any** set of strings over Σ (a subset of Σ*) | binary strings ending in 1 |

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.

```python
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)
```

```text
Σ* 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

![Chomsky hierarchy as nested sets: regular languages inside context-free, inside context-sensitive, inside recursively enumerable; each with its grammar type and machine: finite automaton, pushdown automaton, linear bounded automaton and Turing machine](https://skills101.in/learn-img/theory-of-computation/chomsky-hierarchy.svg)

| Type | Language class | Machine | Memory | Example | Used in |
|---|---|---|---|---|---|
| 3 | **Regular** | Finite automaton (DFA/NFA) | none beyond the state | strings ending in `01` | regex, lexers, input validation |
| 2 | **Context-free** | Pushdown automaton (PDA) | a stack | balanced brackets, aⁿbⁿ | programming-language syntax, parsers |
| 1 | **Context-sensitive** | Linear bounded automaton | tape limited to input size | aⁿbⁿcⁿ | — |
| 0 | **Recursively enumerable** | Turing machine | unlimited tape | anything computable | every algorithm |

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).


Practice quiz and free certificate: https://skills101.in/learn/theory-of-computation/toc-basics-languages