Strings and languages

Alphabet

An alphabet Σ is a finite, non-empty set of symbols. Σ = {0, 1} is the binary alphabet; Σ = {a, b, c} is another. A symbol is atomic — it has no parts.

String

A string over Σ is a finite sequence of symbols from Σ. Its length |w| is how many symbols it has, counting repeats: |0110| = 4.

The empty string ε is the string of length zero. It is a string like any other — it is not "nothing", and it is not the same as the empty set. Half the marks lost on this topic come from that one confusion.

Powers of an alphabet

Σ^k is the set of strings of length exactly k. So Σ¹ is essentially Σ itself, Σ² is every pair, and:

Σ⁰ = {ε}

One element, not zero — whatever the alphabet is, there is exactly one string of length 0 over it.

Σ* and Σ⁺

Σ* is the set of all strings over Σ: Σ⁰ ∪ Σ¹ ∪ Σ² ∪ … It is infinite for any non-empty alphabet, though every string in it is finite. Σ⁺ is the same set without ε.

A language over Σ is any subset of Σ*. That is the whole definition — which is why "is this language regular?" is a question worth a whole module.

Try it

Change the alphabet and the bound. Watch the count, not just the list.

Concatenation

If x and y are strings, xy is x followed by y, and |xy| = |x| + |y|. Concatenation is associative, and ε is its identity: εw = wε = w.

The same thing, spelled differently

The question papers and the textbook do not always agree on names. These all mean the same thing, and this tool accepts either spelling.