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

UptoLike

ВУЗ: 

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

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

Рубрика: 

84
Таким
образом, мы ввели отношение непосредственного следования одной
конфигурации за другой. Очевидным образом можно определить степень,
транзитивное и рефлексивно-транзитивное замыкания этого отношения. Будем
обозначать их традиционно через
,
и
соответственно. Если две
конфигурации связаны знаком
, то мы будем говорить, что вторая получает-
ся из первой за n движений. Соответственно значок
обозначает положи-
тельное число движений, а
— любое число движений, включая нуль.
Определение 6.3. Пусть T = (Q, Σ, Γ, δ, q
0
, F) — машина Тьюринга. Язык,
принимаемый машиной T, есть L = {w | w∈ Σ
*
и (q
0
, w, 1)
(q, α, i)
для некото-
рых q∈ F, α∈ Γ
*
и i >0}.
Мы
предполагаем, что данная Tm, распознающая язык L, останавливается,
т.е. не имеет никакого следующего движения, всякий раз, как входная цепочка
принимается. Но для цепочек, которые не принимаются, Tm может не
остановиться.
Пример 6.1. Построим Tm, распознающую cfl L ={0
n
1
n
| n ≥ 1}. Положим
T = (Q, Σ, Γ, δ, q
0
, F), где Q ={q
0
, q
1
, q
2
, q
3
, q
4
, q
5
}; Σ = {0, 1}; Γ = {0, 1, B, X, Y};
F ={q
5
}. Функцию δ определим следующим образом:
1. δ(q
0
, 0) = (q
1
, X, R).
В состоянии q
0
символ 0 заменяется на X и машина сдвигается вправо в
состояние q
1
в поисках 1.
2. а) δ(q
1
, 0) = (q
1
, 0, R);
б) δ(q
1
, Y)=(q
1
, Y, R);
в) δ(q
1
, 1) = (q
2
, Y, L).
Оставаясь
в состоянии q
1
,
машина продвигается вправо сквозь все нули (п. 2а) и
блок Y (п. 2б). Наткнувшись на 1, заменяет её на Y и переходит в состояние q
2
,
начав движение влево (п. 2в).
3. а) δ(q
2
, Y)=(q
2
, Y, L);
б) δ(q
2
, X)=(q
3
, X, R);
в) δ(q
2
, 0) = (q
4
, 0, L).
Оставаясь в состоянии q
2
, машина продвигается влево сквозь блок Y (п. 3а).
Если машина встречает X, все ещё оставаясь в состоянии q
2
, то больше нет
нулей, которые следовало бы заменять на X, и машина переходит в состояние
q
3
, начиная движение вправо, чтобы убедиться, что не осталось единиц (п. 3б).
Если же 0 встретился, машина переходит в состояние q
4
, чтобы продолжить
движение в поисках крайнего левого 0 (п. 3в).
4. а) δ(q
4
, 0) = (q
4
, 0, L)
б) δ(q
4
, X)=(q
0
, X, R).
Машина движется сквозь нули (п. 4а). Если встретился X, то машина про-
шла самый левый нуль. Она должна, сдвинувшись вправо, превратить этот 0 в
X (п. 4б). Происходит переход в состояние q
0
, и процесс, только что описанный
в п. 1–4, повторяется.
5. а) δ(q
3
, Y)=(q
3
, Y, R)
б) δ(q
3
, B)=(q
5
, Y, R).
*
__
T
__
T
+
__
n
T
__
n
T
*
__
T
__
T
+
*
__
T

Страницы