Branches History Index

◀ ▲ ▶Branches / Theoretical-computer-science / Formal-languages / Chapter: Classification of Formal Languages

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

Explanations: 1

  1. Definition: Type-3 (Linear) Grammars and Regular Languages
  2. Definition: Type-2 (cf) Grammars and Context-free Languages
  3. Definition: Type-1 (cs) Grammars and Context-sensitive Languages
  4. Definition: Type-0 (Phrase Structure) Grammars and Recursively Enumerable Languages

Thank you to the contributors under CC BY-SA 4.0!

Github:
bookofproofs

References

Bibliography

  1. Erk, Katrin; Priese, Lutz: "Theoretische Informatik", Springer Verlag, 2000, 2nd Edition
  2. Hoffmann, Dirk: "Theoretische Informatik, 3. Auflage", Hanser, 2015