Пересечение контекстно-свободных языков



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


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



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


ЗНАЕТЕ ЛИ ВЫ?

Пересечение контекстно-свободных языков



Определение 16.1.1. Рассмотрим алфавит . Пусть , где для всех i. Обозначим через линейную грамматику , где

Обозначим через язык, порождаемый грамматикой .

Лемма 16.1.2. Язык является непустым тогда и только тогда, когда постовская система соответствия имеет решение.

Пример 16.1.3. Рассмотрим постовскую систему соответствия

(то есть n = 2, и ). Решениями этой системы являются последовательности (1, 1, 2), (1, 1, 2, 1, 1, 2) и т. д. Легко убедиться, что

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

Доказательство. Сначала докажем утверждение теоремы для случая . Из леммы 16.1.2 следует, что если бы проблема распознавания свойства для контекстно-свободных грамматик над алфавитом была разрешима, то проблема соответствий Поста тоже была бы разрешима. Поэтому из неразрешимости проблемы соответствий Поста следует неразрешимость проблемы распознавания свойства для контекстно-свободных грамматик над алфавитом .

Чтобы доказать утверждение теоремы для случая (например, ), достаточно заменить в определении символ a на ede, символ b на edde и символ c на eddde.

Лемма 16.1.5. Язык является бесконечным тогда и только тогда, когда постовская система соответствия имеет решение.

Доказательство. Если постовская система соответствия имеет хотя бы одно решение, то она имеет бесконечно много решений.

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

Упражнение 16.1.7. Пусть . Рассмотрим язык L1, порождаемый грамматикой

и язык L2, порождаемый грамматикой

Верно ли, что ?

Упражнение 16.1.8. Пусть . Рассмотрим язык L1, порождаемый грамматикой

и язык , порождаемый грамматикой

Верно ли, что ?

Упражнение 16.1.9. Пусть . Рассмотрим язык L1, порождаемый грамматикой

и язык L2, порождаемый грамматикой

Верно ли, что ?

 

 

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

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

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

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

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



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

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