Introduction
The theory of computation asks a precise question: which problems can a machine solve, and how much power does the machine need? To ask that precisely, we first need a precise way to state a problem. The trick that the whole subject rests on is simple: every yes-or-no problem is a set of strings.
"Is this number divisible by 3?" becomes the set of all binary strings whose value is divisible by 3. "Is this password valid?" becomes the set of all valid passwords. A machine solves the problem when it can tell, for any string, whether the string is in the set. This lesson builds that vocabulary, and every later lesson uses it.
How it works
An alphabet Σ is a finite set of symbols. Binary uses Σ = {0, 1}; many of our examples use Σ = {a, b}. A string (or word) over Σ is a finite sequence of symbols, such as abba. Its length |w| counts symbols, so |abba| = 4.
The empty string ε has no symbols and length 0. It is a real string, not "nothing": the set {ε} contains one string. The empty language ∅ contains no strings at all.
Strings combine:
- Concatenation joins two strings: if x =
aband y =ba, then xy =abba. Joining with ε changes nothing: xε = x. - Power repeats a string: w³ = www, and w⁰ = ε.
- Reverse reads it backwards: the reverse of
abbisbba.
A language is any set of strings over Σ. Σ* is the set of all strings, including ε; it is infinite, but each string in it is finite. A language can be given by listing its strings, when it is finite, or by a rule, such as "strings with as many a's as b's".
Languages combine too:
- Union L ∪ M holds strings in either language.
- Concatenation L·M holds every xy with x in L and y in M.
- Star L* holds every concatenation of zero or more strings from L, so it always contains ε.
In Python, a string is a str, ε is "", a finite language is a set, and a rule is a function that returns True or False. itertools.product lists every string of a given length.
word = "abb"
print("length:", len(word))
print("reverse:", word[::-1])
print("word squared:", word * 2)
print("prefixes:", [word[:i] or "ε" for i in range(len(word) + 1)])Syntax
sigma = ["a", "b"] # the alphabet
word = "abba" # a string; "" is ε
len(word), word[::-1], word * 3 # length, reverse, power
{x + y for x in A for y in B} # the concatenation A·B
"".join(p) for p in itertools.product(sigma, repeat=n) # every string of length n
Example
from itertools import product
sigma = ["a", "b"]
def strings_up_to(n):
words = [""]
for length in range(1, n + 1):
for letters in product(sigma, repeat=length):
words.append("".join(letters))
return words
def equal_ab(word):
return word.count("a") == word.count("b")
all_words = strings_up_to(3)
print("Strings of length 0 to 3:", len(all_words))
in_language = [w if w else "ε" for w in all_words if equal_ab(w)]
print("Equal numbers of a and b:", in_language)
A = {"a", "ab"}
B = {"b", ""}
print("A·B =", sorted({x + y for x in A for y in B}))Line by line
strings_up_to(3)starts with ε and adds every string of length 1, 2 and 3, usingproductwithrepeat=length.- Over two symbols there are 1 + 2 + 4 + 8 = 15 strings of length 0 to 3.
equal_abis the rule for the language "as many a's as b's". Filtering keeps ε,abandba; ε is printed as the symbol ε so that it is visible.- The concatenation A·B takes every word of A followed by every word of B. Because B contains ε, the words of A themselves appear, and the duplicate
abappears only once in a set.
Expected result
Strings of length 0 to 3: 15
Equal numbers of a and b: ['ε', 'ab', 'ba']
A·B = ['a', 'ab', 'abb']
In the real world
Every input a program accepts forms a language: valid email addresses, JSON documents, Python programs. Compilers start by deciding which strings are valid tokens, network devices recognise packet formats, and search tools match text against patterns. The theory lets us say exactly which kinds of machine can recognise which languages.
Common mistakes
- Treating ε as "no string": {ε} has one member, ∅ has none, and ∅·L is ∅ while {ε}·L is L.
- Forgetting that Σ is infinite* while each of its strings is finite.
- Expecting a set to keep order: sort the strings before printing them.
- Confusing L with Σ**: L* uses only words of L, glued together.
Best practices
- Represent ε as
""in code, but print it as ε, so that it is visible. - Write a language's rule as a small function, and test it on short strings first.
- Generate strings in order of length when exploring a language, so that small cases come first.
Summary
An alphabet is a finite set of symbols, a string is a finite sequence of them, and a language is a set of strings. ε is the string of length 0, and Σ* is every string. Union, concatenation and star build new languages, and a yes-or-no problem is the same thing as a language.
Quick check
Key takeaways
- A language is just a set of strings, and a decision problem is a language.
- ε (a string) is different from ∅ (a language with no strings).
- Concatenation and star build big languages from small ones.
Practice problems for this lesson
My notes
Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.