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

UptoLike

ВУЗ: 

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

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

Рубрика: 

86
информации. Именно, состояние записывается как пара элементов, причём один
осуществляет управление, а другой запоминает символ. Подчеркнём, что этот
приём используется только концептуально. Никакой модификации основной
модели машины Тьюринга не подразумевается. Речь идёт только о удобных
обозначе-ниях состояний для “программиста” машины Тьюринга.
Пример 6.2. Пусть T =(Q, {0, 1},{0, 1, B}, δ, [q
0
, B], F), где Q ={[q
0
,0],
[q
0
,1], [q
0
, B], [q
1
,0], [q
1
,1], [q
1
, B]}, F ={[q
1
, B]}. Здесь Q записано как пара
из {q
0
, q
1
} × {0, 1, B}.
Запрограммируем распознавание языка, состоящего из цепочек, в которых
первый символ повторно не встречается в той же самой цепочке.
Отметим, что такой язык является регулярным.
Построим функцию δ следующим образом:
1. а) δ([q
0
, B], 0) = ([q
1
, 0], 0, R);
б) δ([q
0
, B], 1) = ([q
1
, 1], 1, R).
Машина запоминает сканируемый символ во второй компоненте обозначе-
ния состояния и сдвигается вправо. Первой компонентой становится q
1
.
2. а) δ([q
1
, 0], 1) = ([q
1
, 0], 1, R);
б) δ([q
1
, 1], 0) = ([q
1
, 1], 0, R).
Если машина помнит 0 и видит 1 или, наоборот, помнит 1 и видит 0, то она
продолжает движение вправо.
3. а) δ([q
1
, 0], B) = ([q
1
, B], 0, L);
б) δ([q
1
, 1], B) = ([q
1
, B], 0, L).
Машина входит в конечное состояние [q
1
, B], принимая вход, если только
она встречает символ пробела раньше, чем достигает второй копии самого
левого символа.
Если же машина в состоянии [q
1
,0] или [q
1
,1] видит на входе 0 или 1
соответственно, что свидетельствует о повторном вхождении запомненного
символа, то, поскольку в этих двух случаях функция δ не определена, машина
останавливается, не принимая, ибо [q
1
,0],[q
1
,1]∉F.
В общем случае можно допустить произвольное фиксированное число
компонент, причём все, кроме одной, предназначены для запоминания
контекстной информации.
6.2.2. Многодорожечные ленты.
Мы можем подразумевать, что лента
машины Тьюринга разделена на k дорожек для любого конечного k. Приём
состоит в том, что символы на ленте рассматриваются как наборы из k
элементов, по одному на каждой дорожке.
Пример 6.3. Представим, что лента, показанная на рис. 6.2, является лентой
машины Тьюринга для k = 3 в промежуточный момент работы, которая
принимает двоичный код целых чисел, значения которых больше 2. Этот код
записан на верхней дорожке и ограничен слева и справа символами ¢ и $.
Задача машины — определить, является ли закодированное число простым.
Мы не будем строить фактическую программу этой машины, а только обсудим
способ кодирования информации на 3-дорожечной ленте и дадим словесное
описание её работы.

Страницы