Alphabets, Strings and Languages

Every model in the theory of computation (finite automata, pushdown automata, Turing machines) processes strings built from a fixed finite alphabet. A language is simply a set of strings. This note fixes the notation used throughout the Theory of Computation short notes: alphabets, concatenation, powers, Kleene star, and the elementary language operations (union, intersection, complement, concatenation, star, reverse).

These definitions look elementary, but they are the source of several standard mistakes: confusing $\Sigma^*$ with $\Sigma^+$, forgetting that $\varepsilon$ is a string of length 0, or treating infinite languages as if membership tests were automatic.

An alphabet $\Sigma$ is a finite, nonempty set of symbols. Typical alphabets are $\Sigma = \{0,1\}$, $\Sigma = \{a,b\}$, or $\Sigma = \{a,b,c\}$. The empty set is not used as an alphabet here.

Symbols are atomic: the string ab is two symbols, not one. When a question writes $\Sigma = \{0,1,2,\ldots,9\}$, each digit is one symbol.

A string (word) over $\Sigma$ is a finite sequence of symbols from $\Sigma$. The empty string is written $\varepsilon$ (some texts use $\lambda$). It contains no symbols.

Convention used in all Gate CS Mastery TOC notes. The empty string is $\varepsilon$; the empty language (the empty set of strings) is $\emptyset$. They are different objects: $\varepsilon$ is a string, $\emptyset$ is a language, and $\{\varepsilon\}$ is a language containing exactly one string.

The concatenation of strings $u$ and $v$ is the string $uv$ obtained by writing $u$ then $v$. Concatenation is associative: $(uv)w = u(vw)$, and $\varepsilon$ is the identity: $u\varepsilon = \varepsilon u = u$. It is not commutative in general: $ab \neq ba$.

Integer powers of a string:

So $a^3 = aaa$ and $(ab)^2 = abab$. Do not confuse string power with language power (below).

A language over $\Sigma$ is any subset $L \subseteq \Sigma^*$. Languages may be finite (for example $\{a, ab\}$) or infinite (for example $a^* = \{\varepsilon, a, aa, \ldots\}$).

Important special languages:

If $|\Sigma| = k$, then $|\Sigma^n| = k^n$. In particular $|\Sigma^0| = 1$ because $\Sigma^0 = \{\varepsilon\}$, and

for $k > 1$. For $\Sigma = \{0,1\}$ and $n = 3$: $|\Sigma^3| = 8$ and the number of strings of length at most 3 is $1+2+4+8 = 15$.

For languages $L, M \subseteq \Sigma^*$:

Star versus plus. $L^* = L^+ \cup \{\varepsilon\}$. Always $\varepsilon \in L^*$. Whether $\varepsilon \in L^+$ depends on whether $\varepsilon \in L$ (equivalently, whether some $L^k$ for $k \ge 1$ contains $\varepsilon$).

Empty language under operations.

These identities appear in regular-expression simplifications.

Example over $\Sigma = \{a,b\}$. Let $L_1 = \{a, ab\}$ and $L_2 = \{b, ba\}$.

For $w = xyz$ (concatenation of three strings):

The language of all prefixes of strings in $L$ is written $\mathrm{Prefix}(L)$. Regular languages are closed under prefix; that fact is proved later with automata.

$\Sigma^*$ is countably infinite for any finite nonempty $\Sigma$: enumerate by increasing length, and lexicographically within each length. Every language over $\Sigma$ is a subset of a countable set, so languages are at most continuum-many; there are uncountably many languages over $\{0,1\}$, but only countably many finite automata, so some languages are not regular. That counting argument is the cleanest existence proof that non-regular languages exist; concrete examples use the pumping lemma or Myhill-Nerode.

There is no single algorithm in this foundational note. For a fixed language L, membership is a decision problem whose decidability depends on L. An algorithm taking a language description as input needs a finite representation, such as a machine or grammar; the representation matters for that uniform problem.

When a language is finite and listed explicitly, membership is table lookup. When it is given by a pattern such as "$w$ has even length", membership is a direct check on $w$.

$(\Sigma^*, \cdot, \varepsilon)$ is the free monoid generated by $\Sigma$: concatenation is associative with identity $\varepsilon$, and every string has a unique factorization into symbols of $\Sigma$. Language concatenation extends the monoid operation to sets:

The power set of $\Sigma^*$ with union and concatenation forms a semiring; regular expressions exploit that algebraic structure (see Regular Expressions).

By definition $L^* = \bigcup_{k \ge 0} L^k$ and $L^0 = \{\varepsilon\}$ for every language $L$. Taking $L = \emptyset$ gives $\varepsilon \in \emptyset^*$. For $k \ge 1$, $\emptyset^k = \emptyset$, so nothing else enters. Hence $\emptyset^* = \{\varepsilon\}$.

For finite $\Sigma$ with $k = |\Sigma| \ge 1$:

The set of regular languages is countable (each regular language has a regular expression, and regular expressions over a finite alphabet are a countable set). Therefore most languages are not regular.

Let $\Sigma = \{0,1\}$ and $w = 01101$.

Let $A = \{00, 01\}$ and $B = \{1, 11\}$ over $\{0,1\}$.

Let $L = \{a, bb\}$ over $\{a,b\}$. Then $L^*$ contains every string that can be tiled by blocks $a$ and $bb$. Membership examples:

Let $L = \{a\}$ over $\Sigma = \{a\}$. Then $\overline{L} = \{\varepsilon, aa, aaa, \ldots\} = a^* \setminus \{a\}$.

If the same set $L = \{a\}$ is viewed over $\Sigma = \{a,b\}$, the complement also contains every string that uses a $b$, so $\overline{L}$ is different. Always fix $\Sigma$ before taking complements.

The substring count for distinct symbols is the main trap: the formula $n(n+1)/2$ counts nonempty substrings by position, and it overcounts as soon as symbols repeat. Example 2 is the other trap: $\lvert AB\rvert = \lvert A\rvert\,\lvert B\rvert = 4$ holds there only because no two pairs give the same string.

Shortlex (canonical) order lists strings by length, then lexicographically: $\varepsilon, 0, 1, 00, 01, 10, 11, 000, \ldots$. Plain dictionary order is not an enumeration of $\Sigma^*$: $\varepsilon, 0, 00, 000, \ldots$ never reaches 1. Shortlex order is what makes $\Sigma^*$ countable and is the order used to enumerate strings in decidability proofs.

Common misconceptions.