Chapter 02 of 34

Alphabets, Strings & Languages

Every subject has a small vocabulary that everything else is built on. In geometry it is points and lines; in TOC it is symbols, strings and languages. In Introduction to Theory of Computation we said that every yes/no problem can be written as a language and every machine is judged by the language it accepts. Before we can build a single machine, we need these words to mean exactly one thing each.

This chapter defines alphabets, strings and languages precisely, covers the operations on them (concatenation, reversal, powers, Kleene star and more), and solves the counting questions that GATE and university papers love to ask: how many substrings, how many strings of length at most n, how many elements in L1L2. Every count in this chapter was checked by brute force with a short Python script.


Symbols and Alphabets

A symbol is the smallest unit we work with: a letter, a digit, or any other mark. We never look "inside" a symbol.

An alphabet, written Σ (capital sigma), is a finite, non-empty set of symbols.

Examples:

  • Σ = {0, 1} is the binary alphabet.

  • Σ = {a, b} is the alphabet we will use most often in examples.

  • Σ = {a, b, c, ..., z} is the lowercase English alphabet.

  • The set of all 128 ASCII characters is an alphabet. A C compiler's lexer reads strings over it.

  • Σ = {5, 10} could be the coins a vending machine accepts; each coin is one symbol.

Why finite? A machine has to react to each symbol with a fixed rule. With infinitely many symbols, a finite machine could not even have one rule per symbol. Why non-empty? With no symbols there would be only one string (the empty one), and the theory would be trivial.

Note that a symbol can be written with more than one character. If Σ = {10, 5}, then "10" is one symbol, not two. When this could cause confusion, books choose single-character symbols, and so will we.


Strings

A string (or word) over Σ is a finite sequence of symbols from Σ.

Over Σ = {a, b}, the following are strings: a, abba, bbbbb. We usually name strings with letters from the end of the alphabet: u, v, w, x, y, z. Single symbols are named with letters from the start: a, b, c.

Length

The length of w, written |w|, is the number of symbol positions in it. |abba| = 4, |b| = 1. We also write |w|a for the number of a's in w: for w = abba, |w|a = 2 and |w|b = 2.

The Empty String ε

The empty string, written ε (epsilon; some books use λ), is the string with no symbols. |ε| = 0.

ε is a string over every alphabet, but it is never a symbol of the alphabet. It plays the role that 0 plays in addition: gluing ε to any string changes nothing. If a C program reads an empty line, the line it read is ε.


Operations on Strings

Concatenation

The concatenation of x and y, written xy (or x·y), is x followed immediately by y. If x = ab and y = bba, then xy = abbba and yx = bbaab.

Property

Statement

Comment

Associative

(xy)z = x(yz)

So we can write xyz without brackets.

Identity

εw = wε = w

ε is the identity element.

NOT commutative

xy ≠ yx in general

ab·ba = abba but ba·ab = baab.

Length adds

|xy| = |x| + |y|

Used constantly in counting arguments.

Powers of a String

wn means w concatenated with itself n times, with w0 = ε. For w = ab: w0 = ε, w1 = ab, w3 = ababab. Do not confuse (ab)3 = ababab with ab3 = abbb: without brackets the power applies only to the symbol next to it. This is why we write anbn to mean "n a's followed by n b's".

Reversal

The reverse wR is w written backwards: (abb)R = bba, εR = ε. A string with w = wR is a palindrome (ε, a, abba, aba, malayalam).

An important identity: (xy)R = yRxR. The order flips. Check: x = aab, y = ba, so xy = aabba and (xy)R = abbaa; and yRxR = ab · baa = abbaa. Same. But xRyR = baa · ab = baaab, which is different. (It is the same rule as (AB)T = BTAT for matrices, or taking off socks and shoes in reverse order.)


Prefixes, Suffixes and Substrings

  • x is a prefix of w if w = xy for some string y. The prefixes of abc are ε, a, ab, abc.

  • y is a suffix of w if w = xy for some x. The suffixes of abc are ε, c, bc, abc.

  • v is a substring of w if w = xvy for some x and y. It must be a contiguous block.

  • A prefix/suffix/substring is proper if it is not w itself. (Some books also exclude ε; always read the question's convention.)

  • A subsequence keeps the order but may skip symbols: ac is a subsequence of abc but not a substring.

Counting Formulas

For a string w of length n:

What

Count

Why

Prefixes (including ε and w)

n + 1

One prefix for each cut position 0, 1, ..., n.

Suffixes (including ε and w)

n + 1

Same argument.

Proper prefixes (excluding w, including ε)

n

Remove w itself.

Non-empty substrings, all symbols distinct

n(n + 1)/2

Choose a start i and an end j with i ≤ j: n + (n - 1) + ... + 1.

Substrings including ε, all symbols distinct

n(n + 1)/2 + 1

Add the empty string once.

Substrings when symbols repeat

Fewer than the formula

Equal blocks at different positions count once.

Worked Example: Counting Substrings

w = abc (n = 3, all distinct). Substrings: ε, a, b, c, ab, bc, abc. That is 3·4/2 + 1 = 7. Note that ac is missing: it is not contiguous.

w = aab (n = 3, a repeats). Listing by start position: a, aa, aab (start 1); a, ab (start 2); b (start 3). The "a" from start 2 is the same string as the "a" from start 1, so the distinct non-empty substrings are a, b, aa, ab, aab: 5, plus ε gives 6, not 7.

w = banana: the formula would give 21 + 1 = 22, but the true count of distinct substrings (with ε) is 16, because blocks like "an", "na" and "ana" repeat. When symbols repeat, there is no shortcut formula; you must list carefully.


Σk, Σ* and Σ+

Σk = the set of all strings of length exactly k over Σ.
Σ* (Sigma star) = Σ0 ∪ Σ1 ∪ Σ2 ∪ ... = the set of all strings over Σ, including ε.
Σ+ = Σ1 ∪ Σ2 ∪ ... = all non-empty strings. So Σ* = Σ+ ∪ {ε}.

For Σ = {0, 1}:

Σ^0 = { ε }                          (1 string)
Σ^1 = { 0, 1 }                       (2 strings)
Σ^2 = { 00, 01, 10, 11 }             (4 strings)
Σ^3 = { 000, 001, ..., 111 }         (8 strings)
Σ*  = { ε, 0, 1, 00, 01, 10, 11, 000, 001, ... }   (infinite)

Notice Σ0 = {ε}, which has one element. It is not empty.

Counting Strings

If |Σ| = k, each of the n positions can be filled in k ways, so:

  • |Σn| = kn

  • Number of strings of length at most n = k0 + k1 + ... + kn = (kn+1 - 1)/(k - 1) for k ≥ 2. For binary this is 2n+1 - 1.

Check: binary strings of length ≤ 3: 1 + 2 + 4 + 8 = 15 = 24 - 1. Strings of length ≤ 2 over {a, b, c}: 1 + 3 + 9 = 13 = (27 - 1)/2.

Σ* Is Infinite, but Each String Is Finite

Σ* has infinitely many members, yet every single member has some finite length. There is no "infinite string" in Σ*. We can list Σ* in shortlex (canonical) order: shorter strings first, and strings of equal length in dictionary order:

ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, ...

Every string appears at some finite position in this list, which means Σ* is countably infinite. (Plain dictionary order would not work: 0, 00, 000, ... would go on forever and 1 would never be reached.)


Languages

A language over Σ is any subset of Σ*.

That is the whole definition. A language may be finite or infinite, simple or wild. Examples over Σ = {0, 1}:

  • L1 = {01, 10} (finite, two strings).

  • L2 = {w : w ends with 01} = {01, 001, 101, 0001, ...} (infinite).

  • L3 = {0n1n : n ≥ 0} = {ε, 01, 0011, 000111, ...}.

  • L4 = {w : w is the binary form of a prime} = {10, 11, 101, 111, 1011, ...}.

  • Σ* itself (the "everything" language).

∅, {ε} and ε Are Three Different Things

Object

What it is

Size

ε

A string (of length 0)

length 0

{ε}

A language containing exactly one string, the empty one

1 element

∅ (or { })

The empty language, containing no strings at all

0 elements

A machine that accepts only the empty input has language {ε}. A machine that accepts nothing at all has language ∅. This distinction decides many GATE answers.

Languages as Problems

A decision problem is a question with a yes/no answer for each input. After encoding inputs as strings, the problem is the language of yes-instances. "Is n divisible by 3?" is the language {w ∈ {0,1}* : w is the binary form of a multiple of 3}. When a machine accepts exactly that language, we say it solves (or recognises) the problem. You will build such a machine in Designing DFAs: Solved Problems.


Operations on Languages

Since languages are sets, all set operations apply. There are also operations that use concatenation.

Operation

Definition

Union

L1 ∪ L2 = {w : w ∈ L1 or w ∈ L2}

Intersection

L1 ∩ L2 = {w : w ∈ L1 and w ∈ L2}

Difference

L1 - L2 = {w : w ∈ L1 and w ∉ L2}

Complement

L' (also written as L with a bar on top) = Σ* - L. Always taken relative to Σ*.

Concatenation

L1L2 = {xy : x ∈ L1, y ∈ L2}

Power

L0 = {ε}, Ln = Ln-1L

Kleene star (closure)

L* = L0 ∪ L1 ∪ L2 ∪ ...: all strings formed by gluing together zero or more strings from L

Positive closure

L+ = L1 ∪ L2 ∪ ...: one or more strings from L

Reversal

LR = {wR : w ∈ L}

Note that Σ* is just the Kleene star applied to the alphabet viewed as a language of one-symbol strings. That is where the notation comes from.

Worked Example 1: Concatenation

Let L1 = {a, ab} and L2 = {b, bb}. Form every pair (x from L1, y from L2):

         y = b      y = bb
x = a    ab         abb
x = ab   abb        abbb

So L1L2 = {ab, abb, abbb}. There are 4 pairs but only 3 strings, because a·bb and ab·b both give abb. In general |L1L2| ≤ |L1| × |L2|, with equality only when no string can be split in two ways.

The other order gives L2L1 = {ba, bab, bba, bbab}, which is different: concatenation of languages is not commutative.

Worked Example 2: Powers and Star

With L = {a, ab}:

L^0 = { ε }
L^1 = { a, ab }
L^2 = { aa, aab, aba, abab }
L^3 = { aaa, aaab, aaba, aabab, abaa, abaab, ababa, ababab }    (8 strings)
L*  = { ε, a, aa, ab, aaa, aab, aba, aaaa, aaab, aaba, abaa, abab, ... }

Can we describe L* in words? Every piece starts with a, and each b comes right after an a. So L* is exactly the set of strings that are empty or start with a, and that never contain bb. (We confirmed this description against the definition for every string of length up to 8.) Turning "build by gluing pieces" into "check a simple property" is a skill you will use again and again.

Identities Worth Memorising

Identity

Reason

L∅ = ∅L = ∅

No y to pair with; like multiplying by 0.

L{ε} = {ε}L = L

Gluing ε changes nothing; like multiplying by 1.

∅* = {ε}

L0 = {ε} always, and all higher powers of ∅ are ∅.

{ε}* = {ε}

Gluing empty strings gives only ε.

∅+ = ∅

Needs at least one piece, and there is none.

L+ = LL* = L*L

One piece, followed (or preceded) by zero or more.

L* = L+ ∪ {ε}

Zero pieces gives ε.

ε ∈ L+ if and only if ε ∈ L

So L+ = L* - {ε} is false when ε ∈ L.

(L*)* = L* and L*L* = L*

Starring twice adds nothing new.

(L1L2)R = L2RL1R

Follows from (xy)R = yRxR.

And two things that are not identities:

  • (L1 ∪ L2)* ≠ L1* ∪ L2* in general. With L1 = {a} and L2 = {b}, the string ab is in ({a} ∪ {b})* = {a, b}* but not in a* ∪ b*, which contains only all-a or all-b strings. (The ⊇ direction always holds.)

  • Concatenation does not distribute over intersection. Take L = {ε, a}, M = {b}, N = {ab}. Then M ∩ N = ∅, so L(M ∩ N) = ∅. But LM = {b, ab} and LN = {ab, aab}, so LM ∩ LN = {ab}. (It does distribute over union: L(M ∪ N) = LM ∪ LN.)


How Many Languages Are There?

This short argument explains why unsolvable problems must exist, long before we study Turing machines.

  1. Σ* is countable. The shortlex listing gives every string a position: w1 = ε, w2 = 0, w3 = 1, and so on.

  2. The set of all languages is uncountable. Suppose we could list all languages L1, L2, L3, .... Build D = {wi : wi ∉ Li}. D differs from L1 on w1, from L2 on w2, and in general from every Li on wi. So D is missing from the list, a contradiction. This is Cantor's diagonal argument.

  3. Machines are countable. Every machine (any program, any automaton) is described by a finite string, so there are only countably many of them.

Countably many machines cannot cover uncountably many languages. Hence there are languages that no machine recognises. Later chapters will exhibit specific, natural ones.


Common Mistakes

  • Treating ε as a symbol of Σ. It is a string, not a symbol. Σ = {a, b} does not contain ε.

  • Confusing ∅ with {ε}. ∅ has no strings; {ε} has one. ∅L = ∅ but {ε}L = L.

  • Saying Σ0 = ∅. Σ0 = {ε}. Similarly L0 = {ε} even when L = ∅.

  • Using n(n+1)/2 when symbols repeat. The formula counts positions, not distinct strings. For aab it overcounts.

  • Forgetting ε in substring or prefix counts. Read whether the question says "non-empty" or "proper".

  • Assuming |L1L2| = |L1||L2|. Duplicates collapse, as in {a, ab}{b, bb}.

  • Reading ab3 as (ab)3. The exponent binds to the nearest symbol.

  • Writing (xy)R = xRyR. The order reverses: yRxR.


GATE-Style Questions

Q1. How many substrings (including ε) does the string COMPUTER have?

All 8 letters are distinct, so the count is 8·9/2 + 1 = 36 + 1 = 37.

Q2. How many binary strings have length at most 4?

20 + 21 + 22 + 23 + 24 = 31 = 25 - 1.

Q3. What is ∅*? How many strings does it contain?

∅* = {ε}, which contains exactly 1 string. It comes from ∅0 = {ε}; all higher powers are empty.

Q4. L1 = {ε, a} and L2 = {a, aa}. How many strings are in L1L2?

Pairs: ε·a = a, ε·aa = aa, a·a = aa, a·aa = aaa. Distinct strings: {a, aa, aaa}, so 3.

Q5. True or false: L+ = L* - {ε} for every language L.

False. If ε ∈ L then ε ∈ L1 ⊆ L+, so L+ = L*. The statement holds only when ε ∉ L.

Q6. Is ab a substring of aabb? Is it a subsequence of acb?

ab is a substring of aabb (positions 2-3). ab is a subsequence of acb (skip c) but not a substring of it.

Q7. Is the set of all languages over {0, 1} countable?

No. Σ* is countably infinite, and the set of all its subsets is uncountable by Cantor's diagonal argument. This is why some languages are not recognised by any machine.

Q8. For w = 0110, list wR and say whether w is a palindrome.

wR = 0110 = w, so yes, it is a palindrome.


Summary

  • An alphabet Σ is a finite, non-empty set of symbols. A string is a finite sequence of symbols; ε is the empty string, |ε| = 0.

  • Concatenation is associative, has ε as identity, and is not commutative. (xy)R = yRxR.

  • A length-n string has n + 1 prefixes and n + 1 suffixes; with all symbols distinct it has n(n + 1)/2 + 1 substrings including ε.

  • |Σn| = kn; strings of length ≤ n number (kn+1 - 1)/(k - 1). Σ* is countably infinite; Σ+ = Σ* - {ε}.

  • A language is any subset of Σ*. ε, {ε} and ∅ are different objects.

  • Language operations: union, intersection, complement, concatenation, powers, Kleene star, positive closure and reversal. Key identities: L∅ = ∅, L{ε} = L, ∅* = {ε}.

  • There are uncountably many languages but only countably many machines, so some languages cannot be recognised by any machine.

  • Next, Finite Automata introduces the simplest machine that reads these strings.