4. Способы задания автоматов. Матрица переходов и выходов. Определение.

Матрица переходов и выходов представляет собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из состояния q_m под действием входного сигнала x_f в состояние q_s, с выдачей выходного сигнала y_i, то на пересечении строки q_m и столбца q_s записывается пара x_f / y_i.

Для автомата Мура используется матрица, столбцы которой отмечены выходными сигналами y_i, а на пересечении ее строк и столбцов указываются только входные сигналы x_f.

Ниже приведены матрицы переходов и выходов для рассмотренных ранее автоматов A₁ и A₂ (рис. 4.6).

Рис. 4.6. Матрицы переходов и выходов автоматов А₁ (а) и А₂ (б).

5. Машины Тьюринга и конечные автоматы. Определение.

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

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

Определение.

Детерминированным конечным автоматом называют следующую пятерку:

А = (X, Q, δ, q₀, F),

где X = {x₁, ..., x_m} – входной алфавит (конечное множество входных сигналов);

Q = {q₀, q₁, ..., q_n-1} – алфавит состояний автомата (конечное множество символов);

δ – функция переходов;

q₀ ∈ Q – начальное состояние автомата;

F ⊆ Q – множество состояний, называемых заключительными.

На содержательном уровне функционирование конечного автомата можно представить следующим образом. Имеется бесконечная лента с ячейками, в каждой из которых может находиться один символ из Х. На ленте находится цепочка символов α∈ Х*. Ячейки слева и справа от цепочки не заполнены. Имеется некоторое конечное управляющее устройство с читающей головкой, которое может последовательно считывать символы с ленты, передвигаясь слева направо. При этом устройство может находиться в каком-либо одном состоянии из Q. Каждый раз, переходя к новой ячейке, устройство переходит к новому состоянию в соответствии с функцией δ.

На рис. 4.7 изображен конечный автомат в начальном состоянии q₀, считывающий первый символ х_i1 , входной цепочки α_i . Стрелкой показано направление движения читающей головки. Отображение δ можно представить в виде совокупности так называемых команд, которые обозначаются следующим образом:

(q, x) → q′,

где q, q′∈ Q; x = X.

Рис. 4.7. Интерпретация конечного автомата.

Определение.

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

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

Рис. 4.8. Графическое представление команды автомата.