@Filipp42

Какая есть литература по конечным автоматам?

Здравствуйте, заинтересовался конечными автоматами, решил реализовать библиотеку для их удобного построения, но не могу найти достаточно статей и разборов. Подскажите пожалуйста хорошие.
Может быть вы сами работали с конечными автоматами и знаете, когда их применение удобно?
Расскажите, что сможете.
Когда конечный автомат переходит из одного состояния в другое, он выполняет какие-то действия?
Могут ли из одного состояния в другое, передаваться параметры, как из одной функции в другую?
Что это за входная строка такая? Можно ли обойтись без неё?
Заранее спасибо!
  • Вопрос задан
  • 149 просмотров
Пригласить эксперта
Ответы на вопрос 2
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Посмотрите Книгу красного дракона и Введение в теорию автоматов.
Когда конечный автомат переходит из одного состояния в другое, он выполняет какие-то действия?
Может выполнять. Скажем, для распознавания ключевых слов достаточно знать, в каком допускающем состоянии оказался автомат, а вот для распознавания чисел уже необходимо при переходе выполнять дополнительные действия.
Могут ли из одного состояния в другое, передаваться параметры, как из одной функции в другую?
Кроме текущего состояния автомат может помнить какой-то набор параметров, не влияющих на переходы, но меняющийся при переходах. Пример - то же самое распознавание чисел. Автомат должен вычислить/запомнить знак, мантиссу и значение степени.
Что это за входная строка такая? Можно ли обойтись без неё?
Входная строка - это строка, состоящая из входных символов, которые управляют переходом автомата из состояния в состояние. Для чисел это будет набор символов +-123456789.e. Без входной строки автомату нечего будет распознавать.
Ответ написан
@AlexSku
Программист по автоматике
Я столкнулся с ними по автоматике. Среди стандартных шести языков программирования контроллеров есть графический язык SFC (sequential flow chart). У него две разновидности (см. описание Codesys v.2): нестандартный (для каждого состояния описываются три процедуры: enter, during и exit, выполняемые при активации, во время активности (каждый скан) и при деактивации), и стандартный - привязка действий (actions) c условиями).

Но более продвинутая версия это Stateflow в MatLab / Simulink. Рисуются немного по-другому. Там ещё можно выполнять действия во время перехода (причём даже во время такого, который мог состояться, но не состоялся). Кроме условий перехода и функций enter, during, exit есть ещё события (events) и их обработка. Можно оформить в виде классических схем Мура и Мили (но сомневаюсь, что кто-нибудь это делает). Есть дополнения в виде логических таблиц и логических схем переходов. Почитать можете просто документацию. (русский перевод можно найти на сайте exponenta.ru). Хорошее введение в плейлисте экспоненты Управляющая логика.

Как вы поняли, я вам привёл два примера реализации, а не саму математическую теорию. (если же брать математику, то и её бы я реализовал на Haskell, поскольку там любая математика описывается очень лаконично).
(кстати, уже есть на Haskell пример)
Ответ написан
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы