Приведён контекстно‑свободный грамматический фрагмент: S -> S S | 'a' — докажите или опровергните неоднозначность грамматики, при необходимости постройте эквивалентную невозмутительную (unambiguous) грамматику или аргумент о невозможности устранить неоднозначность для данного языка

2 Окт в 13:42
10 +1
0
Ответы
1

Грамматика
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+.

2 Окт в 14:20
Не можешь разобраться в этой теме?
Обратись за помощью к экспертам
Гарантированные бесплатные доработки в течение 1 года
Быстрое выполнение от 2 часов
Проверка работы на плагиат
Поможем написать учебную работу
Прямой эфир