Для каких задач подходят конечные автоматы?

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

Рабочий процесс (см. WF в .NET 3.0)

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

Пример парсера. Недавно я написал парсер, который берет двоичный поток из другой программы. Значение текущего анализируемого элемента указывает размер / значение следующих элементов. Возможно (небольшое) конечное число элементов. Отсюда государственная машина.

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

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

По мере увеличения количества возможных значений статуса количество переходов увеличивается. В этом случае государственные машины очень помогают.

На ум приходят:

• Robot/Machine manipulation... those robot arms in factories
• Simulation Games, (SimCity, Racing Game etc..)

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

Однако мало что из того, что я знаю, не сводится к проблеме синтаксического анализа.

ИИ в играх очень часто реализуется с помощью государственных автоматов. Помогает создать дискретную логику, которую намного проще построить и протестировать.

Объекты в играх часто представлены в виде конечных автоматов. ИИ-персонаж может быть:

• Охрана
• Агрессивный
• Патрулирование
• Спящий

Таким образом, вы можете видеть, что они могут моделировать некоторые простые, но эффективные состояния. Конечно, вы могли бы сделать более сложную непрерывную систему.

Другой пример - такой процесс, как покупка в Google Checkout. Google дает несколько состояний для Финансов и Порядка, а затем информирует вас о переходах, таких как очистка кредитной карты или получение отказа, и позволяет вам сообщить ему, что заказ был отправлен.

Сопоставление регулярных выражений, парсинг, управление потоком в сложной системе.

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

Конечные автоматы, если их хорошо реализовать, будут очень эффективными.

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

http://research.cs.queensu.ca/~thurston/ragel/

Это также позволяет избежать страшного «goto».

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

В этом примере каждая комната в игре считается одним государством.

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

Хороший ресурс - это бесплатный Электронная книга конечного автомата. Мой собственный быстрый ответ ниже.

Если ваша логика должна содержать информацию о том, что произошло при последнем запуске, она должна содержать состояние.

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

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

1. сбросить модем
2. инициировать связь с модемом
3. дождитесь уровня сигнала, который укажет на хорошее соединение с вышкой
4. ...

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

enum states{reset,initsend, initresponse, waitonsignal,dial,ppp,...}
modemfunction()
{
  static currentstate

  switch(currentstate)
  {
  case reset:
    Do reset
    if reset was successful, nextstate=init else nextstate = reset
    break
  case initsend
    send "ATD"
    nextstate = initresponse 
    break
  ...
  }
currentstate=nextstate
}

Более сложные конечные автоматы реализуют протоколы. Например, протокол диагностики ЭБУ, который я использовал, может отправлять только 8-байтовые пакеты, но иногда мне нужно отправлять пакеты большего размера. ЭБУ работает медленно, поэтому мне нужно дождаться ответа. В идеале, когда я отправляю сообщение, я использую одну функцию, и тогда мне все равно, что происходит, но где-то моя программа должна отслеживать линию и отправлять и отвечать на эти сообщения, разбивая их на более мелкие части и повторно собирая части полученных сообщений в последнее сообщение.

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

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

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

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

Примеры этого потока ввода: некоторый текстовый файл в случае синтаксического анализа, строка для регулярных выражений, такие события, как player entered room для игрового AI и т. д.

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

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

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

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

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