Если у не зависящей от контекста грамматики G есть несколько деривационных деревьев для некоторой строки w ∈ L (G) , она называется неоднозначной грамматикой . Для некоторой строки, сгенерированной из этой грамматики, существует несколько производных справа и слева.
проблема
Проверьте, соответствует ли грамматика G правилам производства —
X → X + X | X * X | X |
неоднозначно или нет.
Решение
Давайте выясним дерево деривации для строки «a + a * a». У него два крайних левых вывода.
Вывод 1 — X → X + X → a + X → a + X * X → a + a * X → a + a * a
Разобрать дерево 1 —
Вывод 2 — X → X * X → X + X * X → a + X * X → a + a * X → a + a * a
Разобрать дерево 2 —
Поскольку для одной строки «a + a * a» существует два дерева разбора, грамматика G неоднозначна.