Грамматика
S -> a S b | S S | ε
неоднозначна.

1) Контрпример (две разные деревья вывода для одной и той же строки)

Возьмём строку w = "aabb". Две разные позиции корня в дереве дают разные деревья, но одинаковую выведенную строку.

Дерево 1 (вложение):
S
└─ a S b
└─ a S b
└─ ε

Это соответствует левому выводу
S ⇒ a S b ⇒ a a S b b ⇒ a a ε b b = aabb.

Дерево 2 (конкатенация + пустой справа):
S
└─ S S
├─ S
│ └─ a S b
│ └─ a S b
│ └─ ε
└─ S
└─ ε

Это соответствует выводу
S ⇒ S S ⇒ (a S b) S ⇒ (a a S b b) S ⇒ aabb S ⇒ aabb ε = aabb.

Деревья различны (в первом корень применяет правило a S b, во втором — правило S S), но дают одну и ту же строку. Значит грамматика неоднозначна.

2) Эквивалентная недвусмысленная грамматика

Язык, порождаемый исходной грамматикой, — язык правильных (сбалансированных) скобочных последовательностей с парой скобок a...b (Dyck‑язык с одной парой). Для этого языка существует простая недвусмысленная грамматика:

S -> a S b S | ε.

Интуитивно: любая ненулевая правильная последовательность имеет вид a u b v, где u и v — правильные последовательности; поэтому правило a S b S однозначно описывает первое совпадение a с соответствующей b и остаток. Формально:

Эквивалентность L(G) = L(G'): по рекуррентной структуре обе грамматики генерируют точно те же правильные скобочные строки (любая продукция a S b в исходной грамматике либо задаёт вложение, либо в комбинации с S S даёт то же разбиение a u b v).Недвусмысленность G': доказательство по индукции по длине слова. Для пустой строки разбор единственный. Для ненулевой строки w первая буква обязана быть a; наиболее левое соответствующее b (первый индекс, где число a и b в префиксе сравнялось) уникален, поэтому разложение w = a u b v однозначно, а по предположению индукции u и v имеют единственные разборы, следовательно разбор w единственный.

Таким образом преобразование выражается простым объединением правила конкатенации S S в правиле a S b S, что устраняет неоднозначность, сохраняя язык.

Замечание: это стандартный приём для грамматик для правильных скобочных последовательностей — выбирать правило, которое явно разбирает строку по первому совпадающему a–b, благодаря чему разбор становится уникальным.