Приведён контекстно‑свободный грамматический фрагмент: S -> S S | 'a' — докажите или опровергните неоднозначность грамматики, при необходимости постройте эквивалентную невозмутительную (unambiguous) грамматику или аргумент о невозможности устранить неоднозначность для данного языка
Грамматика S -> S S | 'a' амбиґу́озна. Доказ (контрпример): строка "aaa" имеет две разные синтаксические деревья (и, соответственно, два разных вывода).
Дерево 1 (лево‑ассоциативно): ((a a) a)
S SS -> 'a'S -> 'a'S -> 'a'
Дерево 2 (право‑ассоциативно): (a (a a))
S S -> 'a'SS -> 'a'S -> 'a'
Оба дерева порождают одну и ту же строку "aaa", значит грамматика неоднозначна. Более общо: для строки a^n число различных деревьев соответствует числу различных способов скобочного разбиения n элементов (числа Каталана) — для n≥3 это больше единицы, следовательно неоднозначность подтверждается для всех n≥3.
Однако язык L = { a^n | n ≥ 1 } сам по себе не является неустранимо неоднозначным (не inherently ambiguous). Можно дать эквивалентную невозмутительную (unambiguous) грамматику, например: S -> 'a' | S 'a' (или праворекурсивно: S -> 'a' S | 'a').
Краткое обоснование невозмутительности: в грамматике S -> 'a' | S 'a' в любой выводной цепочке в каждый момент есть ровно одна нетерминальная S, поэтому количество применений правила S -> S 'a' однозначно равно длине строки минус 1, и порядок применений фиксирован — для каждой строки a^n ровно один вывод/дерево. Следовательно грамматика невозмутительная и порождает тот же язык a+.
Грамматика
S -> S S | 'a'
амбиґу́озна. Доказ (контрпример): строка "aaa" имеет две разные синтаксические деревья (и, соответственно, два разных вывода).
Дерево 1 (лево‑ассоциативно): ((a a) a)
SSS -> 'a'S -> 'a'S -> 'a'
Дерево 2 (право‑ассоциативно): (a (a a))
SS -> 'a'SS -> 'a'S -> 'a'
Оба дерева порождают одну и ту же строку "aaa", значит грамматика неоднозначна. Более общо: для строки a^n число различных деревьев соответствует числу различных способов скобочного разбиения n элементов (числа Каталана) — для n≥3 это больше единицы, следовательно неоднозначность подтверждается для всех n≥3.
Однако язык L = { a^n | n ≥ 1 } сам по себе не является неустранимо неоднозначным (не inherently ambiguous). Можно дать эквивалентную невозмутительную (unambiguous) грамматику, например:
S -> 'a' | S 'a'
(или праворекурсивно: S -> 'a' S | 'a').
Краткое обоснование невозмутительности: в грамматике S -> 'a' | S 'a' в любой выводной цепочке в каждый момент есть ровно одна нетерминальная S, поэтому количество применений правила S -> S 'a' однозначно равно длине строки минус 1, и порядок применений фиксирован — для каждой строки a^n ровно один вывод/дерево. Следовательно грамматика невозмутительная и порождает тот же язык a+.