11.Методы задания машин Тьюринга

3 способа задания МТ: 1) табличный – достаточно задать 1 таблицу ; 2) в виде ориентированного графа (вершины соответствуют состояниям Q, дуги командам программы состояний из 6-ти знаков qiaj ? qi| aj| dk ); 3) задание МТ в виде строки знаков.

Абстрактные автоматы задаются с помощью таблиц переходов (выходов), гра-

фов, матриц переходов.

Таблица переходов (таблица выходов) автомата Мили представляет собой таб-

лицу, в которой левый столбец обозначается входными сигналами, а верхняя строка –состояниями, начиная с начального состояния. На пересечении строки и столбца указывается следующее состояние, в которое переходит автомат (в таблице переходов) или выходной сигнал, выдаваемый им (в таблице выходов).

Часто автомат задают с помощью графа автомата. Граф автомата – ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Иногда применяется способ задания автомата с помощью матрицы переходов и выходов, которая представляет собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из состояния qm под действием входного сигнала xf в состояние qs, с выдачей выходного сигнала yi, то на пересечении строки qm и столбца qs записывается пара xf / yi.

12.Граф-схемы и их связь диаграммой состояний автоматов.

Граф-схема алгоритма - алгоритм описанный специальными графическими символами.

Диагра́мма состоя́ний — ориентированный граф для конечного автомата, в котором

• вершины обозначают состояния

• дуги показывают переходы между двумя состояниями

На практике вершины обычно изображаются в виде окружностей и, если нужно, двойных окружностей. В нотации UML состояния изображаются прямоугольниками с закругленными углами^[1].

Ориентированный граф (кратко орграф) — (мульти) граф, рёбрам которого присвоено направление. Направленные рёбра именуются также дугами, а в некоторых источниках (Оре) и просто рёбрами.

Конечный автомат — абстрактный автомат без выходного потока, число возможных состояний которого конечно. Результат работы автомата определяется по его конечному состоянию.

большую наглядность обеспечивает задание конечных автоматов с помощью графов или диаграмм состояний.

Граф автомата состоит из узлов, соединенных ветвями. Узлы (кружки на схеме графа) отождествляют внутренние состояния автомата. Каждая ветвь графа, т.е. ориентированная линия, стрелка которой указывает следующее состояние автомата, отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе. Входной и соответствующий ему выходной сигналы разделяются на чертеже запятой или косой чертой. Если некоторый входной сигнал не меняет состояния автомата, то соответствующая ветвь замыкается на кружке (узле), из которого она выходит.

Поскольку таблица состояний и граф (диаграмма) состояний несут одну и ту же информацию, их можно преобразовать друг в друга. Каждое состояние представляется кружком, а каждый элемент таблицы преобразуется в отрезок ориентированной линии, соединяющей соответствующие кружки. Процедура обратного преобразования очевидна.

В настоящее время в классе синхронных автоматов рассматривают, в основном, два типа автоматов: автомат Мили и автомат Мура.