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

Теорема 9.6.1. Если L₁ - контекстно-свободный язык и L₂ - автоматный язык, то язык является контекстно-свободным.

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

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

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

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

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

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

Здесь S₁₁, S₁₂, S₂₁ и S₂₂ соответствуют символам , , и из доказательства теоремы 9.6.1.

Теорема 9.6.3*. Если L₁ - линейный язык и L₂ - автоматный язык, то язык является линейным.

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

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

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

Эту грамматику можно упростить, заменив S₁₁ и S₃₃ на один символ.

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

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

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

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

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

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

Упражнение 9.6.9. Существует ли над алфавитом {a,b} такой линейный язык L, что язык не является контекстно-свободным?

9.7*. Теорема Парика

Замечание 9.1.7. В этом разделе предполагается, что зафиксирован некоторый линейный порядок на алфавите . Пусть .

Определение 9.7.2. Через будем обозначать функцию из в , определенную следующим образом: . Аналогично, каждому языку ставится в соответствие множество , определенное следующим образом:

Пример 9.7.3. Пусть и L = {a₁,a₁a₂a₂,a₂a₂a₁}. Тогда .

Определение 9.7.4. Пусть и . Тогда через обозначается множество

При этом множество B называется системой предпериодов множества L(B,P). Множество P называется системой периодов множества L(B,P).

Определение 9.7.5. Множество называется линейным (linear), если A = L(B,P) для некоторых конечных множеств B и P.

Определение 9.7.6. Множество называется полулинейным (semilinear), если оно является объединением конечного числа линейных множеств.

Теорема 9.7.7 (Теорема Парика). Если язык является контекстно-свободным, то множество является полулинейным.

Доказательство можно найти в [Гин, с. 207-211].

Пример 9.7.8. Пусть . Рассмотрим язык . Можно проверить, что множество не является полулинейным. Следовательно, язык L не является контекстно-свободным.

Теорема 9.7.9. Если множество является полулинейным, то существует такой автоматный язык L, что .

Доказательство. Докажем это для произвольного линейного множества A = L(B,P) (на полулинейные множества утверждение распространяется по теореме 3.1.1). Рассмотрим конечный автомат , где Q = {1,2}, I = {1}, F = {2} и

Очевидно, что .

Замечание 9.7.10. Теорема 9.3.1 является следствием теорем 9.7.7 и 9.7.9.

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

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

Для наглядности стек обычно изображают вертикально, так, что доступный элемент данных (вершина) находится наверху. Но при формальном определении конфигурации (мгновенного состояния) МП-автомата удобно считать все содержимое стека конечной последовательностью символов, то есть словом (в алфавите, в котором перечислены все возможные данные, "умещающиеся" в одной ячейке стека). Прежде чем определить конфигурацию, придется принять произвольное соглашение о том, в каком порядке записывать содержимое стека в этом слове. В этой книге считается, что вершина стека находится в начале слова (то есть слева). В разделе 10.1 даются необходимые определения. В разделе 10.2 доказывается, что МП-автоматы распознают в точности контекстно-свободные языки.