4.6.1 · D1Theory of Computation

Foundations — Alphabet, string, language — formal definitions

1,864 words8 min readBack to topic

Before you can read a single line of the parent note, you must be fluent in a handful of tiny symbols. Below we introduce them one at a time, each with a plain-words meaning, a picture, and the reason the topic needs it. Nothing here assumes you have seen any of it before.


0. The most basic idea: a set

The picture: think of a set as a bag. You can peek inside and see which things are in it, but the bag has no "first" or "second" slot — order is meaningless, and you can't hold two identical copies.

Why the topic needs it. The alphabet is a set, and (spoiler) a language is a set too. Every "how many things are inside?" question in the parent note is really a set-counting question, so we must be rock-solid on what a set is.

Figure — Alphabet, string, language — formal definitions

Notice already a subtle thing the parent leans on: (empty bag) is very different from (a bag containing one empty bag). We return to this on the third floor.

Why the topic needs it. The definition of language is literally "" — a language is any sub-collection of all-possible-words. Without you cannot read that line.


1. Symbol and alphabet

The picture: is the box of rubber stamps you're allowed to use. Nothing outside the box exists for this problem.

Why finite & non-empty? A real machine can only be built to recognise finitely many distinct inputs — an infinite stamp-box could never fit inside a finite device. And an empty box lets you stamp nothing at all, giving a theory with no words to study.


2. Sequence, order, and the string

Here a new idea enters that a plain set cannot express: order and repetition.

Figure — Alphabet, string, language — formal definitions

The picture: a string is a row of stamped letters on a strip of paper. The strip has numbered slots; slot order changes the word.

Why the topic needs it. Everything a computer reads — a password, a program, a DNA read — is an ordered row of symbols. The string is the object of study; the alphabet just supplies its ink.


3. Gluing words: concatenation

Why the topic needs it. This is the only building operation on strings; the parent's length rule, powers, reversal and even the language operations are all defined through it.

Because gluing two strips just puts their marks in a longer row, the counts add: And taping on a blank strip changes nothing, which is why — the empty string is the "do-nothing" glue.


4. All possible words: the star

Now we build the biggest object the parent uses. It needs one more piece of notation.

Figure — Alphabet, string, language — formal definitions

The picture: picture bags stacked by length — the bag holds only , the bag holds the single letters, the bag holds the two-letter words, and so on forever. dumps all these bags into one giant collection.

Why the topic needs it. is "the universe of all words you could ever type". A language is then simply a chosen sub-collection of this universe — which is exactly why the next floor needs .


5. The club: language

Why the topic needs it. This is the payoff. Every machine later in the course — Finite Automata (DFA NFA), Regular Expressions, Context-Free Grammars — is a bouncer that answers "is this word on the list?". The families you'll meet (Regular Languages, and the limits shown by the Pumping Lemma, plus the Countability and Diophantine Diagonalization argument that most languages have no machine at all) are all classifications of which subsets of a machine can handle.


Prerequisite map

Set and braces

Membership and size

Subset relation

Empty set

Alphabet Sigma

Ordered sequence

String and length

Empty string epsilon

Concatenation

Kleene star Sigma-star

Language

Topic 4.6.1


Equipment checklist

What do the curly braces build, and does order matter inside them?
A set — an unordered collection of distinct members; order does not matter.
What does mean?
is a member of the set .
What is when is a set?
The number of members (cardinality) of .
What is and what is ?
The empty set (no members); .
State when holds.
When every member of is also a member of .
Give the three defining properties of an alphabet .
Finite, non-empty, set of symbols.
How does a string differ from a set of symbols?
A string is ordered and allows repeats; a set is unordered with distinct members.
What is and its length?
The empty string (blank word); .
What does concatenation do, and what is ?
Glues onto the end of ; .
What does contain that does not?
The empty string (the length-0 words).
In one line, what is a language?
Any subset of — i.e. a set of strings.