Overview

Up until this point, we’ve mainly analyzed one language at a time. We defined a language \(L\) on an alphabet \(\Sigma\) as a subset of the set of strings \(\Sigma^* = \bigcup_{i=0}^\infty \Sigma^i\) on \(\Sigma\) (i.e. \(L \in 2^{\Sigma^*}\)). We then used regular expressions to describe particular languages and minimum edit distance to describe a relation between particular strings.

Now suppose we want to generalize across languages. What is the next larger object? It is a set of languages: a subset \(\mathcal{L}\) of \(2^{\Sigma^*}\). This gives us four levels of abstraction:

1. Primitive (unanalyzed) elements \(\sigma \in \Sigma\)
2. Collections of primitive elements: sets \(\Sigma\) or sequences \(\boldsymbol\sigma \in \Sigma^*\)
3. Languages: collections of sequences of primitive elements \(L \in 2^{\Sigma^*}\)
4. Collections of languages \(\mathcal{L} \subseteq 2^{\Sigma^*}\)

We’ll be particularly interested in collections whose members share some property. We will call these collections classes of languages (or families of languages). A compact description of one particular language is a grammar, and a collection of such descriptions is a class of grammars \(\mathcal{G}\).

We’ve already seen a few classes of languages and grammars. The regular languages form a class of languages, and regular expressions form a class of grammars. In this module, we will examine the regular languages and some phonologically interesting subclasses. We will ask two questions: (i) which properties do these classes have, and (ii) where are their expressive boundaries?