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

UptoLike

ВУЗ: 

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

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

Рубрика: 

89
13. δ([q
8
, B], [√, d ]) = ([q
8
, B], [√, d ], R) для d∈{a, b}.
Машина двигается вправо через отмеченные символы на правой половине
цепочки.
14. δ([q
8
, B], [B, B]) = ([q
9
, B], [√, B], L).
Если машина находит пробел [B, B], она останавливается и принимает
входную цепочку. Если машина находит неотмеченный символ, когда первая
компонента ее состояния — q
8
, она останавливается, не принимая входной
цепочки.
6.2.4. Сдвиг символов ленты.
Машина Тьюринга может освобождать
место на своей ленте, сдвигая все непустые символы на конечное число ячеек
вправо. Она может затем вернуться к освобожденным ячейкам и печатать
символы по своему выбору. Если пространство доступно, машина может
сдвигать блоки символов влево подобным же образом.
Пример 6.5. Построим часть машины Тьюринга T = (Q, Σ, Γ, δ, q
0
, F),
которая время от времени имеет необходимость сдвигать символы на две ячей-
ки вправо. Пусть Q содержит состояния вида [q, A
1
, A
2
] для q∈{q
1
, q
2
} и A
1
, A
2
∈Γ.
Пусть B — пробел, а X — специальный символ, не используемый машиной
нигде, кроме как в процессе сдвига. Мы предполагаем, что машина начинает
процесс сдвига в состоянии [q
1
, B, B]. Относящаяся к этому часть функции δ
определяется следующим образом:
1. δ([q
1
, B, B], A
1
) = ([q
1
, B, A
1
], X, R) для A
1
∈Γ \{B, X}.
Машина запоминает первый прочитанный символ в третьей компоненте её
состояния, печатает на его месте символ X и начинает движение вправо.
2. δ([q
1
, B, A
1
], A
2
) = ([q
1
, A
1
, A
2
], X, R) для A
1
, A
2
∈ Γ \ {B, X}.
Машина запоминает прочитанный символ в третьей компоненте ее
состояния, сдвигая перед этим третью компоненту на место второй, печатает на
его месте символ X и двигается вправо.
3. δ([q
1
, A
1
, A
2
], A
3
) = ([q
1
, A
2
, A
3
], A
1
, R) для A
1
, A
2
, A
3
∈ Γ \ {B, X}.
Машина запоминает прочитанный символ в третьей компоненте ее
состояния, сдвигая перед этим третью компоненту на место второй, печатает на
его месте символ A
1
из прежней второй компоненты состояния и двигается
вправо. Очевидно, что символ A
1
будет напечатан двумя ячейками правее той
позиции, в которой он находился прежде. Заметим, что вторая и третья
компоненты состояния играют роль буфера, через который проходят
задерживаемые символы. Поскольку буфер рассчитан на два элемента, он
обеспечивает задержку каждого символа на то время, пока машина проходит
две позиции на ленте.
4. δ([q
1
, A
1
, A
2
], B) = ([q
1
, A
2
, B], A
1
, R) для A
1
, A
2
, A
3
∈ Γ \ {B, X}.
Когда на ленте виден пробел, запомнённый во второй компоненте символ
помещается на ленту.
5. δ([q
1
, A
1
, B], B) = ([q
2
, B, B], A
1
, L) для A
1
∈ Γ \ {B, X}.
Последний запомненный символ из второй компоненты состояния
помещается на ленту, после чего начинается движение влево с целью выйти на
крайнюю правую свободную ячейку. Она помечена, как и все другие
освобожденные ячейки, символом X.

Страницы