Лекция 7 Formal gramatika

Формал грамматика

Определение формальной грамматики и языка

Формальная грамматика – это математическая система, определяющая язык посредством порождающих правил.
Определение 1.9. Формальной грамматикой называется четверка вида:







Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского, регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.
Регулярная грамматика — формальная грамматика типа 3 по иерархии Хомского, регулярные грамматики определяют в точности все регулярные языки, и поэтому эквивалентны конечным автоматам и регулярным выражениям. Регулярные грамматики являются подмножеством контекстно-свободных.
Контекстно-свободная грамматика (КС-грамматика, бесконтекстная грамматика) — частный случай формальной грамматики (тип 2 по иерархии Хомского), у которой левые части всех продукций являются одиночными нетерминалами (объектами, обозначающими какую-либо сущность языка (например: формула, арифметическое выражение, команда) и не имеющими конкретного символьного значения). Смысл термина «контекстно-свободная» заключается в том, что есть возможность применить продукцию к нетерминалу, причём независимо от контекста этого нетерминала (в отличие от общего случая неограниченной грамматики Хомского).
Контекстно-зависимая грамматика ( CSG ) является формальной грамматикой , в которой левые стороны и правые стороны каких - либо правила производства могут быть окружены контекстом терминальных и нетерминальных символов . Контекстно-зависимые грамматики являются более общими, чем контекстно-свободные , в том смысле, что есть языки, которые могут быть описаны с помощью CSG, но не контекстно-свободных грамматик. Контекстно-зависимые грамматики менее общие (в том же смысле), чем неограниченные грамматики . Таким образом, CSG расположены между контекстно-свободной и неограниченной грамматиками в иерархии Хомского .
Хомский ввел контекстно-зависимые грамматики как способ описания синтаксиса естественного языка, когда часто бывает, что слово может или не может быть подходящим в определенном месте в зависимости от контекста. Уолтер Савич раскритиковал терминологию «контекстно-зависимая» как вводящую в заблуждение и предложил «не стирать» как лучшее объяснение различия между CSG и неограниченной грамматикой .
К нулевому классу относятся все формальные грамматики. Элементы этого класса называются неограниченными грамматиками (англ. unrestricted grammars), поскольку на них не накладывается никаких ограничений. Они задают все языки, которые могут быть распознаны машиной Тьюринга. Эти языки также известны как рекурсивно перечислимые (англ. recursively enumerable).
Правила можно записать в виде:
α→βα→β, где αα — любая непустая цепочка, содержащая хотя бы один нетерминальный символ, а ββ — любая цепочка символов из алфавита.