Chapter 2 - Alphabets, Words, Languages, and Problem Representation

Computers work with text. Programs are text, data is stored as text (sequences of bits), and inputs/outputs are essentially text. This chapter introduces the formal language we need to talk about these “texts” precisely. This formalism is the bedrock upon which we will build all the core concepts of theoretical computer science.

2.1 Aims

This chapter has three main goals:

1. Introduce the fundamental vocabulary: We will define the core concepts of Alphabet, Word, and Language. These are the basic building blocks for describing information and computation.
2. Formalize Algorithmic Problems: We will use this new vocabulary to precisely define what an “algorithmic problem” is. We will focus on two crucial classes: Decision Problems and Optimization Problems.
3. Measure Information Content: We will explore the concept of text compressibility by introducing Kolmogorov Complexity. This powerful idea allows us to measure the information content of a word and provides a formal definition for the elusive concept of randomness.

2.2 Alphabets, Words, and Languages

Just like natural languages, the languages of computation start with symbols.

Alphabets and Words

Definition 2.1: Alphabet

An alphabet is a finite, non-empty set, usually denoted by $\Sigma$. The elements of an alphabet are called letters, characters, or symbols.

Examples:

• The Boolean alphabet: ${\Sigma }_{bool}=\{0,1\}$
• The Latin alphabet: ${\Sigma }_{lat}=\{a,b,c,\dots ,z\}$
• A keyboard alphabet: ${\Sigma }_{Tastatur}={\Sigma }_{lat}\cup \{A,\dots ,Z,\bigsqcup ,>,<,\dots ,!\}$, where $\bigsqcup$ is the space symbol.
• The alphabet for m-adic numbers: ${\Sigma }_m=\{0,1,\dots ,m-1\}$ for any $m\ge 1$.

Definition 2.2: Word

A word (or string) over an alphabet $\Sigma$ is a finite sequence of letters from $\Sigma$.

• The empty word, denoted by $\lambda$ (or $ϵ$), is the sequence with zero letters.
• The length of a word $w$, denoted $|w|$, is the number of letters in the sequence.
• ${\Sigma }^{\ast }$ is the set of all possible words over $\Sigma$.
• ${\Sigma }^{+}={\Sigma }^{\ast }\setminus \{\lambda \}$ is the set of all non-empty words.

For example, 010011 is a word over ${\Sigma }_{bool}$ with length $|010011|=6$. The set $({\Sigma }_{bool}{)}^{\ast }$ contains all possible binary strings: $\{\lambda ,0,1,00,01,10,11,000,\dots \}$.

Representing Objects as Words

We can use words to represent virtually any object of interest in computation.

• Numbers: A binary word $x=x_1{x}_2\dots x_n$ can represent the natural number $\text{Nummer}(x)={\sum }_{i=1}^n{x}_i\cdot 2^{n-i}$. We denote the standard binary representation of a number $m$ as $\text{Bin}(m)$.
• Sequences of Numbers: A sequence of numbers $a_1,a_2,\dots ,a_m$ can be represented as a single word using a separator symbol, e.g., $\text{Bin}(a_1)\#\text{Bin}(a_2)\#\dots \#\text{Bin}(a_m)$ over the alphabet $\{0,1,\#\}$.
• Graphs: A directed graph $G=(V,E)$ with $n$ vertices can be represented by its $n\times n$ adjacency matrix. By writing out the rows of the matrix separated by a #, we get a single word representing the graph. For example, the graph in Figure 2.1 has the adjacency matrix: $$\left(\begin{array}{cccc}0& 0& 1& 1\\ 0& 0& 1& 1\\ 0& 1& 0& 1\\ 0& 0& 0& 0\end{array}\right)$$ This can be encoded as the word 0011#0011#0101#0000#.

Operations on Words and Subwords

Definition 2.3: Concatenation

The concatenation of two words $x$ and $y$ is the word $xy$ formed by appending $y$ to the end of $x$.

Concatenation is associative, i.e., $(uv)w=u(vw)$. The set of all words ${\Sigma }^{\ast }$ with the concatenation operation forms a mathematical structure called a monoid, with the empty word $\lambda$ as the identity element ($x\lambda =\lambda x=x$).

Definition 2.6: Subwords

Let $w$ be a word over $\Sigma$.

• $v$ is a substring (Teilwort) of $w$ if $w=xvy$ for some words $x,y$.
• $v$ is a prefix of $w$ if $w=vy$ for some word $y$.
• $v$ is a suffix of $w$ if $w=xv$ for some word $x$.

For example, in abcabcabc, abc is a prefix, cabc is a substring, and bc is a suffix.

Languages

Definition 2.9: Language

A language $L$ over an alphabet $\Sigma$ is any subset of ${\Sigma }^{\ast }$.

This is a very general definition. Any set of strings is a language.

Examples of languages over $\Sigma =\{a,b\}$:

• $L_1=\varnothing$ (the empty language)
• $L_2=\{\lambda \}$ (the language containing only the empty word)
• $L_3=\{a^n{b}^n\mid n\in \mathbb{N}\}=\{\lambda ,ab,aabb,aaabbb,\dots \}$
• $L_4=\{w\in \{a,b{\}}^{\ast }\mid |w{|}_a=|w{|}_b\}$ (all words with an equal number of a’s and b’s)

We can perform operations on languages:

• Concatenation: $L_1{L}_2=\{vw\mid v\in L_1,w\in L_2\}$
• Kleene Star: $L^{\ast }={\bigcup }_{i\ge 0}{L}^i=L^0\cup L^1\cup L^2\cup \dots$, where $L^0=\{\lambda \}$. The Kleene star represents repeating words from the language zero or more times.

Distributivity of Language Operations

Concatenation distributes over union, but not over intersection.

• Union (holds): $L_1(L_2\cup L_3)=L_1{L}_2\cup L_1{L}_3$
• Intersection (does not hold): In general, $L_1(L_2\cap L_3)\ne L_1{L}_2\cap L_1{L}_3$. We only have the inclusion $L_1(L_2\cap L_3)\subseteq L_1{L}_2\cap L_1{L}_3$. Why? A word in $L_1{L}_2\cap L_1{L}_3$ might be formed by concatenating a word from $L_1$ with one from $L_2$, and also by concatenating a different word from $L_1$ with one from $L_3$. The two decompositions might not be the same.

2.3 Algorithmic Problems

Using our new vocabulary, we can now formalize what we mean by an “algorithmic problem.” We’ll start with the most fundamental type.

Decision Problems

Definition 2.11: Decision Problem

A decision problem is a pair $(\Sigma ,L)$, where $\Sigma$ is an alphabet and $L\subseteq {\Sigma }^{\ast }$ is a language.
The problem is to determine, for any given word $x\in {\Sigma }^{\ast }$, whether or not $x$ is in $L$.

An algorithm solves (or decides) the problem $(\Sigma ,L)$ if it halts on every input $x$ and outputs “yes” (or 1) if $x\in L$, and “no” (or 0) if $x\notin L$.

A language for which such an algorithm exists is called recursive or decidable.

Intuition

Think of a decision problem as a membership test:

• The alphabet $\Sigma$ tells us what symbols can appear in a valid input.
• Each word $x\in {\Sigma }^{\ast }$ is just a possible encoding of an input.
• The language $L$ is the set of all yes-instances of the problem.
  So solving the problem = checking whether the given word is in $L$.

Examples:

• PRIMALITY:

  • Alphabet: ${\Sigma }_{bool}=\{0,1\}$
  • Word: $\text{Bin}(13)=1101$
  • Language: $\{\text{Bin}(n)\mid n\text{ is prime}\}$
  • Question: “Is 13 prime?” ⇨ check if $1001\in L$

• Hamiltonian Cycle (HK):

  • Alphabet: $\{0,1,\#\}$
  • Word: a binary encoding of a graph, e.g., 011#101#...
  • Language: all encodings of graphs that have a Hamiltonian cycle.
  • Question: “Does this graph have a Hamiltonian cycle?”

• SAT (Satisfiability):

  • Alphabet: ${\Sigma }_{logic}=\{\text{symbols for Boolean formulas}\}$
  • Word: $(x\vee \neg y)\wedge (y\vee z)$ encoded as a string
  • Language: all formulas that are satisfiable.
  • Question: “Is this formula satisfiable?”

Optimization Problems

Many real-world problems are not simple yes/no questions. They involve finding the best solution among many possibilities.

Definition 2.14: Optimization Problem

An optimization problem $U$ is formally a 6-tuple $({\Sigma }_I,{\Sigma }_O,L,M,\text{cost},\text{goal})$, where:

• ${\Sigma }_I,{\Sigma }_O$ are the input and output alphabets.
• $L\subseteq {\Sigma }_I^{\ast }$ is the language of valid problem instances.
• $M$ maps an instance $x\in L$ to a set $M(x)$ of feasible solutions.
• $\text{cost}$ assigns a cost to each feasible solution.
• $\text{goal}$ is either Minimum or Maximum.

An algorithm solves $U$ if for any instance $x$, it returns a feasible solution $y\in M(x)$ with optimal cost.

Intuition

For optimization problems, the language $L$ just tells us what counts as a valid instance.
The “word” is the encoding of that instance.
The solution set $M(x)$ contains all possible valid answers, and the algorithm’s job is to pick the one with the best cost according to the goal.

Example: Traveling Salesman Problem (TSP)

• Instance Language $L$: All encodings of weighted complete graphs.
• Word $x$: e.g., a matrix encoding of a graph $(G,c)$.
• Feasible Solutions $M(G,c)$: All Hamiltonian cycles in $G$.
• Cost: Total weight of the cycle.
• Goal: Minimize cost.

Other examples:

• Shortest Path:

  • Word = encoding of a graph + source + target.
  • $M(x)$ = all paths between source and target.
  • Cost = length of path.
  • Goal = Minimum.

• Knapsack:

  • Word = list of items with weights/values and a capacity.
  • $M(x)$ = all subsets of items that fit in the capacity.
  • Cost = total value.
  • Goal = Maximum.

Other Problem Types

• Function Problems: Compute a function $f:{\Sigma }_1^{\ast }\to {\Sigma }_2^{\ast }$.

  • Example: FACTORING
    • Alphabet: $\{0,1\}$
    • Word: $\text{Bin}(21)=10101$
    • Function: $f(21)=(3,7)$
    • Output is not just yes/no, but the actual factors.

• Enumeration Problems: List all the words in a language $L$.

  • Example: ALL PRIMES
    • Alphabet: $\{0,1\}$
    • Language: all encodings of prime numbers.
    • Task: output $2,3,5,7,11,\dots$

Intuition

• Function problems: “don’t just tell me yes/no, give me the actual answer.”
• Enumeration problems: “list all solutions, not just one.”

2.4 Kolmogorov Complexity

How can we measure the “information content” of a single word? The intuitive idea is that a string is simple (low information) if it has a short description, and complex (high information) if it doesn’t. The string 00...0 ($n$ times) can be described as “n zeros,” while a random-looking string seems to have no description shorter than the string itself.

This leads to Kolmogorov’s brilliant insight: the ultimate description of a string is a program that generates it.

Definition 2.17: Kolmogorov Complexity

The Kolmogorov Complexity of a word $x$, denoted $K(x)$, is the length of the shortest program (encoded as a binary string) in a fixed universal programming language (e.g., Pascal, Python) that generates $x$ as its output.

This definition is surprisingly robust.

• Invariance Theorem: The choice of programming language doesn’t significantly change the complexity. For any two languages A and B, there is a constant $c_{A,B}$ such that for any string $x$, $|K_A(x)-K_B(x)|\le c_{A,B}$. The complexity is an intrinsic property of the string, not the language used to describe it.
• Incompressible Strings: For any length $n$, there exist strings $x$ with $|x|=n$ such that $K(x)\ge n$. A simple counting argument shows this: there are $2^n$ strings of length $n$, but only $2^n-2$ programs of length less than $n$. There simply aren’t enough short programs to describe every long string.

Applications of Kolmogorov Complexity

1. Defining Randomness: Kolmogorov complexity gives us a formal way to define what it means for a string to be random.

   A string $x$ is random if it is incompressible, i.e., $K(x)\ge |x|$. This captures the idea of “no pattern” or “no simple description.”

2. Proving Lower Bounds: It can be used to prove that certain problems are hard. For example, one can prove a weaker version of the Prime Number Theorem by arguing that if primes were too sparse, one could create short descriptions for many numbers (via their prime factorization), which would contradict the existence of incompressible numbers.

3. Connecting Computability and Complexity: If a language $L$ is decidable, then the Kolmogorov complexity of its words (ordered canonically) cannot grow arbitrarily. Specifically, for the $n$-th word $z_n$ in $L$, we have $K(z_n)\le {\log }_2(n)+c$. This is because we can write a short program that, given $n$, finds and prints $z_n$. This provides a powerful tool for proving that certain languages are not decidable.

2.5 Summary and Outlook

This chapter laid the essential groundwork for the rest of our study.

• We defined alphabets, words, and languages as the formal tools to describe data and problems.
• We categorized algorithmic tasks into decision, optimization, and other types of problems.
• We introduced Kolmogorov complexity as a robust measure of the information content of a string, which also provides a formal definition of randomness.

The study of these fundamental concepts is the core of Formal Language Theory, one of the oldest and most foundational areas of computer science. With this language in hand, we are now ready to explore the machines that process it, starting with the simplest model: the finite automaton.

Next Chapter: Chapter 3 - Finite Automata