Oct 19

Individual grammars can be seen as names of languages, and a grammar formalism provides some subset of the class of all languages with names.

The relation between a name and its bearer is a question much studied in philosophy. But in our constructed case, the name itself contains enough information to identify its bearer. This is done however in many different ways.

We can begin by looking at a very straightforward way of naming languages, due to Stephen Kleene.

We have a finite set of basic names, one for each letter of our alphabet, and two additional ones, naming the empty language, and the language consisting of just the empty string. This provides us with a name for each language with up to one sentence of length one or less. This is shown in figure 1.

Table 1: basic names
symbol meaning
Z \(\emptyset\)
E \(\{\epsilon\}\)
C a \(\{a\}\)

Starting from basic sets, we can construct larger sets of strings by means of the operations of set union, set concatenation, and set iteration. We extend our naming schemes with symbols for these operations, as shown in figure 2. I indicate the bearer of a name \(r\) using the notation \(r^{\bullet}\)

Table 2: composite names
symbol meaning
Alt r s \(r^{\bullet} \cup s^{\bullet}\)
Con r s \(r^{\bullet} \cdot s^{\bullet}\)
Star r \((r^{\bullet})^{\ast}\)

It is more convenient when writing things down in a human readable way to use a more intuitive notation. Typically, a name such as Star (Con (C a) (Alt E Z)) would be rendered as \((a(\epsilon + 0))^{\ast}\). The translation is shown in figure 3.

Table 3: translation into more intuitive notation
symbol translation
Z \(0\)
E \(\epsilon\)
C a \(a\)
Alt r s \(r+ s\)
Con r s \(r s\)
Star r \(r^{\ast}\)