Математическая теория формальных языков
Пересечение контекстно-свободного языка с автоматным языком
Теорема 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, что язык
не является контекстно-свободным?
