2018-01-08
2087
Рассмотрим две основные операции: композиция и итерация МТ. Пусть М1 и М2 - машины Тьюринга с общим алфавитом. Композицией (или произведением) машин Тьюринга М1 и М2 (в этом порядке) называется машина Тьюринга М (обозначение М=М1·М2), работающая следующим образом: если на вход машины М подать входное слово Р, то оно сначала преобразуется машиной М1, а затем полученное выходное слово подаётся на вход машины М2, и выходное слово машины М2 считается результатом преобразования входного слова Р машиной М: М(Р)=М2(М1(Р)).
Если известны функциональные схемы (ФС) машин М1 и М2, то ФС композиции М=М1·М2 строится следующим образом:
1. СТОП-состояние машины М1 отождествляется с начальным состоянием машины М2;
2. СТОП-состояние машины М2 объявляется СТОП-состоянием композиции М=М1·М2;
3. Остальные состояния М2 переобозначаются.
Пусть даны три МТ с общим алфавитом - М1, М2 и М3 и некоторое условие С. МТ, описываемая формулой 
, называется разветвлением машины М1 на машины М2 и М3 по признаку С, если она работает следующим образом: входное слово Р подаётся на вход машины М1, результат обработки ею слова Р (М1(Р)) подаётся на вход машины М2, если условие С выполнено, и на вход М3 - в противном случае.
|
|
|
Можно считать, что машина М1 имеет два СТОП-состояния 
и 
, таких, что машина М1 приходит в состояние в том случае, когда для М1(Р) выполнено условие С, и в - в противном случае.
Итерацией называется операция установления обратной связи от машины МJ к машине МI, при которой выходное слово машины МJ подаётся на вход машины МI (СТОП-состояние МJ отождествляется с начальным состоянием МI). При этом образуется цикл; начало и конец цикла будем обозначать точкой (·) над соответствующими буквами. Если в МТ содержится несколько циклов, то начала и концы циклов обозначаются двумя (··), тремя (···) и т.д. точками над соответствующими буквами.
Указанные операции над МТ позволяют из более простых машин собирать суперпозицию МТ, реализующую более сложные алгоритмы.
Для построения ФС суперпозиции МТ поступают следующим образом (по умолчанию считаем, что у всех машин алфавиты одинаковы - 0 и 1).
1. Таблица составной машины имеет столько строк, сколько их в сумме во всех исходных машинах. Вначале эта таблица заполняется строками из ФС каждой исходной машины в том порядке, в каком они записаны в формуле (слева направо и сверху вниз).
2. Состояния в 1-й колонке формируемой таблицы заменяем состояниями общей машины так, чтобы их номера шли в порядке возрастания; во 2-й и в 3-й колонках проводим переобозначения состояний исходных машин в соответствии с проведенными заменами. При этом их СТОП-состояния не изменяются; не изменяются символы, записываемые на ленту, и символы команд на перемещение головки.
|
|
|
3. В заключение проводим переобозначения для СТОП-состояний. Для этого нужно уяснить, как проходит передача управления от машины к машине и как проявляются СТОП-состояния общей машины, т. е. необходимо отождествить состояния исходных машин и общей машины с учетом новых обозначений.
Пример 5.3. Пусть МТ С определена операцией умножения С=АВ[1], причём машины А и В заданы своими ФС (соответственно табл. 5.4. и 5.5).
Таблица 5.4 Таблица 5.5
| А | В | |||||
| А1 | 0RA2 | 0RA2 | B1 | 0RB2 | 1RB3 | |
| А2 | 1RA1 | 1LA0 | B2 | 1SB2 | 0LB1 | |
| B3 | 0SB0 | 1LB3 |
Построим таблицу результирующей машины. ФС для машины М приведена в табл. 5.6.
|
| М | ||
| С1 | 0RC2 | 0RC2 |
| С2 | 1RC1 | 1LC3 |
| С3 | 0RC4 | 1RC5 |
| С4 | 1SC4 | 0LC3 |
| С5 | 0SC0 | 1LC5 |
Пример 5.4. Машины Тьюринга A, B и C заданы своими ФС (табл. 5.7-5.9). Суперпозиция этих машин описывается формулой:
Таблица 5.7 Таблица 5.8 Таблица 5.9
| А | В | С | ||||||||
| А1 | 1RA1 | 0LA2 | В1 | 0RB2 | 0RB0(1) | С1 | 0LC1 | 1RC2 | ||
| А2 | 0RA2 | 1SA0 | В2 | 1RB1 | 1SB0(2) | С2 | 1RC1 | 0SC0 |
Построим ФС составной машины N. В соответствии с правилами построения результирующей таблицы запишем алфавит состояний МТ N: N={N0, N1, N2, N3, N4, N5, N6}; здесь обозначено: N1=B1, N2=B2, N3=C1, N4=C2, N5=A1, N6=A2.
Таблица 5.10
| N | ||
| N1 | 0RN2 | 1RN3 |
| N2 | 1RN1 | 1SN5 |
| N3 | 0LN3 | 1RN4 |
| N4 | 1RN3 | 0SN0 |
| N5 | 1RN5 | 0LN6 |
| N6 | 0RN6 | 1SN1 |
Приведем краткое описание работы общей МТ N. Её работа начинается с работы МТ B. Если она по результату обработки входного слова приходит к первому СТОП-состоянию, тогда работу продолжит МТ C; её СТОП-состояние - общее СТОП-состояние МТ N. Если машина В приходит ко вто-
рому СТОП-состоянию, тогда начнет работать МТ A; её СТОП-состояние отождествляется с начальным состоянием МТ В и далее процесс продолжится в зависимости от того, как поведет себя машина В.
5.4. Задания для самостоятельной работы
1. Используя правила композиции и ветвления, составить программу (ФС) МТ N, которая состоит из машин A, B, C, D.
| A | B | C | D | |||||||||||
| A1 | 0RA1 | 0SA2 | B1 | 0RB2 | 1RB0(1) | C1 | 1RC1 | 0RC2 | D1 | 0RD2 | 1SD0(1) | |||
| A2 | 0SA0(1) | 1RA2 | B2 | 1LB1 | 1SB0(2) | C2 | 0SC0(1) | 1SC0(2) | D2 | 1LD1 | 1SD0(2) |
1. 
4. 
|
2. 
|
2. Исследовать работу полученной машины М для приведённых конкретных конфигураций.
Структуры данных
Цель практического занятия по данной теме – рассмотреть основные виды структур данных: линейные списки и их разновидности, а также операции над ними.
Списки
Линейным списком ( просто списком) называется конечная последовательность элементов, взятая из некоторого множества. Различают списки односвязные, двусвязные, кольцевые, кольцевые двусвязные, а также их специфические варианты – стек и очередь [6].
В односвязном списке каждый элемент, кроме последнего, содержит ссылку на следующий элемент в списке, т.е. у каждого элемента есть два поля: имя и указатель (рис. 6.1а). Структура списка (рис. 6.1б) содержит указатель на первый элемент (First), который является внешним.
Эта структура данных позволяет заносить элемент в список и удалять элемент из списка без перемещения остальных элементов, т.е. без переобозначения их индексов. Заметим, что элементом списка может быть достаточно сложная структура данных, в том числе и список.
 |
Рассмотрим процедуры вставки элемента INS(NEL, FREE, POS) и удаления элемента DEL(POS) при работе с различными списками. Здесь NEL – новый элемент, FREE – индекс первой свободной ячейки, POS – позиция того элемента, после которого нужно вставить (удалить) элемент.
|
|
|
Пример 6.1. Задан список, состоящий из 6 элементов. Требуется выполнить следующее задание.
1. Записать список в виде двух массивов NAME и NEXT.
2. Вставить элемент А34 между А3 и А4; показать, как при этом изменяются массивы.
3. Удалить из исходного списка А5; показать, как при этом изменяются массивы.
Решение представлено в табл. 6.1 – 6.3, состоящих из трех основных столбцов: индекса, имени элемента – NAME и указателя на следующий элемент – NEXT.
|
| Индекс | NAME | NEXT |
| ---- | ||
| А1 | ||
| А2 | ||
| А3 | ||
| А4 | ||
| А5 | ||
| А6 | ||
| 7Free | ---- | ---- |
Таблица 6.2 Таблица 6.3
| Индекс | NAME | NEXT | Индекс | NAME | NEXT | |
| --- | --- | |||||
| A1 | A1 | |||||
| A2 | A2 | |||||
| 3 Pos | A3 | A3 | ||||
| A4 | 4 Pos | A4 | ||||
| A5 | 5 Free | |||||
| A6 | А6 | |||||
| A34 | ||||||
| 8 Free | --- | --- |
Двусвязный список
В двусвязном списке присутствует система двойных указателей, поэтому в таблице добавляется столбец PREV (previous - предыдущий), указывающий на связи с предыдущим элементом.
 |
Пример 6.2. Для двусвязного списка, состоящего из 6 элементов (рис. 5.2.), выполнить то же задание, что и в примере 6.1.
Решение представлено в табл. 6.4-6.6.
Таблица 6.4 Таблица 6.5
| Индекс | NAME | NEXT | PREV | Индекс | NAME | NEXT | PREV | ||
| ---- | ---- | ---- | ---- | ||||||
| A1 | A1 | ||||||||
| A2 | A2 | ||||||||
| A3 | 3 Pos | A3 | |||||||
| A4 | A4 | ||||||||
| А5 | A5 | ||||||||
| A6 | A6 | ||||||||
| 7 Free | --- | --- | --- | A34 | |||||
| 8 Free | --- | --- | --- |
Таблица 6.6
| Индекс | NAME | NEXT | PREV |
| ---- | ---- | ||
| A1 | |||
| A2 | |||
| A3 | |||
| 4 Pos | A4 | ||
| 5 Free | |||
| A6 |
|
|
|
Кольцевой список
Рассмотрим кольцевой список, в котором последний элемент имеет указатель на первый элемент.
 |
Пример 6.3. Задан кольцевой список, состоящий из шести элементов (рис. 6.3.); выполнить то же задание, что и в примере 6.1.
Решение опять представим в виде таблиц (табл. 6.7а, б, в) с тремя столбцами: индекс, имя и указатель на следующий элемент.
Разница между содержимым таблицы обычного списка (пример 1, табл. 6.1) и содержимым таблицы кольцевого списка (табл. 6.7а) в том, что в табл. 6.7а нет пустой строки и в 6–й строке NEXT[6] =1, а не пусто. Содержимое табл. 6.7б и 6.7в аналогично содержимому табл. 6.2 и 6.3 для простого списка.
Таблица 6.7а Таблица 6.7б Таблица 6.7в
| Индекс | NAME | NEXT | Индекс | NAME | NEXT | Индекс | NAME | NEXT | ||
| А1 | А1 | А1 | ||||||||
| А2 | А2 | А2 | ||||||||
| А3 | 3 Pos | А3 | А3 | |||||||
| А4 | А4 | 4 Pos | А4 | |||||||
| А5 | А5 | 5 Free | ||||||||
| А6 | А6 | А6 | ||||||||
| 7 Free | ---- | ---- | А34 | |||||||
| 8 Free | ---- | ---- |
Стек
Рассмотрим работу со стеком. Стек представляется массивом, в таблице – это столбец NAME. Вершина стека определяется значением переменной ТОР. Ввод и вывод элемента производится на одном конце списка. При работе со стеком производятся следующие операции:
вставка - TOP:=TOP + 1; <ввод элемента>;
удаление – <удаление элемента>; ТОР:= ТОР – 1;
Пример 6.4. В стек (рис. 6.4) поступило 4 элемента el1, el2, el3, el4.
1. Записать представление такого стека в виде массива NAME.
2. Вставить элемент el5.
3. Удалить элемент el4 (из исходного массива).
 |
 |
Рис. 6.4
|
|
| Индекс | NAME |
| EL1 | |
| EL2 | |
| EL3 | |
| 4 Top | EL4 |
Очередь
Рассмотрим работу с очередью. Здесь ввод производится в один конец очереди (хвост очереди), а вывод – из другого (голова очереди). В таблице для очереди используются указатели: Tail – хвост очереди, Head – голова очереди.
Пример 6.5. Очередь в текущий момент состоит из 5 элементов (рис.6.5); первые 9 элементов отсутствуют.
 |
|
Решение может быть представлено в виде трех таблиц, состоящих из двух основных столбцов: индекс и указатели Head, Tail, задающие направление очереди, а также имя элемента.
|
| ||||||||||||||||
Таблица 6.11
| Индекс | NAME |
| … | --- ... --- |
| 10 Head 14 Tail | EL1 EL2 EL3 EL4 EL5 |
