Проблема однозначности

Теорема 16.2.1.

Пусть . Тогда не существует алгоритма, позволяющего по произвольной контекстно-свободной грамматике G над алфавитом

узнать, является ли грамматика G однозначной.

Доказательство. Рассмотрим язык . Следуя доказательству теоремы 9.4.3, построим грамматику G для этого языка, исходя из грамматик и .

Грамматика G является неоднозначной тогда и только тогда, когда постовская система соответствия

имеет решение.

Упражнение 16.2.2.

Однозначна ли контекстно-свободная грамматика