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

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

Формальное определение [ править ]

Неограниченная грамматика является формальной грамматикой , где есть конечное множество нетерминальных символов, является конечным множеством терминальных символов , и не пересекается, ^{[примечание 1]} является конечным множеством производственных правил вида где и являются строками символов в и не является пустой строкой, а является специально обозначенным начальным символом. ^[1]^:²²⁰ Как следует из названия, нет никаких реальных ограничений на типы производственных правил, которые могут иметь неограниченные грамматики. ^{[заметка 2]} ${\ Displaystyle G = (N, \ Sigma, P, S)}$ ${\ displaystyle N}$ ${\ displaystyle \ Sigma}$ ${\ displaystyle N}$ ${\ displaystyle \ Sigma}$ $P$ $\alpha \to \beta$ $\alpha$ $\beta$ $N\cup \Sigma$ $\alpha$ $S\in N$

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

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

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

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

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

Вычислительные свойства [ править ]

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

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

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

См. Также [ править ]

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

Примечания [ править ]

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

Ссылки [ править ]

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

[2] На самом деле, в этом нет строгой необходимости, поскольку неограниченная грамматика не делает различий между ними. Обозначение существует исключительно для того, чтобы знать, когда прекратить генерировать сентенциальные формы грамматики; точнее, язык,распознаваемый с помощью, ограничен строками терминальных символов $L(G)$ $G$

[3] Хотя Hopcroft и Ульман (1979)не говоря уже о мощностях,,явно, доказательство их теоремы 9.3 (строительства эквивалентной машины Тьюринга с заданной неограниченной грамматикой, p.221, см Раздел #Equivalence к машинам Тьюринга ) неявно требует конечностии конечной длины всех строк в правилах. Любой членили, который не встречается в,может быть опущен без влияния на сгенерированный язык. $N$ $\Sigma$ $P$ $P$ $P$ $N$ $\Sigma$ $P$

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

[1]