Математическая теория формальных языков
Проблема однозначности
Теорема 16.2.1.
Пусть . Тогда не существует алгоритма, позволяющего по произвольной контекстно-свободной грамматике G над алфавитом
узнать, является ли грамматика G однозначной.
Доказательство. Рассмотрим язык . Следуя доказательству теоремы 9.4.3, построим грамматику G для этого языка, исходя из грамматик и .
Грамматика G является неоднозначной тогда и только тогда, когда постовская система соответствия
имеет решение.
Упражнение 16.2.2.
Однозначна ли контекстно-свободная грамматика
Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий