Линейная грамматика

Линейная грамматика — это контекстно-свободная грамматика, такая что правая часть любого её правила вывода содержит не больше одного нетерминала.

Линейный язык — язык, порождаемый некоторой линейной грамматикой.

Пример

Простым примером линейной грамматики служит грамматика с множеством нетерминалов , алфавитом , начальным нетерминалом и правилами вывода

Данная грамматика порождает нерегулярный язык .

Соответствие регулярным языкам

Выделяют особые виды линейных грамматик:

  • Леволинейная грамматика, в которой нетерминалы всегда находятся в начале правых частей правил вывода;
  • Праволинейная грамматика, в которой нетерминалы всегда находятся в конце правых частей правил вывода.

Каждый из этих видов в отдельности описывает в точности класс регулярных языков. Регулярной грамматикой называют грамматику, являющуюся либо леволинейной, либо праволинейной.

Другим особым типом линейной грамматики является:

  • Линейная грамматика, в которой нетерминалы всега находятся либо в начале, либо в конце правых частей правил вывода.

Добавлением новых нетерминалов можно привести любую линейную грамматику к описанному выше виду, не меняя при этом порождаемый грамматикой язык. Например, может быть приведена к виду

Таким образом, линейные грамматики такого вида порождают такой же класс языков, что и произвольные линейные грамматки.

Выразительность

Все регулярные языки являются линейными. Классическим примером линейного, но не регулярного языка является описанный выше язык . Все линейные языки являются контекстно-свободными. Примером контекстно-свободного, но не линейного языка является язык Дика, состоящий из правильных скобочных последовательностей. Таким образом, регулярные языки являются собственным подмножеством линейных языков, которые, в свою очередь, являются собственным подмножеством контекстно-свободных языков.

В то время, как все регулярные линейные языки являются детерминированными, существуют недетерминированные линейные языки. Примером такого языка может служить язык палиндромов чётной длины над алфавитом , который задаётся линейной грамматикой . Произвольное слово данного языка не может быть разобрано автоматом с магазинной памятью без считывания всех его символов, поэтому язык является недетерминированным[1]. Задача проверки заданного контекстно-свободного языка на то, является ли он линейным, неразрешима[2].

Примечания

  1. Hopcroft J. E., Motwani R., Ullman J. D. Introduction to Automata Theory, Languages, and Computation (англ.). — 2 ed. Addison-Wesley, 2001. — P. 249—253.
  2. Greibach, Sheila. The Unsolvability of the Recognition of Linear Context-Free Languages (англ.) // Journal of the ACM : journal. — 1966. — October (vol. 13, no. 4). doi:10.1145/321356.321365.
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.