7.2. Определение и задание автоматов

Алфавитом называется всякое конечное множество A = {a₁, . . . , a_n}. Элементы множества A называются символами.

Определение

Конечным автоматом называется всякая пятерка

A = (A, B, Q, , ), где:

1. A  входной алфавит;

2. B  выходной алфавит;

3. Q  конечное множество состояний автомата;

4. : A  Q  Q  функция перехода;

5. : A  Q  B  функция выхода автомата.

В дальнейшем мы будем использовать наименование автомата, применительно только к конечным автоматам.

Символы входного и выходного алфавитов представляют входные и выходные сигналы автомата.

Отображения  и  задают функционирование автомата A и называются функциями перехода и выхода.

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

Отображение  задает символ на выходе A для такой же ситуации.

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

Рассмотрим основные способы представления автоматов.

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

Пусть  = (A, B, Q, , )  это автомат и A = {a₁, . . . , a_m}, Q = {q₁, . . . , q_r}.

Изобразим состояния  с помощью системы из r непересекающихся кругов на плоскости, которые помечены символами этих состояний. Из каждого круга, изображающего состояние, проведем m ориентированных дуг, каждая из которых помечена одним из символов входного алфавита.

Дуге, выходящей из состояния q_j, помеченной входным символом a_i, припишем также выходной символ (a_i, q_j), заключив его в скобки.

Проведем эту дугу в состояние (a_i, q_j).

Соответствующий фрагмент изображения автомата имеет вид, приведенный на рис.7.1.

q_j q_k

a_i((a_i, q_j))

Рис. 7.1

Здесь q_k = (a_i, q_j).

Построенное по заданным правилам представление автомата называется диаграммой переходов.

Диаграммы переходов полностью определяют представляемые ими автоматы.

Множества A и B определяются символами, приписанными дугам без скобок и в скобках соответственно.

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

Множество всех состояний автомата  задается помеченными кругами.

Отображения  и  полностью представлены в диаграмме. При этом значение (a_i, q_j) равно состоянию, в которое ведет дуга диаграммы, выходящая из состояния q_j и помеченная входным символом a_i.

Значение (a_i, q_j) равно символу выходного алфавита, который приписан в скобках для той же дуги.

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

Если в некоторый момент времени t автомат  находится в состоянии q_j и на его вход поступает символ a_i, то функционирование этого автомата можно представить с помощью перемещения по диаграмме из состояния q_j по дуге, помеченной входным символом a_i.

При этом выбранная дуга ведет в состояние, в котором  будет находиться в момент времени t + 1. Символ на выходе автомата в момент t приписан этой же дуге в скобках.

Поэтому функционирование автомата  в последовательные моменты t₀, t₀+1, . . . , t₀+i, . . . можно промоделировать с помощью прохождения соответствующего пути в диаграмме переходов.

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