Мартыненко Б.К. Языки и трансляции

Подождите немного. Документ загружается.

110

Снова мы предполагаем без потери общности рассуждений, что для каждого

q ∈F и a ∈Σ значение δ(q, a) не определено.

Формально пусть G =(V

, Σ, P, A

), где V

= {[X, Y] | X ∈Σ∪{ε}, Y ∈Γ} ∪

Q ∪ { A

, A

}, а

P = {(1) A

→ q

(2) A

→ [a, a]A

для каждого a ∈Σ,

(3) A

→ A

(4) A

→ [ε, B]A

(5) A

→ε,

(6) q[a, C] → [a, D] p для каждых a ∈Σ∪{ε}, q ∈Q, C ∈Γ, таких, что

δ( q, C) = ( p, D, R),

(7) [b, E]q[a, C] → p[b, E][a, D] для всех C, D, E ∈Γ; a, b ∈Σ∪{ε}, q ∈Q,

таких, что δ(q, C) = ( p, D, L),

(8) [a, C]q → qaq, q[a, C] → qaq, q →ε для каждого a ∈Σ∪{ε}, C ∈Γ и

q ∈F}.

Используя правила 1 и 2, получаем вывод вида

, a

] [a

, a

] ... [a

, a

, где a

∈Σ, i = 1, 2,..., k.

Предположим, что Tm T принимает цепочку a

... a

, используя не более, чем

m ячеек справа от своего ввода. Тогда, используя правило 3, затем m раз прави-

ло 4 и, наконец, правило 5, продолжим предыдущий вывод. Получим

, a

] [a

, a

] ... [a

, a

] [ε, B]

Заметим, что с этого момента и впредь только правила 6 и 7 могут использо-

ваться до тех пор, пока не порождается принимающее состояние. При этом пер-

вые компоненты в обозначениях нетерминалов никогда не изменяются, а вторые

моделируют записи, производимые Tm T на ее ленте.

Индукцией по числу l движений машины T можно показать, что если

, a

...a

, 1)

(q, X

... X

, r), то

, a

][a

, a

]...[a

, a

][ε,B]

, X

][a

, X

]...[a

r – 1

, X

r – 1

]q[a

, X

]...[a

k + m

, X

k + m

где a

, a

, ... , a

∈Σ; a

k + 1

= a

k + 2

= ... = a

k + m

= ε; X

, X

, ..., X

k + m

∈Γ; X

s + 1

= X

s + 2

= ... =

k + m

= B.

База. Пусть l = 0. Утверждение выполняется очевидным образом.

Индукционная гипотеза. Предположим, что утверждение выполняется

для всех l ≤ n (n ≥ 0).

Индукционный переход. Пусть Tm T выполняет следующие n +1 дви-

жений:

, a

...a

, 1)

, X

... X

, j

)

, Y

...Y

, j

Тогда по индукционной гипотезе существует вывод вида

, a

][a

, a

]...[a

, a

][ε, B]

, X

][a

, X

]... q

, X

]...[a

k + m

, X

k + m

111

Судя по последнему движению, должно быть δ(q

, X

) = ( q

, Y

, D) и D = L, если

= j

–1 или D = R, если j

= j

+ 1. Соответственно при D = R существует правило

грамматики вида 6: q

, X

] → [a

, Y

; при D = L существует правило

грамматики вида 7: [a

–1

, X

–1

, X

] → q

–1

, X

–1

][a

, Y

Таким образом, еще один шаг вывода дает

, X

][a

, X

]...q

, X

]...[a

k + m

, X

k + m

]

, Y

][a

, Y

]...q

, Y

]...[a

k + m

, Y

k + m

где X

= Y

для всех i ≠ j

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

Далее, если q ∈F, то по правилам грамматики вида 8 можно получить вывод

, X

][a

, X

]... q [a

, X

]...[a

k + m

, X

k + m

]

...a

Итак, доказано, что если a

...a

принимается Tm T, то a

...a

∈L(G).

Чтобы завершить доказательство теоремы, остается показать, что если A

w, то цепочка w принимается Tm T. Прежде всего отметим, что любой вывод и,

в частности, вывод A

w может начинаться только по правилам 1– 5, дающим

результат вида

, a

][a

, a

]...[a

, a

][ε, B]

Далее могут применяться правила 6 и 7, дающие в конце концов результат вида

, X

][a

, X

]...q[a

, X

]...[a

k + m

, X

k + m

где q ∈F, после чего правила 8 дадут w = a

...a

Собственно, надо показать, что движения Tm T моделируются на участке

вывода

, a

][a

, a

]...[a

, a

][ε, B]

, Y

][a

, Y

]...q[a

, Y

]...[a

k+ m

, Y

k + m

где q ∈F. Другими словами, если такой вывод имеет место, то существуют

движения Tm T вида (q

, a

...a

, 1)

(q, Y

...Y

k + m

, j). Докажем это утвержде-

ние индукцией по l — длине вывода.

База. Пусть l = 0. Утверждение выполняется очевидным образом.

Индукционная гипотеза. Предположим, что утверждение выполняется

для всех l ≤ n (n ≥ 0).

Индукционный

переход. Пусть имеется вывод длиной l = n + 1. В общем

случае имеем

, a

][a

, a

]...[a

, a

][ε, B]

, X

][a

, X

]...q

, X

]...[a

k + m

, X

k + m

]

, Y

][a

, Y

]...q[a

, Y

]...[a

k + m

, Y

k + m

где q ∈F. Согласно индукционной гипотезе существует переход

, a

...a

, 1)

, X

...X

k + m

, j

Ясно, что последний шаг вывода мог быть выполнен только посредством

правила вида 6 или 7. Если применялось правило вида 6, то j = j

+1; если

112

использовалось правило вида 7, то j = j

–1. Эти правила существуют благодаря

тому, что δ(q

, X

) = (q, Y

, D), где D = R, если j = j

+ 1, или D = L, если j = j

– 1.

При этом X

= Y

для всех i ≠ j

. Благодаря этим значениям функции δ машина T

совершает еще одно движение, переводящее ее в принимающую конфигурацию:

, a

...a

, 1)

, X

...X

k + m

, j

)

(q, Y

...Y

k + m

, j),

где q ∈F. Другими словами, показано, что w = a

...a

принимается Tm T.

Итак, если w ∈L(G), то цепочка w принимается машиной T. Теорема доказа-

на полностью.

113

Глава 8

ЛИНЕЙНО ОГРАНИЧЕННЫЕ АВТОМАТЫ

И КОНТЕКСТНО-ЗАВИСИМЫЕ ЯЗЫКИ

§ 8.1. Линейно ограниченные автоматы

Линейно ограниченный автомат (lba) есть недетерминированная однолен-

точная машина Тьюринга, которая никогда не покидает те ячейки, на которых

размещен ее ввод. Формально он определяется следующим образом.

Определение 8.1. Линейно ограниченным автоматом называется формаль-

ная система M =(Q, Σ, Γ, δ, q

, F), в которой Q — множество состояний; q

∈

— начальное состояние; F ⊆ Q — множество конечных состояний; Γ— алфа-

вит допустимых символов ленты; Σ⊆Γ — алфавит входных символов, кото-

рый содержит два особых символа: ¢ и

$ — левый и правый маркеры, находя-

щиеся с самого начала на концах входной цепочки для того, чтобы предотвра-

щать выход головки ленты за пределы участка, на котором размещается входная

цепочка (считается, что маркеры могут использоваться только в этой роли: на

место маркера нельзя записать какой-нибудь другой символ ленты, и никакой

символ ленты не может быть заменен каким-нибудь маркером); δ — отображе-

ние типа Q ×Γ→2

Q ×Γ×{L, R}

Движения линейно ограниченного автомата описываются в терминах

конфигураций. Конфигурация lba M обозначается как (q, A

…A

, i), где q ∈Q;

, A

,…,A

∈Γ; i — целое, причем 1≤ i ≤ n . Согласно определению A

=¢,

= $.

Если ( p, A, L) ∈δ(q, A

) и i > 1, то

(q, A

…A

, i)

( p, A

…A

i – 1

i + 1

…A

, i –1).

Если ( p, A, R) ∈δ(q, A

) и i < n, то

(q, A

…A

, i)

( p, A

…A

i – 1

i + 1

…A

, i +1).

Другими словами, lba M печатает символ A на месте A

, изменяет свое состояние

на p и продвигает свою головку влево или вправо, не выходя из области, в

которой символы находились изначально.

Отношения на множестве конфигураций

, ,

или

определяются

обычным для недетерминированных машин Тьюринга образом.

Определение 8.2. Языком, принимаемым линейно ограниченным автоматом

M, называется множество

{w | w ∈(Σ \ {¢, $})

, (q

, ¢w$, 1)

(q, ¢α$, i), q ∈F, α∈Γ

, 1 ≤ i ≤ n, n = |w| +2}.

Определение 8.3. Линейно ограниченный автомат M является детермини-

рованным, если #δ(q, A) ≤ 1 для любых q ∈Q, A ∈Γ.

Неизвестно, является ли класс множеств, распознаваемых детерминирован-

ными линейно ограниченными автоматами, строгим подклассом множеств, рас-

познаваемых недетерминированными lba, или они совпадают. Конечно, спра-

ведливо, что любое множество, принимаемое недетерминированным линейно

ограниченным автоматом, принимается некоторой детерминированной маши-

ной Тьюринга. Однако длина ленты, требуемая этой Tm, может быть экспонен-

циальной, а не линейной, функцией от длины входной цепочки.

114

§ 8.2. Связь линейно ограниченных автоматов

с контекстно-зависимыми языками

Наш интерес к недетерминированным линейно ограниченным автоматам

проистекает из того факта, что класс множеств, принимаемых ими, является в

точности классом контекстно-зависимых языков.

Теорема 8.1. Если L — контекстно-зависимый язык, то язык L принимает-

ся некоторым линейно ограниченным автоматом.

Доказательство. Пусть G =(V

, V

, P, S) — контекстно-зависимая

грамматика. Мы построим lba M, такой, что язык, принимаемый lba M, есть

L(G). Мы не будем вдаваться в детальное построение автомата M, поскольку

оно очень сложно, а просто опишем, как он работает.

Входная лента будет иметь две дорожки. Дорожка 1 будет содержать вход-

ную строку x (x ≠ε) с концевыми маркерами. Дорожка 2 будет использоваться

для работы.

На первом шаге lba M помещает символ S в крайнюю левую ячейку дорожки

2. Затем автомат входит в порождающую подпрограмму, которая выполняет

следующие шаги:

1. Подпрограмма выбирает последовательные подстроки символов α на

дорожке 2, такие, что α→β∈P.

2. Подстроки α заменяются на β, сдвигая вправо, если необходимо, символы,

расположенные справа от α. Если эта операция заставляет символ быть вытолк-

нутым за правый маркер, автомат останавливается. Как известно, промежуточ-

ные сентенциальные формы в контекстно-зависимой грамматике не длиннее,

чем выводимая терминальная цепочка. Так что, если на очередном шаге полу-

чена сентенциальная форма длиннее x, то продолжать процесс не имеет смысла,

потому что все последующие сентенциальные формы будут разве лишь длиннее.

3. Подпрограмма недетерминированно выбирает, возвращаться ли к шагу 1,

либо идти на выход.

4. При выходе из подпрограммы дорожка 1 все еще будет содержать строку x,

в то время как дорожка 2 будет содержать некоторую строку γ, такую, что S

γ.

Автомат M сравнивает посимвольно цепочки x и γ. Если окажется, что x ≠γ, то

автомат останавливается, не принимая; если же окажется, что x = γ, то он оста-

навливается, принимая входную цепочку.

Ясно, что если x ∈L(G), то найдется такая последовательность движений lba

M, которая сгенерирует цепочку x на дорожке 2, и тогда автомат остановится,

принимая. Аналогично, если lba M принимает цепочку x, то должна существо-

вать последовательность движений, генерирующих цепочку x на дорожке 2.

Только при таком условии lba M принимает цепочку x. Но, по построению, про-

цесс генерации x воспроизводит вывод этой цепочки из S. Следовательно, S

Теорема доказана.

Теорема 8.2. Если язык L принимается линейно ограниченным автоматом,

то L — контекстно-зависимый язык.

Доказательство. Построение контекстно-зависимой грамматики, которая

моделирует линейно ограниченный автомат, подобно построению, описанному

в теореме 7.4, в которой грамматика типа 0 строилась, чтобы моделировать дви-

жения машины Тьюринга. Нетерминалы контекстно-зависимой грамматики

должны указывать не только первоначальное содержание некоторой ячейки

ленты lba, но также и то, является ли эта ячейка смежной с концевым маркером

115

слева или справа. Такие ячейки в обозначении нетерминалов мы будем снаб-

жать маркерами ¢ и $, обозначающими, что ячейка граничит соответственно с

левым, правым или обоими концевыми маркерами. В обозначении нетерминала

состояние lba должно также комбинироваться с символом, находящимся под

головкой ленты. Контекстно-зависимая грамматика не может иметь отдельных

символов для концевых маркеров и состояния линейно ограниченного автомата,

потому что эти символы должны были бы заменяться на пустые цепочки, когда

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

Формально пусть M = (Q, Σ, Γ, δ, q

, F) — недетерминированный lba, где

¢,$ ∉Σ и L — язык, принимаемый lba M, причем ε∉L.

Положим G =(V

, V

, P, A

), где

={A

, A

} ∪ {[q, ¢, X, a, $], [¢, q, X, a,$], [¢, X, a, q,$], [q, X, a], [q, X, a,$],

[X, a, q, $], [¢, X, a], [X, a], [X, a, $]|a ∈Σ\ {¢, $}, X ∈Γ\ {¢, $}, q ∈Q};

= Σ; а множество P включает следующие правила:

(1) A

→ [q

, ¢, a, a, $] — моделируют начальные конфигурации вида (q

, ¢a$, 1);

(2.1)

[q, ¢, X, a, $] → [¢, p,

X, a, $], если ( p, ¢, R) ∈δ(q, ¢);

(2.2)

[¢, q, X, a, $] → [p, ¢, Y, a, $], если (p, Y, L) ∈δ(q, X );

(2.3)

[¢, q, X, a, $] → [¢, Y, a, p, $], если ( p, Y, R) ∈δ(q, X );

(2.4)

[¢, X, a, q, $] → [¢, p, X, a, $], если ( p, $, L) ∈δ(q, $);

Моделируют движе-

ния на односимволь-

ной цепочке при

q ∈Q \ F.

(3.1) [q, ¢, X, a, $] → a;

(3.2) [¢, q, X, a, $] → a;

(3.3) [¢, X, a, q, $] → a;

Восстанавливают входную односимвольную цепочку при

q ∈F.

(4.1) A

→[q

, ¢, a, a]A

;

(4.2) A

→[a, a]A

;

(4.3) A

→[a, a, $];

Моделируют начальные конфигурации вида (q

, ¢w$, 1), где

|w| >1.

(5.1) [q, ¢, X, a] → [ ¢, p, X, a], если ( p, ¢, R) ∈δ(q,¢);

(5.2) [¢, q, X, a] → [p, ¢, Y, a], если (p, Y, L) ∈δ(q, X );

(5.3) [¢, q, X, a] [Z, b]→ [¢, Y, a] [p, Z, b], если ( p, Y, R) ∈δ(q, X );

Моделируют

движения на

левом конце

цепочки при

q ∈Q \ F.

(6.1) [q, X, a] [Z, b] → [Y, a][ p, Z, b], если ( p, Y, R) ∈δ(q, X );

(6.2) [Z, b] [q, X,

a] → [p, Z, b] [Y, a], если ( p, Y, L) ∈δ(q, X );

(6.3) [q, X,

a] [Z, b, $]→ [Y, a] [p, Z, b, $], если ( p, Y, R) ∈δ(q, X );

Моделируют

движения в сере-

дине цепочки при

q ∈Q \ F.

(7.1) [q, X, a, $] → [ Y, a, p, $], если ( p, Y, R) ∈δ(q, X );

(7.2) [X, a, q, $] → [p, X, a, $], если ( p, $, L) ∈δ(q, $);

(7.3) [Z

, b] [q, X, a, $] → [p, Z, b] [Y, a, $], если ( p, Y, L) ∈δ(q, X );

Моделируют

движения на пра-

вом конце цепоч-

ки при q ∈Q \ F.

(8.1) [q, ¢, X, a] → a;

(8.2) [¢, q, X, a] → a;

Восстановление входного символа при переходе в состояние q ∈F

на левом конце цепочки.

(8.3) [q, X, a] → a;

Восстановление входного символа при переходе в состояние q ∈F в

середине цепочки.

(8.4) [q, X, a, $] → a;

(8.5) [X, a, q, $] → a;

Восстановление входного символа при переходе в состояние q ∈F

на правом конце цепочки.

(9.1) a[X, b] → ab;

(9.2) a[X,

b, $] → ab;

Восстановление входной цепочки слева направо.

(9.3) [X, a]b → ab;

(9.4) [¢, X, a]b → ab;

Восстановление входной цепочки справа налево.

Здесь p ∈Q; X,Y,Z ∈Γ\ {¢, $}; a,b ∈Σ\ {¢, $}.

116

Очевидно, что построенная нами грамматика G — контекстно-зависима.

Индукцией по числу движений lba M нетрудно доказать, что если непустая

цепочка принимается линейно ограниченным автоматом M, то она выводима в

контекстно-зависимой грамматике G. И наоборот, индукцией по длине вывода

можно доказать, что если цепочка выводима в контекстно-зависимой граммати-

ке G, то она принимается линейно ограниченным автоматом M.

§ 8.3. Контекстно-зависимые языки —

подкласс рекурсивных множеств

В гл. 2 было показано, что каждый контекстно-зависимый язык рекурсивен.

Теперь мы покажем, что обратное утверждение неверно.

Теорема 8.3. Существуют рекурсивные множества, которые не являются

контекстно-зависимыми.

Доказательство.

Мы можем перечислять все строки из множества {0, 1}

как в § 7.3. Пусть x

— i-я строка. Аналогично мы можем перечислять все грам-

матики типа 0, у которых алфавит терминалов состоит из тех же символов 0 и 1.

Поскольку имена нетерминалов не существенны, а каждая грамматика имеет

конечное их число, можно предположить, что имеется не более чем счетное

число нетерминалов, которые можно представить в бинарном коде как 01, 011,

0111, 01111, и т.д. Предполагается, что 01 — всегда начальный нетерминал.

Кроме того, терминал 0 будем представлять как 00, а терминал 1 — при помощи

кода 001. Символ → представим кодом 0011, а запятую, отделяющую одно пра-

вило грамматики от другого, — кодом 00111. Таким образом, символы алфави-

тов, используемые в правилах грамматики, представляются двоичными кодами:

00 — терминал 0, 001 — терминал 1 и 01

где i = 1, 2, ... — нетерминалы. Состав

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

вилам грамматики, в которых эти нетерминалы используются.

Заметим, что не все цепочки из 0 и 1 представляют грамматики, тем более

контекстно-зависимые грамматики. Однако по заданной цепочке можно легко

судить, является ли она csg. Поскольку имеется бесконечно много csg, мы мо-

жем их нумеровать некоторым разумным образом: G

, G

, ... .

Доказательство теоремы теперь тривиально.

Определим язык L ={x

| x

∉L(G

) }. Язык L — рекурсивен. Действительно, по

любой данной цепочке x

легко определить i, а затем можно сгенерировать G

Согласно теореме 2.2 имеется алгоритм, который определяет, находится ли це-

почка x

в языке L(G

), поскольку G

— контекстно-зависимая грамматика. Сле-

довательно, имеем алгоритм определения для любой цепочки x, находится ли она

в языке L.

Теперь покажем, что язык L не порождается никакой контекстно-зависимой

грамматикой. Предположим противное: язык L порождается csg G

. Пусть x

∈L.

Поскольку L = L(G

), то x

∈L(G

). Но по самому определению языка x

∉L(G

Получаем противоречие, которое отвергает наше предположение о том, что су-

ществует csg G

, порождающая язык L. Поскольку приведенное рассуждение

справедливо для каждой csg G

в перечислении и поскольку перечисление со-

держит каждую csg, мы заключаем, что язык L не является контекстно-

зависимым языком. Следовательно, L — рекурсивное множество, которое не

является контекстно-зависимым. Что и требовалось доказать.

117

Глава 9

ОПЕРАЦИИ НАД ЯЗЫКАМИ

§ 9.1. Замкнутость

относительно элементарных операций

В этой главе мы применяем операции объединения, конкатенации, обра-

щения, замыкания и т.д. к языкам разных типов. Интересно выяснить, какие

операции какие классы языков сохраняют, т.е. отображают языки некоторого

класса в тот же самый класс. Есть ряд причин интересоваться этим вопросом.

Во-первых, знание, сохраняет операция или нет данный класс языков, помогает

характеризовать этот класс. Во-вторых, часто бывает легче узнать, что сложный

язык относится к некоторому классу, при помощи того факта, что эта принад-

лежность является результатом различных операций над другими языками в

данном классе, чем путем непосредственного конструирования грамматики для

этого языка. В-третьих, знание, полученное из изучения операций над языками,

может быть использовано при доказательстве теорем, как это было сделано в гл.

7, где мы показали, что класс рекурсивно перечислимых множеств строго со-

держит рекурсивные множества, используя при доказательстве тот факт, что ре-

курсивные множества замкнуты относительно дополнения.

Начнем с рассмотрения операций объединения, конкатенации, замыкания

Клини и обращения. Используем следующую лемму о “нормальной форме” для

контекстно-зависимых языков и языков типа 0:

Лемма 9.1. Каждый контекстно-зависимый язык порождается контекст-

но-зависимой грамматикой, в которой все правила имеют форму либо α→β, где

α и β — цепочки, состоящие из одних только нетерминалов, либо A → b, где A —

нетерминал, а b — терминал. Каждый язык типа 0 порождается граммати-

кой типа 0, правила которой имеют указанную форму.

Доказательство. Пусть G =(V

, V

, P, S) — контекстно-зависимая грамма-

тика. Каждому a ∈V

сопоставим новый символ X

. Рассмотрим грамматику

, V

, P

, S), где

= V

∪ {X

| a ∈V

}. Множество P

включает все пра-

вила вида X

→ a. Если α→β∈P, то α

→β

∈P

, где цепочки α

и β

получа-

ются из цепочек α и β путем замещения в них каждого терминала a символом

. Доказательство тривиально и мы оставляется его читателю в качестве уп-

ражнения. Подобное же доказательство применимо к грамматикам типа 0.

Теорема 9.1 Классы регулярных, контекстно-свободных, контекстно-зави-

симых

и рекурсивно перечислимых множеств замкнуты относительно объеди-

нения, конкатенации, замыкания и обращения.

Доказательство. Для класса регулярных множеств доказательство было да-

но в гл. 3.

118

Рассмотрим две грамматики: G

(1)

, P

, S

) и G

(2)

, P

, S

причем обе либо контекстно-свободные, либо контекстно-зависимые, либо типа

0. Без потери общности можно предполагать, что

(1)

∩

(2)

= ∅.

Кроме того, согласно лемме 9.1 и теореме 4.5 можно считать, что правила

грамматик G

и G

имеют форму α→β и A → a, где α и β — цепочки, состоя-

щие из одних только нетерминалов, A — одиночный нетерминал, а a — одиноч-

ный терминальный символ. Кроме того, если G

и G

— контекстно-свободные

грамматики, то β = ε подразумевает, что α есть S

или S

и что α никогда не по-

является в правой части никакого правила.

Объединение. Пусть G

= (

(1)

∪

(2)

∪ {S

(1)

∪

(2)

, P

, S

), где S

∉

(1)

∪

(2)

, а множество P

содержит правила S

→ S

и все правила из

множеств P

и P

за исключением S

→ε и

→ε, если G

и G

— контекстно-

зависимы. В случае, когда

и G

— контекстно-зависимы и S

→ε∈P

или

→ε∈P

, добавим правило S

→ε к множеству правил P

. Теперь грамматика

— того же типа, что и грамматики G

, G

и L(G

)=L(G

) ∪ L(G

Конкатенация. Пусть G

(1)

∪

(2)

∪ {S

(1)

∪

(2)

, P

, S

), где S

∉

(1)

∪

(2)

, а множество P

содержит правило S

→ S

и все правила из мно-

жеств P

и P

, за исключением правил S

→ε и

→ε, если G

и G

— контекст-

но-зависимы. В случае, когда G

и G

— контекстно-зависимы и S

→ε∈P

, до-

бавим правило S

→ S

к множеству правил P

; если S

→ε∈P

то

добавим пра-

вило S

→ S

к множеству P

. Если S

→ε∈P

и S

→ε∈P

, то

добавим правило

→ε к множеству P

. Теперь грамматика G

— того же типа, что и грамматики

, G

и L(G

)=L(G

)L(G

Заметим, что поскольку

(1)

∩

(2)

= ∅ и все правила из множеств P

, P

имеют нетерминалы исключительно слева, невозможно, чтобы строка, образо-

ванная правым концом сентенциальной формы грамматики

, за которой сле-

дует левый конец сентенциальной формы грамматики

, могла быть левой сто-

роной правила в множестве

. Это означает, что левая часть любого правила це-

ликом состоит из нетерминалов только одной из двух грамматик (см. рис. 9.1).

Соответственно и все правило относится к одной

исходной грамматике. Доказа-

тельство того, что L(G

) = L(G

)L(G

) просто.

Рис. 9.1.

119

Замыкание. Пусть G

=(V

(1)

, P

, S

), где V

(1)

∪ {S

}, а P

∪ {S

→ S

, S

→ε}, если G

— контекстно-свободная грамматика, иначе

= P

∪ {S

→ε, S

→ S

, S

→ S

} ∪ {a

→ aS

, a

→ aS

| a ∈

(1)

Однако в случае, когда G

— контекстно-зависимая грамматика, правило S

→ε,

если оно имеется, отбрасывается. Грамматика G

является грамматикой того же

типа, что и G

, и L(G

)=(L(G

))

Теперь рассмотрим операции пересечения и дополнения.

Теорема 9.2. Класс контекстно-свободных языков не замкнут относительно

пересечения

Доказательство. Языки L

={a

|n ≥ 1, i ≥ 0} и L

={a

| n ≥ 1,

i ≥ 0} являются контекстно-свободными, поскольку они порождаются граммати-

ками

= ({S, T}, {a, b, c}, {S → Sc, S → T, T → aTb, T → ab}, S) и G

= ({S, T},

{a, b, c}, {S → aS, S → T, T → bTc, T→ bc}, S) соответственно. Теперь язык L

= L

∩ L

= {a

| n ≥ 1}, который не контекстно-свободен по тривиальному

следствию из теоремы 4.7. Действительно, все цепочки L не соответствуют тре-

буемому условию: в L должна быть цепочка uvwxy, такая, что все цепочки вида

y при любом n тоже принадлежали бы языку L. Мы могли бы считать

u = y = ε, но ядро w должно быть в первой степени, а в цепочках из языка L оно

тоже в степени n.

Теорема 9.3. Класс контекстно-свободных языков не замкнут относительно

дополнения

Доказательство. Поскольку класс контекстно-свободных языков замкнут

относительно объединения, но не пересечения, то он не может быть замкнут от-

носительно дополнения, поскольку L

∩ L

LL∪ .

Теорема 9.4. Класс контекстно-свободных языков замкнут относительно

пересечения с регулярным множеством

Доказательство. Пусть L — контекстно-свободный язык, а R — регулярное

множество. Предположим, что

=(Q

, Σ, Γ, δ

, p

, Z

, F

) — недетерминиро-

ванный

магазинный автомат (npda), принимающий язык L, а A =(Q

, Σ, δ

, q

, F

)

— детерминированный конечный автомат (dfa), принимающий множество

Построим недетерминированный магазинный автомат (npda)

=(Q

× Q

, Σ, Γ,

δ, [p

, q

], Z

, F

× F

), который принимает L ∩ R. Функция δ определяется сле-

дующим образом. Для всех p ∈Q

, q∈Q

, a ∈Σ∪{ε} и Z ∈Γ функция δ([ p, q],

a, Z) содержит ([p’, δ

(q, a)], γ) всякий раз, как δ

(p, a, Z) содержит ( p’, γ). (На-

помним, что δ

(q, ε)=q для всех q ∈Q

.) Неформально npda P

хранит след со-

стояний npda P

и dfa A в своем конечном управлении.

I. Предположим, что x ∈L ∩ R. Пусть x = a

…a

, где a

∈Σ∪{ε}, 1 ≤ i ≤ n,

так что существуют состояния

, q

,…, q

∈Q

, p

,…, p

∈Q

и цепочки

,γ

,…,γ

∈Γ

, для которых имеют место δ

, a

i + 1

)=q

i + 1

и (p

, a

i + 1

…a

, γ

)