Я ищу хорошие примеры конечных автоматов; язык не особенно важен, просто хорошие примеры.

Реализации кода полезны (обобщенный псевдокод), но также очень полезно собирать различные варианты использования FSM.

Примеры не обязательно должны быть основаны на компьютере, например, пример Mike Dunlavey's Railroad network, очень полезен.

Сейф (событие вызвано)

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

Светофор (срабатывает время | срабатывает датчик [событие])

• Состояния : КРАСНЫЙ, ЖЕЛТЫЙ, ЗЕЛЕНЫЙ (простейший пример)
• Переходы : после таймера измените КРАСНЫЙ на ЗЕЛЕНЫЙ, ЗЕЛЕНЫЙ на ЖЕЛТЫЙ и ЖЕЛТЫЙ на КРАСНЫЙ. Может также запускаться при обнаружении автомобилей в различных (более сложных) состояниях.

Торговый автомат (событие сработало, вариант сейфа )

• Состояния : IDLE, 5_CENTS, 10_CENTS, 15_CENTS, 20_CENTS, 25_CENTS и т. Д., VEND, CHANGE
• Переходы : состояние изменяется при вставке монет, купюр, переходе к VEND при правильной сумме покупки (или более), затем переходе к CHANGE или IDLE (в зависимости от того, насколько этичен ваш торговый автомат)

Пример протокола пограничного шлюза

BGP - это протокол, который поддерживает основные решения по маршрутизации в Интернете. Он поддерживает таблицу для определения достижимости узлов данного узла и делает Интернет по-настоящему децентрализованным.

В сети каждый узел BGP является одноранговым и использует конечный автомат с одним из шести состояний Idle , Connect , Active , OpenSent , OpenConfirm и Established . Каждое одноранговое соединение в сети поддерживает одно из этих состояний.

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

Диаграмма состояний БПГ.

вхолостую

Первое состояние простаивает . В этом состоянии BGP инициализирует ресурсы, отклоняет попытки входящего соединения и инициирует соединение с партнером.

Connect

Второе состояние Connect . В этом состоянии маршрутизатор ожидает завершения соединения и в случае успеха переходит в состояние OpenSent . В случае неудачи он сбрасывает таймер ConnectRetry и переходит в активное состояние по истечении срока действия.

активный

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

OpenSent

В состоянии OpenSent маршрутизатор отправляет сообщение Open и ожидает его в ответ. Сообщения поддержки активности обмениваются, и после успешного получения маршрутизатор переводится в состояние « установлено» .

установленный

В установленном состоянии маршрутизатор может отправлять / получать: Keepalive; Обновить; и уведомляющие сообщения от / от своего партнера.

Больше информации о BGP в Википедии

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

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

Анализатор CSV, используемый в плагине jquery-csv

Это базовый синтаксический анализатор Chomsky Type III .

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

Токенизатор:

var tokenizer = /("|,|\n|\r|[^",\r\n]+)/;

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

Есть 10 правил, которым должен удовлетворять парсер:

• Правило № 1 - Одна запись в каждой строке, каждая строка заканчивается новой строкой
• Правило № 2 - завершающий символ новой строки в конце файла опущен
• Правило № 3 - Первая строка содержит данные заголовка
• Правило № 4 - пробелы считаются данными, а записи не должны содержать запятой
• Правило № 5 - Строки могут или не могут быть разделены двойными кавычками
• Правило № 6 - Поля, содержащие разрывы строк, двойные кавычки и запятые, должны быть заключены в двойные кавычки
• Правило № 7 - Если для заключения полей используются двойные кавычки, то двойная кавычка, появляющаяся внутри поля, должна быть экранирована, предшествуя другой двойной кавычкой
• Поправка № 1 - Поле без кавычек может или может
• Поправка № 2 - Цитируемое поле может или не может
• Поправка № 3 - Последнее поле в записи может содержать или не содержать нулевое значение

Примечание: 7 верхних правил получены непосредственно из IETF RFC 4180 . Последние 3 были добавлены для покрытия крайних случаев, представленных современными приложениями для работы с электронными таблицами (например, Excel, Google Spreadsheet), которые по умолчанию не разделяют (т.е. заключают в кавычки) все значения. Я попытался внести изменения в RFC, но пока не получил ответа на свой запрос.

Хватит заводить, вот схема:

Состояния:

1. начальное состояние для записи и / или значения
2. открыта цитата
3. вторая цитата была обнаружена
4. встречается значение без кавычек

Переходы:

• а. проверяет оба указанных значения (1), значения без кавычек (3), нулевые значения (0), нулевые записи (0) и новые записи (0)
• б. проверяет вторую цитату char (2)
• с. проверяет экранированную кавычку (1), конец значения (0) и конец записи (0)
• д. проверяет конец значения (0) и конец записи (0)

Примечание: на самом деле отсутствует состояние. Должна быть строка от 'c' -> 'b', помеченная состоянием '1', потому что экранированный второй разделитель означает, что первый разделитель все еще открыт. На самом деле, вероятно, было бы лучше представить его как еще один переход. Создание их - это искусство, единого правильного пути не существует.

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

Разница между состояниями и переходами:

Состояние является конечным, то есть оно может означать только одно.

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

По сути, отношение состояние-> переход - 1 -> * (то есть один ко многим). Состояние определяет «что это такое», а переход определяет «как оно обрабатывается».

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

Псевдокод:

csv = // csv input string

// init all state & data
state = 0
value = ""
entry = []
output = []

endOfValue() {
  entry.push(value)
  value = ""
}

endOfEntry() {
  endOfValue()
  output.push(entry)
  entry = []
}

tokenizer = /("|,|\n|\r|[^",\r\n]+)/gm

// using the match extension of string.replace. string.exec can also be used in a similar manner
csv.replace(tokenizer, function (match) {
  switch(state) {
    case 0:
      if(opening delimiter)
        state = 1
        break
      if(new-line)
        endOfEntry()
        state = 0
        break
      if(un-delimited data)
        value += match
        state = 3
        break
    case 1:
      if(second delimiter encountered)
        state = 2
        break
      if(non-control char data)
        value += match
        state = 1
        break
    case 2:
      if(escaped delimiter)
        state = 1
        break
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
    case 3:
      if(separator)
        endOfValue()
        state = 0
        break
      if(newline)
        endOfEntry()
        state = 0
        break
  }
}

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

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

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

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

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

Простой FSM на Java

int i=0;

while (i<5) {
 switch(i) {
   case 0:
     System.out.println("State 0");
     i=1;
     break;
   case 1:
     System.out.println("State 1");
     i=6;
     break;
   default:
     System.out.println("Error - should not get here");
     break;      
  }

} 

Вот и ты. Хорошо, это не блестяще, но это показывает идею.

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

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

Состояния, например, находятся на первом этаже, на первом этаже и т. Д. И перемещаются с первого на второй этаж или с третьего на первый этаж, но в настоящее время находятся между этажами 3 и 2 и т. Д.

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

На каждом этаже, кроме верхнего и нижнего, будут две кнопки: одна для запроса подъема, другая для спуска.

Хорошо, вот пример. Предположим, вы хотите разобрать целое число. Было бы что-то вроде dd*где dцелая цифра.

state0:
    if (!isdigit(*p)) goto error;
    p++;
    goto state1;
state1:
    if (!isdigit(*p)) goto success;
    p++;
    goto state1;

Конечно, как сказал @Gary, вы можете замаскировать их gotoс помощью оператора switch и переменной состояния. Обратите внимание, что это может быть структурировано в этот код, который изоморфен исходному регулярному выражению:

if (isdigit(*p)){
    p++;
    while(isdigit(*p)){
        p++;
    }
    // success
}
else {
    // error
}

Конечно, вы также можете сделать это с помощью справочной таблицы.

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

Пример железнодорожной сети

Одним из примеров FSM является сеть железных дорог.

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

Существует конечное количество дорожек, соединяющих эти переключатели.

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

Конечный автомат в Ruby:

module Dec_Acts
 def do_next
    @now = @next
    case @now
    when :invite
      choose_round_partner
      @next = :wait
    when :listen
      @next = :respond
    when :respond
      evaluate_invites
      @next = :update_in
    when :wait
      @next = :update_out
    when :update_in, :update_out
      update_edges
      clear_invites
      @next = :exchange
    when :exchange
      update_colors
      clear_invites
      @next = :choose
    when :choose
      reset_variables
      choose_role
    when :done
      @next = :done
    end
  end
end

Это поведение отдельного вычислительного узла в распределенной системе, устанавливающего схему связи на основе канала. Более менее. В графической форме это выглядит примерно так:

Проверьте эту ссылку для некоторых простых примеров лексического анализа (FSM):

http://ironbark.bendigo.latrobe.edu.au/subjects/SS/clect/clect03.html

Вы также можете проверить "книгу драконов" для примеров (это не легкое чтение)

http://en.wikipedia.org/wiki/Compilers:_Principles,_Techniques,_and_Tools

На практике государственные машины часто используются для:

• Цели проектирования (моделирование различных действий в программе)
• Парсеры естественного языка (грамматики)
• Разбор строки

Одним из примеров может быть конечный автомат, который сканирует строку, чтобы увидеть, имеет ли он правильный синтаксис. Например, голландские почтовые индексы имеют формат «1234 AB». Первая часть может содержать только цифры, вторая - только буквы. Может быть написан конечный автомат, который отслеживает, находится ли он в состоянии NUMBER или в состоянии LETTER, и если он обнаруживает неправильный ввод, отклоните его.

Этот конечный автомат принимает два состояния: числовое и альфа. Конечный автомат запускается в числовом состоянии и начинает читать символы строки для проверки. Если в любом из состояний встречаются недопустимые символы, функция возвращает значение False, отклоняя ввод как недействительный.

Код Python:

import string

STATE_NUMERIC = 1
STATE_ALPHA = 2

CHAR_SPACE = " "

def validate_zipcode(s):
cur_state = STATE_NUMERIC

for char in s:
    if cur_state == STATE_NUMERIC:
        if char == CHAR_SPACE:
            cur_state = STATE_ALPHA
        elif char not in string.digits:
            return False
    elif cur_state == STATE_ALPHA:
        if char not in string.letters:
            return False
return True

zipcodes = [
    "3900 AB",
    "45D6 9A",
]

for zipcode in zipcodes:
    print zipcode, validate_zipcode(zipcode)

Источник: (конечно) государственные машины на практике