Найти эквивалентную грамматику LR для одного и того же числа грамматик "a" и "b"?

Question

Я не могу найти эквивалентную грамматику LR для:

S → aSbS | bSaS | ε

которые я думаю, распознают строки с тем же числом "а", что и "б".

Что бы обойти это? Можно ли найти и грамматику LR для этого?

Заранее спасибо!

РЕДАКТИРОВАТЬ:

Я нашел то, что я считаю эквивалентной грамматикой, но я не смог доказать это.

Я думаю, что мне нужно доказать, что оригинальная грамматика генерирует язык выше, а затем доказать, что язык генерируется для следующей эквивалентной грамматики. Но я не уверен, как это сделать. Как я должен это делать?

S → aBS | BAS | ε

B → b | уток

A → a | блеять

Заранее спасибо...

PS: я уже доказал, что эта новая грамматика - LL(1), SLR(1), LR(1) и LALR(1).

Answer 1

Если грамматика не связана напрямую с другой грамматикой - например, с помощью стандартных преобразований, таких как нормализация, исключение нулевого производства и т. Д., - доказать, что две грамматики получают один и тот же язык, очень сложно, не зная, что это за язык. Обычно легче доказать (независимо), что каждая грамматика выводит язык.

Первая грамматика, которую вы предоставляете:

S → aSbS | bSaS | ε

на самом деле выводит язык всех строк по алфавиту {a, b}* где число a s совпадает с числом b s. Мы можем доказать это в двух частях: во-первых, каждое предложение, распознаваемое грамматикой, обладает этим свойством, и, во-вторых, каждое предложение, обладающее этим свойством, может быть получено с помощью этой грамматики. Оба доказательства основаны на индукции.

Для прямого доказательства мы поступим по индукции по числу дифференцирований. Предположим, у нас есть какой-то вывод S → α → β → … → ω где все греческие буквы представляют последовательности нетерминалов и терминалов.

Если длина деривации точно равна нулю, так что она начинается и заканчивается S, то в любом производном предложении нет терминалов, поэтому ясно, что каждое производное предложение имеет одинаковое число a s и b s. (Базовый шаг)

Теперь для шага индукции. Предположим, что каждый вывод длины i как известно, заканчивается производным предложением, которое имеет одинаковое число a s и b s. Мы хотим доказать из этой предпосылки, что каждый вывод длины i+1 заканчивается предложением, которое имеет одинаковые номера a s и b s. Но это также очевидно: каждый из трех возможных этапов производства сохраняет паритет.

Теперь давайте рассмотрим противоположное направление: каждое предложение с одинаковым числом a s и b s может быть получено из этой грамматики. Мы сделаем это по индукции по длине строки. Нашей вводной предпосылкой будет то, что если это так, то для каждого j ≤ i, каждое предложение с точно j с и j b s имеет происхождение от S тогда каждое предложение точно i+1 с и i+1 б с. (Здесь мы рассматриваем только предложения, состоящие только из терминалов.)

Рассмотрим такую ​​глупость. Это либо начинается с а или б. Предположим, что он начинается с a: тогда в предложении есть по крайней мере один b, так что префикс, заканчивающийся этим b, имеет одинаковый номер каждого терминала. (Думайте о струне как о проходе по квадратной сетке: каждое a движется по диагонали вверх и вправо на одну единицу, а каждое b движется по диагонали вниз и вправо. Поскольку конечная точка находится точно на той же высоте, что и начальная точка, и червоточин нет на графике, как только мы поднимаемся, мы должны рано или поздно вернуться к начальной высоте, которая является префиксом, заканчивающимся b.) Таким образом, внутренняя часть этого префикса (все, кроме a в начале и b в конце) сбалансирована, как и остаток строки. Оба они короче, поэтому по предположению индукции они могут быть получены из S, Делая эти замены, мы получаем S S S, который может быть получен из S, Аналогичный аргумент применяется к строкам, начинающимся с b. Опять же, базовый шаг тривиален.

Так что это в основном процедура доказательства, которую вам нужно адаптировать для вашей грамматики.

Удачи.

---

Кстати, этот вопрос также может быть задан на cs.stackexchange.com или math.stackexchange.com, где доступен MathJax. MathJax делает написание математических доказательств гораздо менее утомительным, так что вы можете легко найти более читаемые ответы там.