Где найти примеры конечных автоматов?

[Uana]

Где найти примеры конечных автоматов?
Где найти теорию и рализацию в программном коде?

[Dimka]

Последняя статья Alf'а про рекурсию - там в общих чертах и с простейшим примером.

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

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

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

Таблица переходов эквивалентна грамматике языка автомата - правилам перевода автомата из одного состояния в другое. Под языком понимается набор всех входных символов.

[Dimka]

Простейший автомат поведения льва

Входные символы: "антилопа", "охотник".
Внутренние состояния: "сытый", "голодный".
Действия автомата: "съесть", "спать", "убежать"
Таблица переходов:

Код:

        |сытый                                |голодный
--------|-------------------------------------|---------------------------------
антилопа|спать, перейти в состояние голодный  |съесть, перейти в состояние сытый
--------|-------------------------------------|---------------------------------
охотник |убежать, перейти в состояние голодный|убежать

Условий завершения работы автомата здесь нет.

[Mfcer__]

Вот статьи про конечные автоматы
http://www.rsdn.ru/article/alg/FiniteStateMachine.xml
http://www.rsdn.ru/article/alg/checkStr.xml
http://www.rsdn.ru/article/alg/statemachine.xml

[Uana]

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

[Serega]

Тут много про автоматы

[Olegator]

Почему именно "конечные" автоматы? Это связано с конечностью состояний?
Внутренних?
Внешних?
Обоих?

[Finch]

Количество состояний "Конечных" автоматов строго определено. Состояние  изменяется квантовано внешним воздействием.  Количество внешних воздействий не ограничено.