Абстрактное определение конечного автомата

Абстрактным описанием ЦВМ служит математическое понятие конечного автомата.

Определение. Конечным автоматом называется набор из пяти объектов:

, где

- конечный список входных символов (входной алфавит);

- список выходных символов (выходной алфавит);

- множество внутренних состояний;

- функция перехода в следующее состояние;

- функция выхода.

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

Рис. 3

Входная лента

Выходная лента

В определении конечного автомата предполагается, что функции и всюду определены. Такое описание автомата называется полным.

Пример. Автомат имеет входной алфавит, выходной алфавит, множество внутренних состояний.Функции перехода и выхода задаются предписаниями:

Таблица 5

Подадим на вход последовательность 0,1,0,1. Если автомат находился в состоянии, то считав первый символ 0, он перейдёт в состояние и напечатает 0. Считав затем 1, он перейдёт в состояние и напечатает 0. Считав следующий 0, он перейдёт в состояние и напечатает 1. Наконец, считав последний символ 1, автомат закончит работу в состоянии, печатая 0. Таким образом, автомат преобразовал входной сигнал 0101 в сигнал 0010 на выходе.

Возможны следующие способы описания конечного автомата:

1) С помощью диаграммы состояний, которая представляет собой ориентированный граф. Вершины этого графа помечаются символами, обозначающими внутренние состояния автомата. А каждая дуга помечается упорядоченной парой символов. Первый символ есть входной символ, вызывающий переход автомата в следующее состояние. Второй символ - выходной символ, который автомат печатает. Диаграмма состояния для выше приведённого примера имеет вид.

Рис. 4

2) Второй способ описания конечного автомата – таблица состояний – это табличное представление функций и. В соответствии с примером

Таблица 6

Текущее состояние	Следующее состояние	Выход

Оба способа описания конечного автомата имеют свои преимущества и недостатки. Таблица состояний удобна при вычислениях, а диаграмма состояний является более наглядной. В частности, по диаграмме состояний конечного автомата можно обнаружить состояния недостижимые из других состояний. Например:

Рис. 5

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

7.3. Автоматные функции и эксперименты с автома тами

Дата добавления: 2014-01-11