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

UptoLike

ВУЗ: 

СПбГУ | Санкт-Петербург

Составители: 

Рубрика: 

121
(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∈ Σ \ {¢, $}.
Очевидно, что построенная нами грамматика G — контекстно-зависима.
Индукцией по числу движений lba M нетрудно доказать, что если непустая
цепочка принимается линейно ограниченным автоматом M, то она выводима в
контекстно-зависимой грамматике G. И наоборот, индукцией по длине вывода
можно доказать, что если цепочка выводима в контекстно-зависимой
грамматике G, то она принимается линейно ограниченным автоматом M.
§ 8.3. Контекстно-зависимые языки —
подкласс рекурсивных множеств
В гл. 2 было показано, что каждый контекстно-зависимый язык рекурсивен.
Теперь мы покажем, что обратное утверждение неверно.
Теорема 8.3. Существуют рекурсивные множества, которые не являются
контекстно-зависимыми.
Доказательство.
Мы можем перечислять все строки из множества {0, 1}
*
,
как в § 7.3. Пусть x
i
— i-я строка. Аналогично мы можем перечислять все
грамматики типа 0, у которых алфавит терминалов состоит из тех же символов
0 и 1. Поскольку имена нетерминалов не существенны, а каждая грамматика
имеет конечное их число, можно предположить, что имеется не более чем
счётное число нетерминалов, которые можно представить в бинарном коде как
01, 011, 0111, 01111, и т.д. Предполагается, что 01 — всегда начальный
нетерминал. Кроме того, терминал 0 будем представлять как 00, а терминал 1
— при помощи кода 001. Символ → представим кодом 0011, а запятую,
отделяющую одно правило грамматики от другого, — кодом 00111. Таким
образом, символы алфавитов, используемые в правилах грамматики,
представляются двоичными кодами: 00 — терминал 0, 001 — терминал 1 и 01
i
,
где i = 1, 2, ... — нетерминалы. Состав нетерминального словаря конкретной

Страницы