Математическая теория формальных языков
Проблема автоматности
Лемма 16.4.1.
Пусть , , где ,
и
для всех i. Тогда язык
является автоматным в том и только том случае, когда постовская система соответствия
не имеет решений.
Доказательство Пусть - решение постовской системы соответствия , где
для всех i. Положим
Легко проверить, что ,
и язык L0
является автоматным. Очевидно, что
Как было установлено в упражнении 3.4.2, язык
не является автоматным. Согласно теореме 3.2.1 язык
не является автоматным. Следовательно, и язык не является автоматным.
Обратно, если постовская система соответствия
не имеет решений, то , а этот язык является автоматным.
Теорема 16.4.2.
Пусть . Тогда не существует алгоритма, позволяющего по произвольной контекстно-свободной грамматике G над алфавитом
узнать, является ли автоматным язык L(G).
Доказательство Докажем утверждение теоремы для случая . Из леммы 16.4.1 следует, что если бы проблема распознавания автоматности языка L(G) для контекстно-свободных грамматик над алфавитом
была разрешима, то также была бы разрешима проблема соответствий Поста для постовских систем соответствия , где ,
и
для всех i. Но тогда была бы разрешима проблема соответствий Поста для всех постовских систем соответствия над алфавитом {a,b} (если
для некоторого i, то рассматриваемая постовская система соответствия имеет решение, а именно (i)).
Упражнение 16.4.3.
Является ли автоматным язык, порождаемый грамматикой
Упражнение 16.4.4.
Является ли автоматным язык, порождаемый грамматикой
Упражнение 16.4.5.
Является ли автоматным язык, порождаемый грамматикой
Упражнение 16.4.6.
Является ли автоматным язык, порождаемый грамматикой
