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

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

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

An неограниченная грамматика это формальная грамматика ${displaystyle G = (N, Sigma, P, S)}$ , куда ${displaystyle N}$ - конечный набор нетерминальных символов, ${displaystyle Sigma}$ конечный набор терминальные символы, ${displaystyle N}$ и ${displaystyle Sigma}$ не пересекаются,^{[примечание 1]} ${displaystyle P}$ конечный набор правила производства формы ${displaystyle alpha o eta}$ куда ${displaystyle alpha}$ и ${displaystyle eta}$ строки символов в ${displaystyle Ncup Sigma}$ и ${displaystyle alpha}$ не пустая строка, и ${displaystyle Sin N}$ - это специально обозначенный стартовый символ.^[1]^:220 Как следует из названия, нет никаких реальных ограничений на типы производственных правил, которые могут иметь неограниченные грамматики.^{[заметка 2]}

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

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

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

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

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

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

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

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

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

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

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

Примечания

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