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

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

где:

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

q0 - начальное (стартовое) состояние автомата ();

F - множество заключительных (или допускающих) состояний, таких что ;

У - допустимый входной алфавит (конечное множество допустимых входных символов), из которого формируются строки, считываемые автоматом;

д - заданное отображение множества во множество подмножеств Q:

(иногда д называют функцией переходов автомата).

Автомат начинает работу в состоянии q0, считывая по одному символу входной строки. Считанный символ переводит автомат в новое состояние из Q в соответствии с функцией переходов. Если по завершении считывания входного слова (цепочки символов) автомат оказывается в одном из допускающих состояний, то слово "принимается" автоматом. В этом случае говорят, что оно принадлежит языку данного автомата. В противном случае слово "отвергается".

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

Другие способы описания

Диаграмма состояний (или иногда граф переходов) - графическое представление множества состояний и функции переходов. Представляет собой нагруженный однонаправленный граф, вершины которого - состояния КА, ребра - переходы из одного состояния в другое, а нагрузка - символы, при которых осуществляется данный переход. Если переход из состояния q1 в q2 может быть осуществлен при появлении одного из нескольких символов, то над дугой диаграммы (ветвью графа) должны быть надписаны все они.

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

Детерминированность

Конечные автоматы подразделяются на детерминированные и недетерминированные.

Детерминированным конечным автоматом (ДКА) называется такой автомат, в котором для каждой последовательности входных символов существует лишь одно состояние, в которое автомат может перейти из текущего.

Недетерминированный конечный автомат (НКА) является обобщением детерминированного. Недетерминированность автоматов достигается двумя способами:

Если рассмотреть случай, когда автомат задан следующим образом:

,

где:

S - множество стартовых состояний автомата, такое что ;

Тогда появляется третий признак недетерминизма - наличие нескольких начальных (стартовых) состояний у автомата.

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

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

Автомамтное программимрование - это парадигма программирования, при использовании которой программа или её фрагмент осмысливается как модель какого-либо формального автомата.

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

Определяющими для автоматного программирования являются следующие особенности:

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

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

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

Название автоматное программирование оправдывается ещё и тем, что стиль мышления (восприятия процесса исполнения) при программировании в этой технике практически точно воспроизводит стиль мышления при составлении формальных автоматов (таких как машина Тьюринга, автомат Маркова и др.)

сфетофор visual basic модель

3. Схема и математическая модель работы светофора