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

Question

[Filipp42]

Здравствуйте, заинтересовался конечными автоматами, решил реализовать библиотеку для их удобного построения, но не могу найти достаточно статей и разборов. Подскажите пожалуйста хорошие.
Может быть вы сами работали с конечными автоматами и знаете, когда их применение удобно?
Расскажите, что сможете.
Когда конечный автомат переходит из одного состояния в другое, он выполняет какие-то действия?
Могут ли из одного состояния в другое, передаваться параметры, как из одной функции в другую?
Что это за входная строка такая? Можно ли обойтись без неё?
Заранее спасибо!

Answer 1

[Rsa97]

Посмотрите Книгу красного дракона и Введение в теорию автоматов.

Когда конечный автомат переходит из одного состояния в другое, он выполняет какие-то действия?

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

Могут ли из одного состояния в другое, передаваться параметры, как из одной функции в другую?

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

Что это за входная строка такая? Можно ли обойтись без неё?

Входная строка - это строка, состоящая из входных символов, которые управляют переходом автомата из состояния в состояние. Для чисел это будет набор символов +-123456789.e. Без входной строки автомату нечего будет распознавать.

Comments

[Filipp42]

А автомат всегда что-то распознаёт?
Скажите, вот это, конечный автомат или нет?

; Конечный автомат, описывающий дверь
(let ((state 'zaperto))
    (defun fsm (input)
        (case state
          ((zaperto)
           (cond ((eql input 'otopri)
                  (setf state 'zakrito))))
          
          ((zakrito)
           (case input
             ((otkroi) (setf state 'otkrito))
             ((zapri)  (setf state 'zaperto))))

           ((otkrito)
            (case input
              ((zakroi) (setf state 'zakrito))
              ((zapri)  (setf state 'zaperto)))))))

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

[Rsa97]

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

[Filipp42]

Rsa97, Спасибо!
Объясню, как я представляю конечный автомат на практике:
Конечный автомат - функция, замыкание (это значит она может работать с доступной только ей одной (почти одной) переменной), она принимает один параметр, в зависимости от текущего состояния делает с ним что-то, переходит в нужное состояние. Если надо, может возвращать какое-то значение.
Я правильно понимаю?

[Rsa97]

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

Answer 2

[Александр Скуснов]

Я столкнулся с ними по автоматике. Среди стандартных шести языков программирования контроллеров есть графический язык SFC (sequential flow chart). У него две разновидности (см. описание Codesys v.2): нестандартный (для каждого состояния описываются три процедуры: enter, during и exit, выполняемые при активации, во время активности (каждый скан) и при деактивации), и стандартный - привязка действий (actions) c условиями).

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

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

Comments

[Filipp42]

Скажите, вот это, конечный автомат или нет?

; Конечный автомат, описывающий дверь
(let ((state 'zaperto))
    (defun fsm (input)
        (case state
          ((zaperto)
           (cond ((eql input 'otopri)
                  (setf state 'zakrito))))
          
          ((zakrito)
           (case input
             ((otkroi) (setf state 'otkrito))
             ((zapri)  (setf state 'zaperto))))

           ((otkrito)
            (case input
              ((zakroi) (setf state 'zakrito))
              ((zapri)  (setf state 'zaperto)))))))

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

[Александр Скуснов]

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

[Filipp42]

Александр Скуснов,

[Александр Скуснов]

Да, вижу, что сходится. Только я не в курсе, что за язык.
Ещё не очень логично, что из состояния "открыто" можно сразу попасть в "заперто", минуя "закрыто". Но, как говорится, лишь бы в печку не ставить, автор может давать любые названия и рисовать любые стрелки.

[Александр Скуснов]

Ещё. если посмотрите Codesys и Stateflow, то увидите, что имеются параллельные структуры (цепочки, группы). Такого в обычных текстовых языках я не замечал. (в Stateflow такие состояния рисуются пунктиром и называются AND-группой. Обычная же группа называется XOR-группой, т.к. только одно состояние может быть активным (это ещё называется радиокнопками))

[Filipp42]

Александр Скуснов, Язык - Лисп, на нём можно написать библиотеку для конечных автоматов очень легко.