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

       

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


Определение 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, порождаемый грамматикой

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



Содержание раздела