Formal languages

A formal language is a kind of generalisation of the language we are used to from everyday life.

Basic concepts

To start with, we can think of a formal language as an ordinary language, for example English. What is such a language made of? It consists of words, which we then combine into sentences. We will not be concerned with sentences, only with words. What are words made of? Letters of the alphabet. So we will begin with the alphabet.

An alphabet is any non-empty set. The elements of an alphabet are called symbols. For English, it would be the usual English alphabet with both lower-case and upper-case letters. If we did not want to describe English but, say, numbers, the alphabet would contain all ten digits. An alphabet is often denoted by the symbol Σ.

By a string, also called a word, we mean a finite sequence of symbols from some alphabet Σ. For example, if we have the alphabet Σ= {a,b,c,d,e,…, z}, then “hello” and “doberman” are strings, but “café” is not (we have no letter “é”), nor is “Oliver” (we have no letter “O”) or “good day” (we have no space). The length of a string is the number of symbols it consists of.

Concatenation of strings: if we have two strings a = a₁a₂… a_n and b = b₁b₂… b_m, then concatenating them gives the string ab = a₁a₂… a_nb₁b₂… b_m. Example: concatenating the strings “hello” and “doberman” gives the string “hellodoberman”. We denote concatenation either by a small circle, that is a ∘ b, or by nothing at all, simply writing the strings one after the other without any special symbol.

The empty string is denoted ε and is the string of length zero. If we concatenate a string a = a₁… a_n with the empty string ε, we get a back. That is, a ∘ ε = a.

The closure of the alphabet Σ is the set of all strings we can form from the alphabet Σ, including the empty string. The closure is denoted Σ^∗. For the binary alphabet Σ= {0, 1} we have

$${\mathrm{\Sigma }}^{\ast }=\{\epsilon ,0,1,00,01,10,11,000,001,\dots \}$$

Sometimes we also use the positive closure of the alphabet, which is again the set of all strings we can build from the alphabet, except the empty string. The positive closure is denoted Σ⁺ and Σ⁺ = Σ^∗ ∖ {ε}.

Examples of alphabets

• Let us return to the example with English. Every English word can be found in the closure of an alphabet containing lower-case and upper-case letters (and perhaps a hyphen “-”). If we add to this alphabet a space and punctuation marks (comma, full stop, exclamation mark, question mark, …), the closure contains every sentence we are able to form in English. Of course, this closure will also contain “sentences” like “sadflsf kasdf kagrjewiazrcasckyker kf fkjbsjbgvbadfgsa!!!:??: ::!?:?:sdf”.

• If our alphabet contains all the digits Σ= {0, 1, …, 9}, then the closure contains all the positive integers – and a few extra strings. It also contains numbers starting with zero, such as 00054, or zero on its own, and on top of that the empty string, which is of course not a number.

• An alphabet must be non-empty, so the smallest alphabet has at least one symbol. For example, for the alphabet Σ= {!} we get the closure Σ^∗ = {ε, !, !!, !!!, !!!!, …}, that is, a set of strings which, for every n ∈ ℕ₀, contains a string with n exclamation marks, and contains no other strings.

• Let Σ= {qw,c}. This is a very strange alphabet, because it contains the string qw. This notation is not normally used, because it is confusing and odd, but we can imagine that we glue the letters “q” and “w” together so that they form a single character. Then we can see the string “qw” as the symbol “qw”. If we made the string “qwcqw” from these symbols, it would have length three – it would consist of the symbols “qw”, “c” and “qw”. We will not often meet alphabets like this, but there are situations where we need symbols made up of several symbols.

Formal language

A (formal) language over an alphabet Σ is any subset of Σ^∗. So for a language L over an alphabet Σ we have L ⊆ Σ^∗. Examples of languages:

• In the previous section we defined the alphabet of digits Σ= {0, 1, …, 9}. Its closure is all the strings made up of digits only. If we add the rule that a string must not start with zero and must not be empty, we get the set of positive integers ℤ⁺. We have ℤ⁺ ⊆ Σ^∗, so ℤ⁺ is a language over the alphabet Σ.

• To the previous set of digits we can add the minus sign “-”, so Σ= {0, 1, …, 9, −}. The closure is all the strings made up of digits or the minus sign. That means the closure also contains strings such as “12-84-”, “1-5-8” or “-”. We create the language of integers ℤ by adding three rules:

  • The minus sign does not occur in the string at all, or occurs at the start of the string.
  • The first digit in the string cannot be zero, except in the string “0”.
  • Every string must contain at least one digit.

  This set describes the set of integers and it is a subset of Σ^∗ – so it is a language over the alphabet Σ.

• Let Σ= {0, 1}. The closure is then all the strings made up of zeros and ones. We can define a language L over this alphabet as, for example, the set of all strings with exactly three ones. We can also be more creative and say that the language L is the set of all strings that represent a valid docx file (what comes out of Word).

• Let us stay with the binary alphabet Σ= {0, 1}. Every string of characters (ordinary characters on your keyboard) can be converted into binary form, that is, into zeros and ones, and back again, for example using the ASCII table (or, more precisely, the ASCII table converts characters to numbers and numbers in base 10 can be converted to binary). We can therefore define the language of all strings that correspond to a valid email address, and it will still be a language over the binary alphabet.

Concatenation of languages: we can concatenate languages too. The definition is similar to the Cartesian product of sets. Let L₁ and L₂ be two languages. Their concatenation L₁ ∘ L₂ is a new language, defined like this:

$$L_1\circ L_2=\{w_1\circ w_2|w_1\in L_1,w_2\in L_2\}$$

That is, we take every string from the language L₁ and concatenate it with every string from the language L₂. Example: let

$$\begin{array}{rcl}{L}_1& =& \{0,1\}\\ L_2& =& \{a,b,hello\}\end{array}$$

Then

$$\begin{array}{rcl}{L}_1\circ L_2& =& \{0a,0b,0hello,1a,1b,1hello\}\\ L_2\circ L_1& =& \{a0,a1,b0,b1,hello0,hello1\}\\ L_1\circ L_1& =& \{00,01,10,11\}\end{array}$$

So far we have described languages in plain words, simply saying in English what the language should look like. That is very impractical, so a more formal way of defining a language is introduced. The first of these is the grammar.