ВУЗ:
Составители:
простейшем случае в одну ячейку заносится один символ). Головка считает
данные из ячейки, которая находится прямо перед ней (такая ячейка
называется рабочей) и осуществляет запись на ленту промежуточных
результатов и сдвиг ленты вправо или влево (в простейшем случае - на одну
ячейку).
Процесс работы МТ состоит в следующем. Устройство управления
находится
в одном из состояний, головка обозревает рабочую ячейку и
считывает символ, записанный в ней. Устройство управления анализирует
этот символ и выдает команду, в результате выполнения которой может быть
изменено содержимое ячейки, а лента сдвинута вправо или влево.
Конкретные действия определяются ситуацией, в которой находится машина,
и командами перехода.
Пусть х
0
, х
1
, …, х
n
- символы входного алфавита Х, буквы которого
могут быть записаны на ленте. Символ х
0
отождествляется с нулевым
символом. Иногда он обозначается В и называется пробелом. Считается, что
входное слово записано в ячейках ленты сплошным массивом, а все
незанятые ячейки ленты заполнены пробелами.
Пусть
},...,,{
10 m
qqqQ = - алфавит внутренних состояний устройства
управления МТ. Состояние q
0
- начальное состояние. Предполагается, что в
исходном состоянии МТ находится в состоянии q
0
, а головка обозревает
самый левый символ входной цепочки.
Пусть
},,{ srlI = - множество инструкций управления движением ленты.
Символ l означает сдвиг ленты на одну ячейку влево, r - вправо, s -
отсутствие движения или остановка ленты. Заметим, что символы l и r можно
употреблять в противоположном значении, если считать, что вместо ленты
передвигается головка.
МТ условно можно представить так, как показано на рис. 2.1.
Страницы
- « первая
- ‹ предыдущая
- …
- 24
- 25
- 26
- 27
- 28
- …
- следующая ›
- последняя »
