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

UptoLike

ВУЗ: 

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

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

Рубрика: 

115
Предположим, что Tm T принимает цепочку a
1
a
2
... a
k
, используя не более,
чем m ячеек справа от своего ввода. Тогда, используя правило 3, затем m раз
правило 4 и, наконец, правило 5, продолжим предыдущий вывод. Получим
A
1
q
0
[a
1
, a
1
] [a
2
, a
2
] ... [a
k
, a
k
] [ε, B]
m
.
Заметим, что с этого момента и впредь только правила 6 и 7 могут
использоваться до тех пор, пока не порождается принимающее состояние. При
этом первые компоненты в обозначениях нетерминалов никогда не
изменяются, а вторые моделируют записи, производимые Tm T на её ленте.
Индукцией
по числу l движений машины T можно показать, что если
(q
0
, a
1
a
2
...a
k
, 1)
(q, X
1
X
2
... X
s
, r), то
q
0
[a
1
, a
1
][a
2
, a
2
]...[a
k
, a
k
][ε, B]
m
[a
1
, X
1
][a
2
, X
2
]...[a
r–1
, X
r–1
]q[a
r
, X
r
]...[a
k+ m
, X
k+ m
],
где a
1
, a
2
, ... , a
k
∈Σ; a
k+1
= a
k+2
= ... = a
k+ m
= ε;
X
1
, X
2
, ..., X
k+ m
∈Γ; X
s+1
= X
s+2
= ... = X
k+ m
= B.
База. Пусть l = 0. Утверждение выполняется очевидным образом.
Индукционная гипотеза. Предположим, что утверждение выполняется для
всех l ≤ n (n ≥ 0).
Индукционный переход. Пусть Tm T выполняет следующие n + 1 движений:
(q
0
, a
1
a
2
... a
k
, 1) (q
1
, X
1
X
2
... X
r
, j
1
) (q
2
, Y
1
Y
2
...Y
s
, j
2
).
Тогда по индукционной гипотезе существует вывод вида
q
0
[a
1
, a
1
][a
2
, a
2
]...[a
k
, a
k
][ε, B]
m
[a
1
, X
1
][a
2
, X
2
]... q
1
[a
j
1
, X
j
1
]...[a
k+ m
, X
k+ m
].
Судя по последнему движению, должно быть
δ(q
1
, X
j
1
) = (q
2
, Y
j
1
, D) и D = L, если j
2
= j
1
– 1 или D = R, если j
2
= j
1
+ 1.
Соответственно,
при D = R существует правило грамматики вида 6:
q
1
[a
j
1
, X
j
1
] → [a
j
1
, Y
j
1
]q
2
;
при D = L существует правило грамматики вида 7:
[a
j
1
–1
, X
j
1
–1
]q
1
[a
j
1
, Y
j
1
] → q
2
[a
j
1
–1
, X
j
1
–1
][ a
j
1
, Y
j
1
].
Таким образом, ещё один шаг вывода даёт
[a
1
, X
1
][a
2
, X
2
] ... q
1
[a
j
1
, X
j
1
] ... [a
k+ m
, X
k+ m
]
[a
1
, Y
1
][a
2
, Y
2
] ... q
2
[a
j
2
, Y
j
2
]...[a
k+ m
, Y
k+ m
],
где X
i
= Y
i
для всех i ≠ j
1
.
Итак, вспомогательное утверждение доказано.
Далее,
если q∈F, то по правилам грамматики вида 8 можно получить вывод
[a
1
, X
1
][a
2
, X
2
] ... q [a
j
, X
j
] ... [a
k+ m
, X
k+ m
] a
1
a
2
... a
k
.
Итак, доказано, что если a
1
a
2
... a
k
принимается Tm T, то a
1
a
2
... a
k
∈L(G).
Чтобы завершить доказательство теоремы, остаётся показать, что если
A
1
w, то цепочка w принимается Tm T.
*
__
T
_
_
T
*
G
⇒
*
G
⇒
G
⇒
G
⇒
*
G
⇒
*
G
⇒
__
n
T
*
G
⇒

Страницы