Subject 2 — Computer Science2.7

Formal Languages & Grammars

Alphabets, Strings, and Languages

Formal language theory begins with three foundational objects: alphabets, strings, and languages. These objects let us describe computation with precision rather than intuition.

Alphabet

An alphabet is a finite, non-empty set of symbols. We usually denote alphabets with capital Greek letters such as Sigma.

\Sigma = \{a, b\} \quad\text{or}\quad \Sigma = \{0,1\}

String (Word)

A string over an alphabet Sigma is a finite sequence of symbols from Sigma. The empty string is denoted by epsilon and has length zero.

\varepsilon \in \Sigma^* \qquad |\varepsilon| = 0

Language

A language over Sigma is any set of strings over Sigma. In other words, every language is a subset of Sigma star.

L \subseteq \Sigma^*

Core Notation

The notation below appears constantly in automata, grammars, and computability proofs.

Length of a string

The function |w| returns how many symbols are in w.

|abba| = 4 \qquad |01001| = 5

Power of an alphabet

Sigma to the power n means all strings of length exactly n over Sigma.

\Sigma^2 = \{aa,ab,ba,bb\} \quad\text{for}\quad \Sigma=\{a,b\}

Kleene star

Sigma star is the set of all finite strings over Sigma, including the empty string.

\Sigma^* = \bigcup_{n \ge 0} \Sigma^n

Kleene plus

Sigma plus is the set of all non-empty strings over Sigma.

\Sigma^+ = \bigcup_{n \ge 1} \Sigma^n = \Sigma^* \setminus \{\varepsilon\}

Worked Language Examples

Example A

All binary strings of even length.

L_1 = \{ w \in \{0,1\}^* \mid |w| \text{ is even} \}

Example B

All strings over a and b that end with ab.

L_2 = \{ w \in \{a,b\}^* \mid w \text{ ends with } ab \}

Example C

All strings with equal numbers of a and b. This language is not regular, but still a valid language over the alphabet.

L_3 = \{ w \in \{a,b\}^* \mid \#_a(w) = \#_b(w) \}

A language can be finite, infinite, regular, context-free, decidable, or undecidable. Those classifications come later; for now, language simply means a set of strings.

← Computer Science