Иерархия Хомского
-
Иерархия Хомского
- Иерархия Хомского описывает классы формальных грамматик в теории формальных языков.
- Ноам Хомский предложил четыре класса грамматик, каждый из которых генерирует более сложные языки.
- Каждый класс может полностью генерировать языки младших классов.
-
История и развитие
- Общая идея иерархии была впервые описана Хомским в книге «Три модели описания языка».
- Марсель-Пол Шютценбергер внес вклад в развитие теории формальных языков.
- Математики также разрабатывали модели вычислений, которые оказались эквивалентными грамматикам Хомского.
-
Классы грамматик
- Обычные грамматики генерируют обычные языки и ограничены одним нетерминалом и одним терминалом в правилах.
- Контекстно-свободные грамматики генерируют контекстно-свободные языки и распознаются недетерминированными автоматами pushdown.
- Контекстно-зависимые грамматики генерируют контекстно-зависимые языки и распознаются линейными ограниченными автоматами.
- Рекурсивно перечислимые грамматики генерируют все языки, которые могут быть распознаны машиной Тьюринга.
-
Примеры и приложения
- Примеры языков, генерируемых грамматиками разных типов, включают регулярные выражения и языки программирования.
- Контекстно-зависимые языки используются в синтаксическом анализе языков программирования.
-
Нормальная форма Хомского
- Нормальная форма Хомского представляет собой упрощенную форму грамматики, которая используется для доказательства свойств грамматик.
Полный текст статьи: