3.2.2. Способы задания конечных автоматов

Таблицы переходов и выходов

Этот способ задания автоматов основан на представлении автомата двумя таблицами с одинаковым числом строк и столбцов. Строки таблицы обычно сопоставляются символам входного алфавита X, а столбцы – символам внутреннего алфавита Q (состояниям).

В таблице переходов элемент (i, j) представляет состояние, определяемое значением функции ψ(x, q), в которое автомат перейдет в момент времени t + 1, если в момент времени t он находится в состоянии q, сопоставляемом j-му столбцу, и его входной символ x принимает значение, сопоставляемое i-й строке.

В таблице выходов элемент (i, j) представляет символ выходного алфавита в момент времени t, определяемый значением функции φ(x, q), если в момент времени t он находится в состоянии q, сопоставляемом j-му столбцу, и его входной символ x принимает значение, сопоставляемое i-й строке.

Речь идет о таблицах переходов, выходов полностью определенного автомата Мили.

Автомат Мили – это пятерка объектов <X, Q, Y, ψ, φ>, где X – входной алфавит; Y – выходной алфавит; Q – внутренний алфавит или множество состояний автомата; ψ – функция переходов; φ – функция выходов.

Функция ψ определяется на множестве XQ и принимает значения на множестве Q:

ψ: XQ  Q.

Функция φ также определяется на множестве XQ и принимает значения на множестве Y:

φ: XQ  Y.

В случае не полностью определенных автоматов некоторые клетки таблиц могут быть пустыми или заполнены прочерками (рис. 3.10).

Рис. 3.10

Иногда таблицы переходов и выходов совмещают, при этом элемент (i, j) состоит из двух составляющих. Левая составляющая представляет содержимое таблицы переходов, а правая – таблицы выходов. Составляющие отделяются друг от друга либо запятой, либо наклонной чертой (рис. 3.11).

Рис. 3.11

Заметим, что в случае автомата Мура таблица выходов вырождается в единственную строку.

Автомат А называется автоматом Мура, если его функция выхода не зависит от символов входного алфавита, то есть его функции переходов, выходов имеют вид

ψ : XQ  Q,

φ: Q  Y.

Для автономного автомата однострочными являются как таблица переходов, так и таблица выходов.

В случае комбинационного автомата таблица переходов отсутствует, а таблица выходов вырождается в единственный столбец.

Иногда в таблицах переходов и выходов строки сопоставляются состояниям, а столбцы – символам входного алфавита.

КАДР

Диаграмма переходов

Пусть U и V – произвольные алфавиты. Диаграммой в алфавитах U и V называется всякий ориентированный граф, вершины которого сопоставлены символам алфавита U, а ориентированные ребра произвольным образом помечены символами алфавита V или пустым символом λ.

Диаграммой переходов автомата (автоматной диаграммой переходов) называется диаграмма в алфавитах Q, XY, вершины которой сопоставлены состояниям автомата, а дуги сопоставляются парам (q, ψ(x, q)). Дуга направлена из q в ψ(x, q) и помечена парой (x, φ(x, q)) или (x, –), если значение φ(x, q) не определено.

Итак, всякий автомат задается диаграммой в алфавитах Q, XY, но не всякая диаграмма в этих алфавитах является автоматной диаграммой. В автоматной диаграмме в силу однозначности функции переходов автомата не существует двух дуг, исходящих из одной и той же вершины и имеющих одну и ту же первую метку (один и тот же входной символ) в парах, помечающих дуги.

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

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

Для автоматов Мура второй символ принято использовать для обозначения вершин.

Диаграмма переходов автомата без памяти содержит единственную вершину. В ней начинаются и заканчиваются все дуги диаграммы.

Диаграмма переходов автомата без выхода строится в алфавитах Q, X. Каждая дуга помечена только входным символом.

На рис. 3.12 представлена диаграмма переходов, сопоставляемая следующим таблицам переходов и выходов:

Рис. 3.12

Пусть таблицы переходов и выходов автомата Мура имеют вид

Тогда ей соответствует диаграмма переходов на рис. 3.13.

Рис. 3.13

Между диаграммами переходов и таблицами переходов и выходов имеет место взаимно-однозначное соответствие.

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

КАДР