Basic Definitions

Formal language theory is the study of formal languages. Before we can work with formal languages, it is important to define some vocabulary.

Basic Objects

Symbol

Symbols are the smallest units in formal language theory. They are difficult to define on their own, and are best understood by their relationship to the subsequent definitions.

Alphabet

An alphabet is a non-empty collection of symbols.

Examples of alphabets include:

• A binary alphabet has only two symbols.
  Thanks to its simplicity, this alphabet will be used for many of the examples in this course.
• Standard ASCII is an alphabet with 128 symbols.
  This alphabet is understood by many programming languages.
• The English alphabet has 26 symbols (52 if you distinguish between capital letters and lowercase letters).
  This alphabet is a subset of the alphabet that makes up most of the text in this course.

Conventionally, the symbol 'Σ' (uppercase sigma) denotes alphabets, though any symbol can so long as it does not conflict with other symbols.

Word

A word (also called a string or a sentence) is a finite sequence of symbols.

Three examples of words include:

• The word '01101001' with respect to the binary alphabet.
• The word 'printf("%s\n", "Hello, world!");' with respect to Standard ASCII.
• The word 'computation' with respect to the English alphabet

Conventionally, the symbol 'w' denotes a word, though any symbol can so long as it does not conflict with other symbols.
The symbol 'ε' denotes the null word (also called the empty word).

Language

A language is a potentially infinite set of words with respect to some alphabet (That is, they can be finite or infinite). These are the key objects studied by formal language theory.

Three examples of languages include:

• The set of all binary strings with an odd number of '1' bits make up a formal language with respect to the binary alphabet.
• The set of all C programs that compile successfully make of a formal language. This is because C programs are finite sequences of ASCII symbols (or words with respect to Standard ASCII).
• All words in the English language make up a formal language.

Conventionally, the symbol 'L' denotes a language, though any symbol can so long as it does not conflict with other symbols.
The empty set symbol '∅' denotes an empty language. This is not to be confused with { ε }, the language containing the null word.

Basic Operations

Concatenation

Concatenation is defined for words and languages.

• w ⋅ w → w
• L ⋅ L → L

For any two words a and b, their concatenation a ⋅ b is a word formed by taking the sequence of all symbols in a followed by all symbols in b.

Some basic properties of concatenation of words include:

• Non-commutativity: left-concatenation is distinct from right-concatenation.
  a ⋅ b ≠ b ⋅ a.
• Associativity: the order in which concatenation occurs is irrelevant.
  a ⋅ (b ⋅ c) = (a ⋅ b) ⋅ c.
• Identity: any word concatenated with the null word is the word itself.
  a ⋅ ε = ε ⋅ a = a.

For any two languages L₀ and L₁, their concatenation L₀ ⋅ L₁ is the language formed by concatenating each word in L₀ each word in L₁. This is similar to a Cartesian product.

The concatenation of languages exhibits similar properties to the concatenation of words:

• Non-commutativity: left-concatenation is distinct from right-concatenation.
  L_a ⋅ L_b ≠ L_b ⋅ L_a
• Associativity: the order in which concatenation occurs is irrevelant.
  L_a ⋅ (L_b ⋅ L_c) = (L_a ⋅ L_b) ⋅ L_c
• Zero element: any language concatenated with the empty language is the empty language.
  L ⋅ ∅ = ∅ ⋅ L = ∅

Exponentiation

Exponentiation is defined for words, alphabets and languages. It can be thought of as repeated concatenation, in the same way exponentiation over real numbers can be thought of as repeated multiplication.

• wⁿ → w
• Σⁿ → L
• Lⁿ → L
where n is a non-negative integer.

For any word a, its exponentiation aⁿ is the concatenation of a exactly n times.

The exponentiation of words shares some properties with the exponentiation of real numbers:

• wⁿ ⋅ w^m = w^m+n
• w⁰ = ε

For any alphabet Σ, its exponentiation Σⁿ is the language of all words created by concatenating n symbols from Σ. More simply, Σⁿ is the language of all words in Σ of exactly length n.

For any language L, its exponentiation Lⁿ is the language of all concatenations of n words in L.

Kleene Star

Kleene star (also called Kleene closure) is defined for words, alphabets, and languages. It can be thought of as the limit of exponentiation as n approaches infinity, or the set of zero or more exponentiations.

• w^* → L
• Σ^* → L
• L^* → L

For any word a, its Kleene closure a^* is the language of all concatenations of zero or more counts of a.

For any alphabet Σ, its Kleene closure Σ^* is the language of all words with respect to Σ of length zero or more.

For any language L, its Kleene closure L^* is the language of all concatenations of zero or more words in L.

Kleene Plus

Kleene plus is defined for words, alphabets, and languages. It can be thought of as Kleene closure minus ε, or the set of one or more exponentiations.

• w⁺ → L
• Σ⁺ → L
• L⁺ → L

For any word a, its Kleene plus a⁺ is the language of all concatenations of one or more counts of a.

For any alphabet Σ, its Kleene plus Σ⁺ is the language of all words with respect to Σ of length one or more.

For any language L, its Kleene plus L⁺ is the language of all concatenations of one or more words in L.

Notational Sugar

Often times we may wish to do something like append a single symbol to every word in a language. Because concatenation is not defined between a symbol and a language, we must define the language of the single word of the single symbol to perform this operation. This is unwieldy, so we avoid it by abusing notation.

When necessary, a symbol can behave like the word containing only that symbol. This allows symbols to be used in operations with words. Similarly, a word can behave like the language containing only that word. This allows words to be used in operations with languages. By combining the two extensions, symbols can even be used in operations with languages.