Chapter: Classification of Formal Languages
Formal languages are languages with a grammar. There are only two limitations for grammars: A grammar can, by definition, have only finitely many rules, and every premise must contain at least one variable.
We will see in this chapter that by restricting grammars even more we can generate different types of languages. In other words, different types of grammars will allow us to classify formal languages.
Table of Contents
- Definition: Type-3 (Linear) Grammars and Regular Languages
- Definition: Type-2 (cf) Grammars and Context-free Languages
- Definition: Type-1 (cs) Grammars and Context-sensitive Languages
- Definition: Type-0 (Phrase Structure) Grammars and Recursively Enumerable Languages
- Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
- Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015