§ 3.5. Методы задания конечного автомата и последовательностной машины

Любая функция

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

Уравнение конечного автомата типа П — П

или типа П — Н

также может быть представлено аналогичной таблицей (табл. 3.2).

Таблица 3.1

Таблица 3.2

В каждую клетку табл. 3.2 вписываются символы если строка соответствует символу , а столбец — символу в автомате типа П — П (или в автомате типа П — Н). Такую таблицу будем называть далее основной таблицей конечного автомата.

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

Рассмотрим какой-либо один такой автономный автомат (например, табл. 3.3).

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

Подхадить же к каждому кружку может любое число , не превышающее k. Граф автономного автомата, показанный на рис. 3.5, соответствует табл. 3.3. Из конечного автомата можно построить автономных автоматов , и соответственно по основной таблице конечного автомата можно определить графов этих автономных автоматов. На рис. 3.6 они показаны для случая табл. 3.4.

Рис. 3.5.

Таблица 3.3

Таблица 3.4

Все эти графов имеют одинаковое число k кружков и могут быть теперь объединены в одий граф, если над каждой стрелкой надписью указать значение , при котором эта стрелка реализуется. Надпись проставляется у начала стрелки при автомате типа П — П и у конца стрелки при автомате типа .

На рис. 3.7 показан такой объединенный граф для рассмотренного выше примера (табл. 3.4, рис. 3.6) автомата типа П — Н.

Рис. 3.6.

Рис. 3.7.

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

Диаграмма состояний полностью эквивалентна основной таблице и также задает конечный автомат. По диаграмме состояний немедленно восстанавливается основная таблица и автомата.

Составим квадратную матрицу С. Припишем ее строкам сверху вниз и столбцам слева направо символы . Элементом матрицы, стоящим на пересечении строки и столбца , служит надпись на стрелке, которая на диаграмме состояний ведет из кружка в кружок Этим элементом может быть один символ или дизъюнкция нескольких . Если кружок на диаграмме состояний не соединен стрелкой с кружком то в соответствующую клетку матрицы С вписываем 0.

В качестве примера приведем матрицу (табл. 3.5), соответствующую диаграмме состояний, построенной на рис. 3.7.

Таблица 3.5

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

В каждой строке матрицы соединений обязательно содержится любое из , и при этом только один раз. Матрица соединений может быть выписана по основной таблице, минуя составление диаграммы состояний.

Пусть задана основная таблица для автомата типа П — П, т. е. для соотношения

Каждая клетка основной таблицы определяет тройку символов

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

Все изложенное распространяется и на автоматы типа П — Н, т. е. на автоматы, задаваемые соотношением

в этом случае триаду образует тройка символов

и упорядоченным называется множество, не содержащее двух триад с одинаковыми первыми двумя символами

Переходя к заданию последовательностной машины, приходится совместно рассматривать одно из уравнений (3.5) автомата и уравнение (3.8) преобразователя. Возвращаясь к основной таблице конечного автомата, впишем в каждую клетку не один символ, как ранее, а два: символ и, в соответствии с уравнением преобразователя, символ Если рассматривается автомат типа П — П (уравнение (3.5)), то в каждую клетку, кроме символа вписывается символ , т. е. попросту таблица преобразователя вписывается в основную таблицу автомата.

Такую объединенную таблицу автомата и преобразрвателя назовем основной таблицей П-машины.

Так, например, если автомат типа П — П задан табл. 3.4, а преобразователь — табл. 3.6, то основная таблица П-машины имеет вид табл. 3.7.

Таблица 3.6

Таблица 3.7

Если же рассматривается автомат типа П — Н (уравнение ), то в каждую клетку вписывается символ соответствующий по таблице преобразователя символу стоящему в этой клетке, и символу этегв же втелбца. В рассмотренном примере (автомат — 3.4, преобразователь — табл. 3.6) основная таблица П-машины имеет вид табл. 3.8 (стр. 108).

Заметим, что в случае автомата П — Н могут быть заполненными не все клетки таблицы преобразователя: в каждом столбце таблицы преобразователя заполнены лишь клетки, соответствующие таким , которые содержатся в том же столбце таблицы автомата.

Рис. 3.7.

Так, например, в столбце автомата табл. 3.4 не встречается символ . Поэтому в таблице преобразователя клетка могла бы вообще быть не заполненной.

Рис. 3.8.

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

В П-машине символ определяется не только символом , но и . Поэтому диаграмма состояний П-машины отличается от диаграммы состояний конечного автомата с преобразователем тем, что символ вписывается не в кружке, а рядом с символом над стрелкой. Стрелка ведет от состояния к состоянию . При автомате типа П — П (уравнение ) пара символов () надписывается у начала стрелки (вблизи кружка — рис. ), при автомате типа П — Н (уравнение ) — у конца стрелки (вблизи кружка — рис. ). В первом случае символ к определяется из таблицы выходного преобразователя по символу , надписанному над стрелкой, и символу и, надписанному в кружке, из которого выходит стрелка; во втором же случае — по символу над стрелкой и символу в кружке, к которому подходит стрелка.

На рис. 3.9 в качестве примера показана диаграмма состояний, построенная по табл. 3.8.

Таблица 3.8

По диаграмме состояний последовательностной машины может быть немедленно построена матрица соединений. Она отличается от матрицы соединений конечного автомата тем, что элементами ее служат надписи над стрелками диаграммы состояний, т. е. пары символов (). Для табл. 3.8 (см. диаграмму состояний рис. 3.9) матрица соединений имеет вид, показанный в табл. 3.9.

Таблица 3.9 (см. оригинал)