- Язык: порождаемый грамматикой $G:S\to SS\mid a\mid b$ — все непустые строки над $\{a,b\}$: $L(G)=\{a,b{\}}^{+}$.
- Класс по иерархии Хомского: язык регулярный (Type-3). Грамматика как запись — контекстно‑свободная (Type-2) и не является праволинейной, но порождаемый ею язык принадлежит классу Type‑3.
- Неоднозначность: грамматика неоднозначна. Для любой строки длины $n\ge 3$ существует более одной разметки (разных бинарных деревьев разбиения); число различных деревьев для строки длины $n$ равно каталанову числу
$${\mathrm{Cat}}_{n-1}=\frac{1}{n}\left(\genfrac{}{}{0ex}{}{2n-2}{n-1}\right),$$ напр., для $w=aaa$ есть две разные левые/правые ассоциации:
$$S\Rightarrow SS\Rightarrow SSS\Rightarrow aSS\Rightarrow aaS\Rightarrow aaa$$ и
$$S\Rightarrow SS\Rightarrow SSS\Rightarrow SaS\Rightarrow aaS\Rightarrow aaa.$$
- Преобразование в эквивалентное регулярное описание: регулярное выражение
$$(a\mid b{)}^{+}$$ Можно дать детерминированный автомат: $Q=\{q_0,q_1\}$, начальное $q_0$, принимающее $F=\{q_1\}$, переходы
$$\delta (q_0,a)=\delta (q_0,b)=q_1,\delta (q_1,a)=\delta (q_1,b)=q_1.$$
Эквивалентная (нераспространённая и однозначная) праволинейная грамматика:
$$S\to aS\mid bS\mid a\mid b,$$ которая генерирует $(a\mid b{)}^{+}$ и не даёт неоднозначности (парсинг однозначно соответствует последовательности символов).
- Методы устранения неоднозначности и применимость:
- Для данного языка достаточно заменить правило $S\to SS$ на праволинейные правила (как выше) — стандартный способ для регулярных языков: построить NFA/DFA или праволинейную грамматику (конструкция гарантированно убирает неоднозначность для регулярных языков).
- В общем для контекстно‑свободных языков неоднозначность не всегда устранима: существуют фундаментально (встроенно) неоднозначные CFL; для них невозможно получить эквивалентную однозначную CFG. Для пригодных случаев используются методы рефакторинга грамматики, введение приоритетов/ассоциативности, преобразования в нормальные формы и попытки получить детерминированные подклассы (LL(k), LR(k)) — но успех зависит от языка.