Теория алгоритмов и формальных языков. Мелихов А.Н - 31 стр.

UptoLike

ВУЗ: 

ТТИ ЮФУ | Таганрог

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

Рубрика: 

которая задает МТ, выполняющую сложение чисел в унарном коде.
2.3. Диаграммы Тьюринга
В предыдущем разделе мы рассмотрели пример синтеза машины
Тьюринга. Таблица этой МТ содержала шесть команд и описывала
простейшие операции по просмотру массива унарного кода и стирание двух
его элементов. При выполнении более сложных операций или использовании
более сложных
кодов число команд таблицы существенно возрастает, и
поэтому усложняется процесс синтеза. Для облегчения синтеза используют
композицию элементарных МТ. Набор элементарных МТ, как правило,
ограничен, и все они имеют фиксированную систему команд. Если каким-то
образом обозначить элементарные МТ и указать связи между ними, то
результат их композиции и будет представлять собой
диаграмму Тьюринга
(ДТ).
Пусть
},...,(
10 n
xxxX = - входной алфавит, r, l - сдвиг ленты
соответственно вправо и влево, s - стоп, х
0
или В - пустая буква (пробел), Х* -
множество слов над Х, А - слово в алфавите Х. Будем считать, что
двухбуквенный алфавит Х состоит из В и 1. Будем обозначать через
~
произвольную последовательность букв, несущественную в данном
контексте, а через ∼ - несущественную в данном контексте букву. Пусть ↑
указывает букву, которую в данном шаге просматривает головка.
Приведем теперь несколько примеров простых МТ:
а) МТ х
i
. Примененная к произвольной позиции, печатает в рабочей
ячейке букву х
i
. Очевидно, что таблица Тьюринга для такой МТ имеет вид:
100
qxxq
i
,
10
qxxq
in
;
б) МТ r. Примененная к произвольной позиции, сдвигает ленту на одну
ячейку вправо и останавливается;

Страницы