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

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

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

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

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