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

Question

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

---

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

Answer 1

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

Цитирование статьи Википедии :

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

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

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

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

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

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

Answer 2

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

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

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

Формально , FSA представляет собой алгебраическую структуру F = & lang; & Sigma ;, S, s ₀ , F, & delta; & rang; где & Sigma; - это входной алфавит , S - это набор состояний , s ₀ & isin; S является конкретным начальным состоянием , F & sube; S представляет собой набор принимающих состояний и & delta;: S & times; & Sigma; & Rarr; S - функция перехода состояния .

Answer 3

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

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

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

Answer 4

Важно: Если вы ученик в «визуальном» стиле, остановите все, что вы делаете, и перейдите по этой ссылке ... Прямо сейчас. Если вы «визуальный» ученик, вот отличная ссылка, которая дает очень доступное введение. Реаниматор Оливер Стил Похоже, вы уже одобрили ответ, но если вы цените "визуальное" знакомство с новыми понятиями, как это обычно бывает, вам действительно следует проверить ссылку. Это просто выдающееся. (Примечание: ссылка указывает на обсуждение DFA и NDFA в контексте регулярных выражений - с анимированными интерактивными диаграммами)

Answer 5

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

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

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

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

• как сеть (ужас!)

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

и т.д.. и т.д.

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

Answer 6

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

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

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

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

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

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

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

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

Answer 7

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

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

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

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

Answer 8

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

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

Answer 9

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

Answer 10

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

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