Расширение к CFG, что это?
Рассмотрим следующее расширение для контекстно-свободных грамматик, которое позволяет правилам иметь в левой части один (или более) терминал в правой части нетерминала. То есть правила вида:
A b -> ...
Правая часть может быть чем угодно, как в контекстно-свободных грамматиках. В частности, не требуется, чтобы правая сторона имела точно такой же символ терминала в конце. В этом случае это расширение будет контекстно-зависимым. Но терминал - это не просто контекст. Иногда этот терминал называется "pushback".
Понятно, что это уже не CFG (тип-2). Включает в себя тип-1. Но что это? Неужели тип-0 уже?
Это конкретное расширение разрешено в Грамматиках Определенного предложения dcg в Прологе. (Чтобы избежать недоразумений, я не рассматриваю здесь полные расширения Пролога. Т.е. я предполагаю, что терминалы происходят из конечного алфавита и не являются произвольными терминами, также я не рассматриваю дополнительные аргументы Пролога, которые разрешены в DCG, которые также входят в 0 уже.)
Редактировать: вот более простой способ описать расширение: добавить в CFG правила вида
A b -> <epsilon>
3 ответа
Чтобы ответить на мой вопрос относительно формализма Prolog DCG, это расширение теперь называется полуконтекстом. См. N253 DIN Draft для DCG 2014-04-08 - ИСО / МЭК WDTR 13211-3:2014-04-08
Дано
a1, [b] --> ... .
a2, [b,b] --> ... .
Терминальная последовательность [b] теперь является полуконтекстом, а также терминальной последовательностью [b,b],
Если бы в конце правила появилась та же самая терминальная последовательность, у нас был бы контекст:
a3, [b,b] --> ..., [b,b].
Таким образом, "полу" означает здесь "половина" - аналогично полугруппе, в которой сохраняется половина алгебраических свойств группы.
Вот частичный ответ:
Грамматика относится к типу 0. Контекстно-зависимая грамматика (тип-1) имеет правила вида wAx -> wBx где w и x - строки терминалов и нетерминалов, и B не является пустым. Обратите внимание, что, поскольку B не пусто, |wAx| <= |wBx|, Ваша грамматика имеет правила вида Ax -> z где z является строкой терминалов и нетерминалов и может быть пустым, а x может быть удален. Это нарушает два принципа РГС.
Неудовлетворительно я не ответил на две вещи:
- Язык генерируется вашей грамматикой типа 1? Грамматика типа 0, но это не означает, что язык не может быть типа 1. Например, обычные языки (тип-3) могут быть описаны CFG (тип-2).
Является ли язык рекурсивным? Это важно, поскольку, если это так, язык является разрешимым (не страдает от проблемы остановки).
В настоящее время я пытаюсь доказать второй пункт, но он, вероятно, не в моих силах.
Да это типа 0, я думаю. Принцип для первых 3 типов (3, 2 и 1) заключается в том, что они не могут выполнять редукцию. Это только генеративные типы.
Здесь вы можете преобразовать терминал в epsilon, чтобы он был 0.