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

UptoLike

ВУЗ: 

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

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

Рубрика: 

120
Теорема 8.2. Если язык L принимается линейно ограниченным автоматом,
то L — контекстно-зависимый язык.
Доказательство. Построение контекстно-зависимой грамматики, которая
моделирует линейно ограниченный автомат, подобно построению, описанному
в теореме 7.4, в которой грамматика типа 0 строилась, чтобы моделировать
движения машины Тьюринга. Нетерминалы контекстно-зависимой грамматики
должны указывать не только первоначальное содержание некоторой ячейки
ленты lba, но также и то, является ли эта ячейка смежной с концевым маркером
слева или справа. Такие ячейки в обозначении нетерминалов мы будем
снабжать маркерами ¢ и $, обозначающими, что ячейка граничит соответ-
ственно с левым, правым или обоими концевыми маркерами. В обозначении
нетерминала состояние lba должно также комбинироваться с символом,
находящимся под головкой ленты. Контекстно-зависимая грамматика не может
иметь отдельных символов для концевых маркеров и состояния линейно
ограниченного автомата, потому что эти символы должны были бы заменяться
на пустые цепочки, когда строка превращается в терминальную, а ε-
порождения в csg запрещены.
Формально пусть M = (Q, Σ, Γ, δ, q
0
, F) — недетерминированный lba, где
¢, $ ∈Σ и L — язык, принимаемый lba M, причем ε∉L.
Положим G =(V
N
, V
T
, P, A
1
), где
V
N
={A
1
, A
2
} ∪ {[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};
V
T
= Σ. Mножество P включает следующие правила:
(1) A
1
→ [q
0
, ¢, a, a, $] — моделируют начальные конфигурации вида (q
0
, ¢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
1
→ [q
0
, ¢, a, a]A
2
;
(4.2) A
2
→ [a, a]A
2
;
(4.3) A
2
→ [a, a, $];
Моделируют начальные конфигурации вида (q
0
, ¢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 );
(6.4) [¢, Z, b] [q, X, a] → [¢, p, Z, b] [Y, a], если ( p, Y, L) ∈δ(q, X );
Моделируют дви-
жения в середине
цепочки при
q ∈ Q \ F.

Страницы