Что такое конечные автоматы и почему о них должен знать программист?

Хм ... что вопрос сказал. Это то, о чем я постоянно слышу, но я еще не дошел до того, чтобы разобраться в этом.


(обновлено) Я мог бы посмотреть определение ... но почему бы (как указал @erikson) получить представление о вашем реальном опыте и анекдотах. Сообщество вики-сообщества, которое помогает людям голосовать за самый проницательный ответ. Интересное чтение, спасибо!

12.12.2008 21:24:56
12 ОТВЕТОВ
РЕШЕНИЕ

Короткий ответ: это метод, который вы можете использовать для выражения систем с конкретными состояниями (в отличие от квантовых состояний / вероятностных распределений).

Цитирую статью из Википедии :

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

Итак, что это значит для вас? Проще говоря, это эффективный способ представления пути (ей) от начального состояния до конечного состояния (ей) системы, которая вас интересует. Используя регулярные выражения в качестве довольно простого для понимания примера, давайте рассмотрим шаблон AB + C (представьте, что этот плюс является верхним индексом). Я ожидаю, что этот шаблон будет принимать строки, такие как «ABC», «ABBC», «ABBBC» и т. Д. A в начале, C в конце, некоторое количество B в середине (больше или равно единице) ,

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

      _
     ( ) 
A --> B --> C

С помощью FSA вы можете продолжить свой путь к вычислительной сложности, отправившись в страну машин Тьюринга .

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

13
5.02.2013 02:38:15
Спасибо - я не мог придумать другой способ нарисовать картину, не будучи «претенциозным Visio» в людях.
Bob Cross 7.07.2009 01:50:57
Разве ваша картинка не подразумевает, что в выражении будет хотя бы одна буква "B"? Вы вычисляете AB + C.
Roland 5.02.2013 00:24:34
@ Мистер Роланд, ты не ошибся. Я изменю выражение на B + вместо B *.
Bob Cross 5.02.2013 02:37:08
@BobCross Потому что исправить рисунок немного сложнее, верно?
Loïc Faure-Lacroix 24.04.2017 17:56:39
@ LoïcFaure-Lacroix, нет, я думаю, что картина рассказывает важную историю. Это иллюстрирует скромно сложную концепцию.
Bob Cross 25.04.2017 21:18:33

Да! Вы можете посмотреть это!

http://en.wikipedia.org/wiki/Finite_state_machine

1
12.12.2008 21:28:50
Было бы более интересно услышать некоторые анекдоты не-NPOV о том, почему программист будет заботиться о них.
erickson 12.12.2008 21:31:45
оригинальные исследования приветствуются!
Jimmy 12.12.2008 21:47:56

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

Типичным примером является игровой ИИ, где у NPC разные состояния, которые меняются в зависимости от того, где находится игрок, что-то вроде:

  • NPC_STATE_IDLE
  • NPC_STATE_ALERT (игрок на расстоянии менее 100 метров)
  • NPC_STATE_ENGAGE (игрок атаковал NPC)
  • NPC_STATE_FLEE (низкий уровень здоровья)

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

2
12.12.2008 22:03:03

Вы можете посмотреть это, но какого черта. Интуитивно понятно, что конечный автомат - это абстракция чего-то, имеющего конечное число состояний и правил, по которым вы можете переходить из одного состояния в другое. Состояние является то , для чего может быть истинным или ложным утверждение, и правило это способ , которым вы переход от одного состояния к другому. Таким образом, вы можете иметь, скажем, два состояния: «Я дома» и «Я на работе» и два правила: «Иди на работу» и «Иди домой».

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

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

Формально FSA - это алгебраическая структура F = ⟨Σ, S, s 0 , F, δ⟩, где Σ - входной алфавит , S - набор состояний , s 0 ∈ S - конкретное начальное состояние , F ⊆ S - набор принимающих состояний , и δ: S × Σ → S - функция перехода состояний .

9
12.12.2008 21:46:53
Формально, а? :-) Меня довольно хорошо одолели за то, что я общался с программистами формально. Приветствия.
Mike Dunlavey 8.01.2009 21:49:00
Не заводи меня, Майк. Я не знаю, как часто меня спрашивали "всегда ли это должно быть как математическая задача?" Единственный ответ - «Да. Информатика - это математический предмет».
Charlie Martin 9.01.2009 01:03:32
Да, хотя иногда я думаю, что у разных языков есть свои приверженцы, это почти как музыкальные жанры.
Mike Dunlavey 9.01.2009 01:26:39
Да, вы знаете, я не думаю, что когнитивная связь между музыкой и программированием когда-либо изучалась достаточно. С другой стороны, я думаю, что языковые вопросы могут больше походить на теологию.
Charlie Martin 9.01.2009 01:48:41
Говоря о FSA, вас может заинтересовать этот документ, который я написал в 98 году. arxiv.org/PS_cache/quant-ph/pdf/9807/9807026v1.pdf Он был мотивирован попыткой найти лучший способ доказать правильность программного обеспечения.
Mike Dunlavey 10.01.2009 16:19:54

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

Почему вы должны их знать: потому что вы, вероятно, уже реализовали их.

Каждый раз, когда ваш код имеет ограниченное число возможных состояний (это часть «конечного состояния») и переключается на другое, как только произойдет какой-то ввод / событие (это часть «машины»), вы написали конечный автомат.

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

1
12.12.2008 21:49:15

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

Поскольку веб-сервисы часто не заполнены, вы обычно не видите их в веб-сервисах - вы перестраиваете свой URL так, чтобы каждый URL соответствовал одному пути в коде.

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

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

Чаще всего FSM реализуется как оператор switch, который включает переменную. Каждый случай - это другое состояние. В конце дела вы можете установить состояние на новое значение. Вы почти наверняка видели это где-то.

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

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

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

2
12.12.2008 21:52:37

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

Теперь, если вы знаете теорию, вам не нужно переосмысливать все это. Вы просто говорите: «кусок пирога, это просто конечный автомат» и продолжаете его реализовывать.

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

6
12.12.2008 21:58:01
Мне особенно нравится последнее предложение.
Mike Dunlavey 12.12.2008 22:18:02

FSA - это отличные структуры данных для понимания, потому что при любой возможности их реализации вы работаете на самом низком уровне вычислительной сложности в иерархии Хомского. Отличным примером является морфология слов (как части слов объединяются). Была проделана большая работа, чтобы показать, что даже самые тяжелые случаи могут быть проанализированы в этой чрезвычайно быстрой аналитической структуре. Взгляните на работу Карттуннена и Бизли из PARC.

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

1
12.12.2008 22:00:20

Хорошие ответы выше. Я бы только добавил, что FSA - это прежде всего инструмент мышления , а не методика программирования. Что делает их полезными, так это то, что они обладают хорошими свойствами, и все, что действует как один, обладает этими свойствами. Если вы можете думать о чем-то как о FSA, есть много способов сделать это:

  • как регулярное выражение

  • в качестве таблицы перехода состояний

  • как цикл при включенном состоянии

  • как goto-net (ужасы!)

  • как простой структурированный программный код

и т. д.

Если кто-то говорит, что что-то является FSA, вы можете сразу узнать, о чем они говорят, независимо от того, как оно построено.

2
12.12.2008 22:01:14

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

1
12.12.2008 22:02:02

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

Если вы «визуальный» ученик, вот отличная ссылка, которая дает очень доступное введение.

Реаниматор Оливер Стил

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

(Примечание: ссылка указывает на обсуждение DFA и NDFA в контексте регулярных выражений - с анимированными интерактивными диаграммами)

2
24.04.2017 17:49:08

FSA (включая DFA и NFA) очень важны для информатики и используются во многих областях, включая многие области. Например, скрытые поля markov для распознавания речи, а также регулярные выражения преобразуются в FSA, прежде чем они интерпретируются программным обеспечением и NLP (обработка естественного языка), AI (программирование игр), программированием роботов и т. Д.

Одним из недостатков FSA является то, что они, как правило, медленны и, как правило, трудны для реализации и трудны для понимания или визуализации при чтении кода, но они хороши тем, что обычно предоставляют общие решения проблем, и они хорошо известны с большим количеством исследования по FSA.

1
3.01.2009 18:55:44