Математическая теория формальных языков


           

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


Теорема 16.2.1.

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

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

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

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

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

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

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



Содержание  Назад  Вперед





Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий