Проблемы контекстной свободности



Мы поможем в написании ваших работ!


Мы поможем в написании ваших работ!



Мы поможем в написании ваших работ!


ЗНАЕТЕ ЛИ ВЫ?

Проблемы контекстной свободности



Определение 16.5.1. Пусть , , , где и для всех i. Обозначим через язык .

Лемма 16.5.2. Язык является контекстно-свободным при любых и .

Доказательство Утверждение следует из теорем 9.4.4 и 9.4.2.

Лемма 16.5.3. Рассмотрим алфавит . Пусть и , где , и для всех i. Тогда язык является контекстно-свободным в том и только том случае, когда постовская система соответствия не имеет решений.

Доказательство. Пусть - решение постовской системы соответствия , где для всех i. Положим

Легко проверить, что , и язык L0 является автоматным. Очевидно, что

Можно доказать (например, используя лемму 9.1.1), что язык не является контекстно-свободным. Согласно теореме 9.6.1 язык также не~является контекстно-свободным.

Обратно, если постовская система соответствия не имеет решений, то .

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

Доказательство. Достаточно построить по постовской системе соответствия , где , и для всех i выполняется , и , контекстно-свободную грамматику G1, порождающую язык , и контекстно-свободную грамматику G2, порождающую язык . С учетом леммы 16.5.3 неразрешимость рассматриваемой задачи сводится к неразрешимости проблемы соответствий Поста рассуждением, аналогичным приведенному в доказательстве теоремы 16.4.2.

Лемма 16.5.5. Рассмотрим алфавит . Язык является контекстно-свободным при любых и .

Доказательство. Положим . Язык можно представить в виде объединения пяти контекстно-свободных языков

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

Доказательство. Рассмотрим алфавит . Достаточно построить по постовской системе соответствия , где , и для всех i выполняется , и , контекстно-свободную грамматику G, порождающую язык . С учетом леммы 16.5.5 неразрешимость рассматриваемой задачи сводится к~неразрешимости проблемы соответствий Поста рассуждением, аналогичным приведенному в доказательстве теоремы 16.4.2.

Лемма 16.5.7. Рассмотрим алфавит . Язык является контекстным при любых и .

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

Доказательство. Достаточно построить по постовской системе соответствия , где , и для всех i выполняется , и , контекстную грамматику G, порождающую язык .

Упражнение 16.5.9. Является ли контекстно-свободным язык , где язык L порождается грамматикой

 

 



Последнее изменение этой страницы: 2021-04-04; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 35.175.191.36 (0.017 с.)