Alphabets, strings and languages

Why it exists

Computer science asks what can be computed and how hard it is. To say anything exact, a problem has to become a mathematical object. The object is a language: a set of strings. "Is this number prime?" becomes "is this string, the binary form of the number, in the language of primes?". "Is this program syntactically correct?" is membership in the language of valid programs. Every machine of this subject (finite automata, pushdown automata, Turing machines) is a device that decides, or recognises, membership in a language, and every grammar generates one. This page fixes the notation, which GATE uses without explanation in every later question.

Prerequisites

None. This is a starting point.

Nothing: sets and functions from school mathematics are enough.

Precise definitions

Alphabet. A finite, non-empty set $\Sigma$ of symbols (letters, digits, bits). Examples: $\{0, 1\}$, $\{a, b\}$, the ASCII characters.

String (word). A finite sequence of symbols of $\Sigma$. The length $|w|$ is the number of symbols. The empty string $\varepsilon$ has length $0$ (it is a string, not a symbol, and not the empty set). $|w|_a$ denotes the number of occurrences of the symbol $a$ in $w$.

Concatenation. $xy$ is $x$ followed by $y$; $|xy| = |x| + |y|$. It is associative ($(xy)z = x(yz)$), has the identity $\varepsilon$ ($\varepsilon w = w \varepsilon = w$), and is not commutative ($ab \ne ba$). $w^n$ is $w$ concatenated $n$ times, $w^0 = \varepsilon$.

$\Sigma^n$ and $\Sigma^*$. $\Sigma^n$ is the set of all strings of length $n$; $\Sigma^* = \Sigma^0 \cup \Sigma^1 \cup \Sigma^2 \cup \cdots$ is the set of all strings (including $\varepsilon$), and $\Sigma^+ = \Sigma^* \setminus \{\varepsilon\}$. For $|\Sigma| = k$: $|\Sigma^n| = k^n$. $\Sigma^*$ is infinite but countable: its strings can be listed in order of length, and alphabetically within a length (shortlex order).

Parts of a string. $x$ is a prefix of $w$ if $w = xy$ for some $y$; a suffix if $w = yx$; a substring (factor) if $w = yxz$ (a contiguous piece); a subsequence if its symbols appear in $w$ in the same order but not necessarily next to each other. Every prefix, suffix and substring is a subsequence; the converse is false.

Language. Any subset $L \subseteq \Sigma^*$. It may be finite or infinite. Examples over $\{0, 1\}$: the binary strings that end with $01$; the strings with equally many $0$s and $1$s; the binary representations of prime numbers.

Operations on languages ($A, B \subseteq \Sigma^*$):

• union $A \cup B$, intersection $A \cap B$, difference $A \setminus B$;
• complement $\overline{A} = \Sigma^* \setminus A$ (it depends on the alphabet);
• concatenation $AB = \{xy : x \in A,\ y \in B\}$ and powers $A^0 = \{\varepsilon\}$, $A^{n+1} = A^n A$;
• Kleene star $A^* = A^0 \cup A^1 \cup A^2 \cup \cdots$ (any number of strings of $A$, including none), and $A^+ = A A^* = A^1 \cup A^2 \cup \cdots$;
• reversal $A^R = \{w^R : w \in A\}$.

Decision problems and languages. A yes/no problem on inputs written as strings is the language of the inputs whose answer is yes. "Deciding" or "recognising" the problem means deciding or recognising the language.

How it works

Counting strings and languages

For an alphabet of $k$ symbols there are exactly $k^n$ strings of length $n$ and $(k^{n+1} - 1)/(k - 1)$ strings of length at most $n$ (for $k = 2$: $2^{n+1} - 1$). A language is a set of strings, so it can be counted length by length. The table gives, for languages over $\{0, 1\}$, how many strings of each length belong to each language; each number was found by running a machine for the language on all strings of that length and was confirmed by a second method (a dynamic programme over the machine's states).

The first column is $2^n$; "ends with $01$" has $2^{n-2}$ strings of length $n \ge 2$ (fix the last two symbols); "has an even number of $1$s" has $2^{n-1}$ strings of each length $n \ge 1$ (half of all strings); "length divisible by 3" has $2^n$ strings when $n$ is a multiple of $3$ and none otherwise.

A string with $n$ symbols has:

• exactly $n + 1$ prefixes and $n + 1$ suffixes (counting $\varepsilon$ and the string itself);
• at most $n(n+1)/2 + 1$ distinct substrings (one for each pair of end positions, plus $\varepsilon$), with equality when all symbols are different; the string $abc$ has $7$, the string $aaa$ only $4$ ($\varepsilon$, $a$, $aa$, $aaa$);
• at most $2^n$ distinct subsequences (one for each subset of positions), again with equality when all symbols are different ($abc$ has $8$).

Languages are uncountably many. $\Sigma^*$ is countable, but the set of all subsets of $\Sigma^*$ (all languages) is uncountable (Cantor's diagonal argument). Machines and grammars are finite descriptions, and there are only countably many of those. So most languages have no finite description at all, and in particular most languages cannot be recognised by any program. This is why the limits of computation (undecidability) exist.

The operations in practice

Take $A = \{a, ab\}$ and $B = \{b, \varepsilon\}$. Then $AB = \{ab, a, abb, ab\} = \{a, ab, abb\}$: three strings, not four, because $a \cdot b$ and $ab \cdot \varepsilon$ coincide. In general $|AB| \le |A||B|$. For $L = \{a, bb\}$ the star $L^*$ contains $\varepsilon$, $a$, $aa$, $bb$, $aaa$, $abb$, $bba$, and so on: the strings that can be cut into pieces $a$ and $bb$; the number of such strings of length $n$ is $1, 1, 2, 3, 5, 8, 13, \ldots$ (a Fibonacci number: the string either ends with $a$ or with $bb$).

The empty language and the empty string are different and exam questions use the difference:

Also: $(A \cup B)^*$ is not $A^* \cup B^*$ (the first contains $ab$ for $A = \{a\}$, $B = \{b\}$, the second does not); $\overline{A \cup B} = \overline{A} \cap \overline{B}$ (De Morgan); $(AB)^R = B^R A^R$ (the order reverses).

Worked examples

Cheat box

Traps and GATE patterns

Connections

A language is the thing a DFA accepts, a grammar generates and a regular expression denotes. The counting of strings reappears in the pumping arguments and in the proof that some problems are undecidable.

PYQs

Let S be the set of all ternary strings defined over the
alphabet {a, b, c}. Consider all strings in S that contain at
least one occurrence of two consecutive symbols, that is,
"aa", "bb" or "cc". The number of such strings of length 5
that are possible is _______. (Answer in integer)

Given a language L, define Li as follows :
L0 = {ε}
Li = Li-1 . L for all i > 0 The order of a language L is
defined as the smallest k such that Lk = Lk+1 . Consider the
language L1 (over alphabet 0) accepted by the following
automation.

The order of L1 is_______.

Given the language L ={ab,aa,baa}, which of the
following strings are in L*?
1)abaabaaabaa
2)aaaabaaaa
3)baaaaabaaaab
4)baaaaabaa

Self-check

Revision card

References