Конечные автоматы

Формальной основой ЛА являются конечные автоматы (КА). Конечный автомат является принципиально более простой формальной моделью, нежели компьютерная программа (машина Тьюринга). Программа включает в себя две компоненты: алгоритм и произвольным образом организованные неограниченного объема данные. Конечный автомат не содержит данных и представляет собой алгоритмическую часть программы в чистом виде. Т.е. он представляет собой систему, которая реагирует только на изменение состояния внешней среды, но не способна к запоминанию. Она не имеет изменяемой памяти, сама управляющая информация о структуре автомата хранится в постоянной памяти (обычно в табличной форме). Единственным хранимым параметром автомата является его текущее состояние, которое характеризует текущий шаг выполняемого алгоритма (аналог регистра текущей команды процессора - IP).

Отсутствие собственной памяти задает принципиально другую «модель поведения», аналог которой имеется в животном мире:

· конечный автомат моделирует «инстинктивное» поведение, основанное на воспроизведении программы действий, меняющейся в зависимости от последовательности внешних событий, но не запоминающей информации из внешней среды;

· компьютерная программа моделирует «рефлекторное» поведение, принципиально связанное с запоминанием и обработкой информации о внешних событиях и настройкой (адаптацией) к ним.

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

Теперь приведем формальное определение КА в терминах дискретной математики и теории множеств. Конечный автомат определяется шестью компонентами

A = { I, O, S, S₀, P, D }

· множество (алфавит) входных символов I={I_i};

· множество (алфавит) входных символов O={O_j};

· множество состояний автомата S={S_k};

· начальное состояние S₀ S;

· функция переходов P(S_, I) => S, ставящая в соответствие каждой паре «состояние - входной символ» новое состояние;

· функция выходов D(S_, I) => O, ставящая в соответствие каждой паре «состояние - входной символ» выходной символ.

Опишем, как выглядит работа такой системы:

· КА является дискретной системой, работающей по тактам (шагам), в каждом из которых он получает на вход один из символов входного алфавита;

· последовательность символов на входе КА образует входную цепочку;

· на каждом шаге КА находится в одном из возможных состояний, которое называется текущим. Текущее состояние – единственная характеристика внутреннего описания КА, которая меняется при его работе (изменяемая память). Все остальные элементы его описания являются статическими (т.е. в любой реализации представляют собой постоянную память);

· шаг работы КА состоит в переходе из текущего состояния в новое состояние при получении на вход очередного символа входной цепочки. Этот переход определяется функцией переходов;

· результат работы КА заключается в записи в выходную цепочку символов, генерируемых функцией выходов КА. Т.е. параллельно с переходом в новое состояние формируется выходной символ, определяемый парой «текущее состояние – входной символ». Выходной символ может быть и пустым;

Работа КА заключается в преобразовании входной цепочки символов в выходную. Закон этого преобразования определяет поведение КА. Задача проектирования КА состоит в создании КА, обеспечивающем заданные правила преобразования цепочек. Очевидно, что отсутствие у КА внутренней памяти ограничивает его возможности по преобразованию цепочек (общепринятый термин - моделирующая способность). С другой стороны, эти же ограничения позволяют решать в общем случае многие проблемы (термин – алгоритмическая разрешимость, т.е. принципиальная возможность разработать соответствующий алгоритм).

Хотя автоматы и можно представить в традиционной для алгоритма технологии блок-схем (управляющие КА так и строятся на основе разметки блок-схемы алгоритма), наиболее удобной формой их представления для человека является графическая - диаграмма состояний-переходов, а для программирования и формальных преобразований – табличная. Основные элементы диаграммы состояний – переходов:

· состояние представляет собой окружность, содержащую номер или наименование состояния;

· направленная дуга, соединяющая состояния S_k и S_m, определяется значениями функций переходов и действий: если S_m=P(S_k, I_i) и O_n=D(S_k, I_i), то имеется переход КА из S_k в S_m, который обозначается дугой, соединяющей эти вершины. Дуга подписывается парой символов I_i/O_n. Это означает, что переход по дуге при поступлении на вход символа I_i сопровождается формированием выходного символа O_n.

Если поведение какого-либо объекта можно описать набором предложений вида: «Находясь в состоянии A, при получении сигнала S объект переходит в состояние B и при этом выполняет действие D», то такая система будет представлять собой конечный автомат.

Анализируя приведенный здесь пример диаграммы состояний-переходов и вид преобразования цепочек, можно сделать вывод о поведении автомата и сущности выполняемых им преобразований. Нетрудно заметить, что получая входные цепочки, содержащие символы a и b в произвольном порядке, КА формирует аналогичные цепочки более регулярного вида. Так, из подряд идущих символов b он оставляет один, а в последовательности символов a оставляет все нечетные, кроме первого. При нечетном количестве символов a на входе КА добавляет еще один символ a в выходную последовательность. Отсюда можно вычислить закон преобразования длины входной цепочки символов a - N_a(out) = (N_a(in)+1)/2

Анализируя состояния и условия переходов в них, можно определить их содержательный «смысл»: состояния S_1, S₂ обозначают нечетное и четное число подряд прочитанных символов a.

Табличная форма представления КА включает в себя представление функций переходов и выходов виде таблиц.

На диаграмме состояний-переходов не может быть двух и более дуг из одного состояния, помеченных одним и тем же входным символом. Если это не так, то такая неканоническая форма называется недетерминарованным КА. Такой КА не имеет адекватного табличного (функционального) представления, но может быть преобразован в обычный детерминированный.