Неограниченная грамматика

Теория языка

В теории автоматов класс неограниченных грамматик (также называемых полу-Туэ , грамматиками типа 0 или грамматиками фразовой структуры ) является наиболее общим классом грамматик в иерархии Хомского . На порождения неограниченной грамматики не накладывается никаких ограничений, за исключением того, что каждая из их левых частей не является пустой. ^{[1] : 220} Этот класс грамматик может генерировать произвольные рекурсивно перечислимые языки .

Формальное определение

Неограниченная грамматика — это формальная грамматика , где ${\textstyle G=(N,T,P,S)}$

• ${\displaystyle N}$— это конечный набор нетерминальных символов ,
• ${\displaystyle T}$представляет собой конечный набор терминальных символов с и непересекающимися , ^{[примечание 1]} ${\displaystyle N}$ ${\displaystyle T}$
• ${\displaystyle P}$представляет собой конечный набор правил производства вида , где и являются строками символов , а не является пустой строкой, и ${\displaystyle \alpha \to \beta ,}$ ${\displaystyle \alpha }$ ${\displaystyle \beta }$ ${\displaystyle N\cup T}$ ${\displaystyle \alpha }$

• ${\displaystyle S\in N}$это специально обозначенный начальный символ. ^{[1] : 220}

Как следует из названия, не существует реальных ограничений на типы правил продукций, которые могут иметь неограниченные грамматики. ^{[примечание 2]}

Эквивалентность машинам Тьюринга

Неограниченные грамматики характеризуют рекурсивно перечислимые языки. Это то же самое, что сказать, что для каждой неограниченной грамматики существует некоторая машина Тьюринга, способная распознавать и наоборот. При наличии неограниченной грамматики такую ​​машину Тьюринга достаточно просто построить, как двухленточную недетерминированную машину Тьюринга . ^{[1] : 221} Первая лента содержит входное слово для проверки, а вторая лента используется машиной для генерации сентенциальных форм из . Затем машина Тьюринга делает следующее: ${\displaystyle G}$ ${\displaystyle L(G)}$ ${\displaystyle w}$ ${\displaystyle G}$

1. Начните с левой стороны второй ленты и несколько раз выберите перемещение вправо или текущую позицию на ленте.
2. Недетерминированно выбрать продукцию из продукции в . ${\displaystyle \beta \to \gamma }$ ${\displaystyle G}$
3. Если появляется в какой-то позиции на второй ленте, замените на в этой точке, возможно, сместив символы на ленте влево или вправо в зависимости от относительной длины и (например, если длиннее , сместите символы ленты влево). ${\displaystyle \beta }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$ ${\displaystyle \beta }$ ${\displaystyle \gamma }$
4. Сравните полученную форму предложения на ленте 2 со словом на ленте 1. Если они совпадают, то машина Тьюринга принимает слово. Если нет, то машина Тьюринга возвращается к шагу 1.

Легко видеть, что эта машина Тьюринга будет генерировать все и только сентенциальные формы на своей второй ленте после того, как последний шаг будет выполнен произвольное число раз, поэтому язык должен быть рекурсивно перечислимым. ${\displaystyle G}$ ${\displaystyle L(G)}$

Обратное построение также возможно. При наличии некоторой машины Тьюринга можно создать эквивалентную неограниченную грамматику ^{[1] : 222,} которая даже использует только продукции с одним или несколькими нетерминальными символами в левой части. Следовательно, произвольная неограниченная грамматика всегда может быть эквивалентно преобразована так, чтобы подчиняться последней форме, путем преобразования ее в машину Тьюринга и обратно. Некоторые авторы ^{[ требуется ссылка ]} используют последнюю форму в качестве определения неограниченной грамматики .

Вычислительные свойства

Проблема принятия решения о том, может ли данная строка быть сгенерирована данной неограниченной грамматикой, эквивалентна проблеме о том, может ли она быть принята машиной Тьюринга, эквивалентной этой грамматике. Последняя проблема называется проблемой остановки и неразрешима. ${\displaystyle s}$

Рекурсивно перечислимые языки замкнуты относительно звезды Клини , конкатенации , объединения и пересечения , но не относительно разности множеств ; см. Рекурсивно перечислимые языки#Свойства замыкания .

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

Смотрите также

• Лямбда-исчисление
• Система Semi-Thue – не различает терминальные и нетерминальные символы, допускает пустые левые части

Примечания

1. На самом деле, не является строго необходимым, поскольку неограниченные грамматики не делают реального различия между ними. Обозначение существует исключительно для того, чтобы знать, когда прекратить генерировать сентенциальные формы грамматики; точнее, язык, распознаваемый , ограничен строками терминальных символов. ${\displaystyle T\cap N=\emptyset }$ ${\displaystyle L(G)}$ ${\displaystyle G}$
2. Хотя Хопкрофт и Ульман (1979) не упоминают мощности , , явно, доказательство их теоремы 9.3 (построение эквивалентной машины Тьюринга из заданной неограниченной грамматики, стр. 221, см. Раздел #Эквивалентность машинам Тьюринга) неявно требует конечности и конечной длины всех строк в правилах . Любой член или , который не встречается в , может быть опущен без влияния на сгенерированный язык. ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle P}$ ${\displaystyle N}$ ${\displaystyle T}$ ${\displaystyle P}$

Ссылки

1. Хопкрофт, Джон ; Ульман, Джеффри Д. (1979). Введение в теорию автоматов, языки и вычисления (1-е изд.). Эддисон-Уэсли. ISBN 0-201-44124-1.