Классификация формальных грамматик и задаваемых ими языков, согласно которой они делятся на 4 класса по их условной сложности. (Класс 0, Класс 1, Класс 2, Класс 3)
- Простейшие конструкции (идентификаторы, строки, константы, языки ассемблера, командные процессоры)
- Распознаются автоматами с магазинной памятью. Широко применяются для описания синтаксиса языков программирования
- практически любой формальный язык, анализ текстов на естественных языках (неукорачивающая грамматика, контекстно-зависимая грамматика). Сложные
- Языки, порождаемые всеми возможными грамматиками. Распознаются машиной Тьюринга. Чисто теоретический интерес (рекурсивно-перечислимые языки)
Связанные определения/теоремы/следствия/утверждения: