Levels of Abstraction

What we will now begin to do is to deploy these tools for describing and expressing generalizations about possible languages. To do this, we are going to need to start thinking in terms of sets of sets of languages. That is, we will begin to think about subsets \(\mathcal{L}\) of the set of languages \(2^{\Sigma^*}\) on \(\Sigma\). This approach will yield four important 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 are going to be particularly interested in collections of languages that share some interesting properties. We will call such collections classes of languages (or families of languages), and we will be interested in ways of compactly describing those classes that leverage the property shared by languages in the class. We will call compact descriptions of a particular language grammars and collections thereof classes of grammars \(\mathcal{G}\).