Линейная грамматикаЛинейная грамматика — это контекстно-свободная грамматика, такая что правая часть любого её правила вывода содержит не больше одного нетерминала. Линейный язык — язык, порождаемый некоторой линейной грамматикой. ПримерПростым примером линейной грамматики служит грамматика с множеством нетерминалов , алфавитом , начальным нетерминалом и правилами вывода Данная грамматика порождает нерегулярный язык . Соответствие регулярным языкамВыделяют особые виды линейных грамматик:
Каждый из этих видов в отдельности описывает в точности класс регулярных языков. Регулярной грамматикой называют грамматику, являющуюся либо леволинейной, либо праволинейной. Другим особым типом линейной грамматики является:
Добавлением новых нетерминалов можно привести любую линейную грамматику к описанному выше виду, не меняя при этом порождаемый грамматикой язык. Например, может быть приведена к виду Таким образом, линейные грамматики такого вида порождают такой же класс языков, что и произвольные линейные грамматики. ВыразительностьВсе регулярные языки являются линейными. Классическим примером линейного, но не регулярного языка является описанный выше язык . Все линейные языки являются контекстно-свободными. Примером контекстно-свободного, но не линейного языка является язык Дика, состоящий из правильных скобочных последовательностей. Таким образом, регулярные языки являются собственным подмножеством линейных языков, которые, в свою очередь, являются собственным подмножеством контекстно-свободных языков. В то время, как все регулярные линейные языки являются детерминированными, существуют недетерминированные линейные языки. Примером такого языка может служить язык палиндромов чётной длины над алфавитом , который задаётся линейной грамматикой . Произвольное слово данного языка не может быть разобрано автоматом с магазинной памятью без считывания всех его символов, поэтому язык является недетерминированным[1]. Задача проверки заданного контекстно-свободного языка на то, является ли он линейным, неразрешима[2]. Примечания
|
Portal di Ensiklopedia Dunia