1) Демонстрация неоднозначности для строки $"aaa"$ в грамматике
$$S\to SS\mid "a"$$ Две разные разборки (группировки) дают одну и ту же строку:
- Разборка слева-ассоциативная $((aa)a)$:
$$S\Rightarrow SS\Rightarrow SSS\Rightarrow "a"SS\Rightarrow "a""a"S\Rightarrow "a""a""a".$$
- Разборка справа-ассоциативная $(a(aa))$:
$$S\Rightarrow SS\Rightarrow SSS\Rightarrow S"a"S\Rightarrow "a""a""a".$$
Обе дают одну и ту же итоговую строку $"aaa"$ при разных деревьях разбора ⇒ грамматика амбигуэзна.
2) Эквивалентная без неoднозначности грамматика (порождает $\{a{\}}^{+}$ и однозначна):
$$S\to "a"S\mid "a".$$ Для любой длины $n$ строка $a^n$ имеет единственный цепной (право-рекурсивный) разбор — однозначность.
3) Преобразование в нормальную форму Хомского (CNF) для использования CYK.
Введём нетерминал $A$ для терминала $a$:
$$A\to "a".$$ Приведём правила так, чтобы правая часть была либо два нетерминала, либо один терминал:
$$S\to AS\mid "a",A\to "a".$$ Здесь $S\to AS$ — форма $A\to BC$, а $S\to "a"$ и $A\to "a"$ — формы $A\to a$. Это CNF-подобная форма, пригодная для CYK (при необходимости можно избавиться от дублирующего правила $S\to "a"$, но для CYK такое представление допустимо).
Кратко: исходная грамматика амбигуэзна (пример $"aaa"$ показан); язык регулярный $\{a{\}}^{+}$, поэтому существует однозначная грамматика, например $S\to "a"S\mid "a"$; для CYK можно использовать приведённую CNF-версию с вводом $A\to "a"$.