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

UptoLike

ВУЗ: 

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

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

Рубрика: 

114
вывод в грамматике G, начиная с символа S. Каждая сентенциальная форма в
выводе будет появляться по очереди между двумя последними ограничителями
#. Если некоторый выбор движений приводит к цепочке терминалов, то она
сравнивается с w. Если эти две цепочки равны, то Tm T принимает.
Формально, пусть в какой-то момент Tm T имеет на своей ленте цепочку
вида #w# A
1
A
2
... A
k
#. Машина T передвигает свою головку по цепочке
A
1
A
2
... A
k
, недетерминированно выбирая позицию i и константу r между 1 и
максимальной длиной левой части любого правила из множества P.
Затем Tm T исследует подцепочку A
i
A
i +1
... A
i + r –1
. Если она является левой
частью некоторого правила из множества P, то её можно заменить правой
частью этого же правила. Машина T может быть вынуждена сдвигать
A
i + r
A
i + r +1
... A
k
# вправо или влево, чтобы освободить место или заполнить
пространство, если длина правой части не равна r. При сдвиге вправо символ X
используется для временного заполнения освободившегося пространства.
Из этого простого моделирования выводов в грамматике G должно быть
ясно, что Tm T будет печатать на своей ленте строку вида #w # α#, где α∈V
*
,
точно тогда, когда S
α. Кроме того, если α = w, то Tm T принимает. Заметим,
что для реализации проверки этого равенства опять пригодится символ X.
Что и требовалось доказать.
Теорема 7.4. Если язык L распознается машиной Тьюринга, то язык L
порождается грамматикой типа 0.
Доказательство.
Пусть язык L принимается машиной Тьюринга T = (Q,
Σ, Γ, δ, q
0
, F).
Мы построим грамматику G, которая недетерминированно порождает две
копии представления некоторого слова из множества Σ
*
, а затем моделирует
действие Tm T на одной из этих копий. Если Tm T принимает слово, то
грамматика G превращает вторую копию в терминальную строку. Если Tm T не
принимает слово, вывод никогда не даёт в результате терминальную строку.
Снова мы предполагаем без потери общности рассуждений, что для каждого
q∈F и a∈Σ значение δ(q, a) не определено.
Формально пусть G =(V
N
, Σ, P, A
1
), где
V
N
= {[X, Y] | X∈Σ∪{ε}, Y∈Γ} ∪ Q ∪ { A
1
, A
2
, A
3
},
P = {(1) A
1
→ q
0
A
2
,
(2) A
2
→ [a, a]A
2
для каждого a∈Σ,
(3) A
2
→ A
3
,
(4) A
3
→ [ε, B]A
3
,
(5) A
3
→ε,
(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
1
q
0
[a
1
, a
1
] [a
2
, a
2
] ... [a
k
, a
k
]A
2
, где a
i
∈Σ, i = 1, 2,..., k.
*
G
⇒
*
G
⇒

Страницы