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

редактировать

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

Содержание

1 Формальное определение
2 Эквивалентность машинам Тьюринга
3 Вычислительные свойства
4 См. Также
5 Примечания
6 Ссылки

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

неограниченная грамматика - это формальная грамматика $G = (N, Σ, P, S) {\ displaystyle G = (N, \ Sigma, P, S)}$ $G = (N, \ Sigma, P, S)$ , где $N {\ displaystyle N}$ $N$ - конечный набор нетерминальных символов, $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ - конечный набор терминальных символов, $N {\ displaystyle N}$ $N$ и $Σ {\ displaystyle \ Sigma}$ $\ Sigma$ не пересекаются, $P {\ displaystyle P}$ $P$ - конечный набор производственных правил в форме $α → β {\ displaystyle \ alpha \ to \ beta}$ $\ alpha \ to \ beta$ где $α {\ displaystyle \ alpha}$ $\ alpha$ и $β {\ displaystyle \ beta}$ $\ beta$ - строки символов в $N ∪ Σ {\ displaystyle N \ cup \ Sigma}$ $N \ cup \ Sigma$ и $α {\ displaystyle \ alpha}$ $\ alpha$ не пустая строка, a nd $S ∈ N {\ displaystyle S \ in N}$ $S \ in N$ - специально обозначенный начальный символ. Как следует из названия, нет никаких реальных ограничений на типы производственных правил, которые могут иметь неограниченные грамматики.

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

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

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

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

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

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

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

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

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

См. Также

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

Примечания

Ссылки