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

         

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


Теорема 9.6.1.

Если L1 - контекстно-свободный язык и L2 - автоматный язык, то язык

является контекстно-свободным.

Доказательство. Пусть - контекстно-свободная грамматика, порождающая язык L1. Без ограничения общности можно считать, что множество P содержит только правила вида

и , где ,

и

(см. теорему 8.3.3). Пусть - конечный автомат, распознающий язык L_2. Без ограничения общности можно считать, что для каждого перехода

выполняется равенство |x| = 1 (см. лемму 2.3.3).

Построим контекстно-свободную грамматику , порождающую язык . Положим

где - новый символ (не принадлежащий множеству ).

Пример 9.6.2.

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

и автоматный язык L2, распознаваемый конечным автоматом , где Q = {1,2}, I = {1}, F = {2},

Тогда язык

порождается контекстно-свободной грамматикой

Здесь S11, S12, S21

и S22

соответствуют символам , ,

и



из доказательства теоремы 9.6.1.

Теорема 9.6.3*.

Если L1 - линейный язык и L2 - автоматный язык, то язык

является линейным.

Пример 9.6.4*.

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

и автоматный язык L2, распознаваемый конечным автоматом , где Q = {1,2,3}, I = {1}, F = {3},

Тогда язык

порождается контекстно-свободной грамматикой

Эту грамматику можно упростить, заменив S11 и S33

на один символ.

Упражнение 9.6.5. Найти контекстно-свободную грамматику для языка , где L1

порождается грамматикой

а язык L2

порождается грамматикой

Упражнение 9.6.6. Найти контекстно-свободную грамматику для языка , где L1

порождается грамматикой

а язык L2

порождается грамматикой

Упражнение 9.6.7. Является ли контекстно-свободным язык

Упражнение 9.6.8. Является ли контекстно-свободным язык

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

Существует ли над алфавитом {a,b} такой линейный язык L, что язык

не является контекстно-свободным?



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