Грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, можно построить единственный левосторонний (и единственный правосторонний) вывод. Или, что то же самое: грамматика называется однозначной, если для каждой цепочки символов языка, заданного этой грамматикой, существует единственное дерево вывода. В противном случае грамматика называется неоднозначной.
Преобразование КС-грамматик
Определение КС-грамматика называется приведенной, если она не имеет циклов, e-правил и бесполезных символов.
Рассмотрим основные алгоритмы приведения КС-грамматик.
Перед всеми другими исследованиями и преобразованиями КС-грамматик выполняется проверка существования языка грамматики.
Проверка существования языка грамматики