Использование для конечных автоматов

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

Если вы используете .NET, попробуйте Windows Workflow Foundation. С его помощью вы можете довольно быстро реализовать рабочий процесс конечного автомата.

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

Инфраструктура контроля качества, предназначенная для очистки экрана или иного выполнения тестируемого процесса. (Это моя конкретная область опыта; я создал структуру конечного автомата на Python для моего последнего работодателя с поддержкой передачи текущего состояния в стек и с использованием различных методов выбора обработчика состояния для использования во всех наших скребках экрана на основе TTY) . Концептуальная модель хорошо подходит, поскольку при работе с приложением TTY она проходит через ограниченное количество известных состояний и может быть возвращена в старые (подумайте об использовании вложенного меню). Это было выпущено (с разрешения указанного работодателя); используйте Базар, чтобы проверить http://web.dyfis.net/bzr/isg_state_machine_framework/, если вы хотите увидеть код.

Системы управления билетами, процессами и рабочими процессами - если ваш билет имеет набор правил, определяющих его движение между NEW, TRIAGED, IN-PROGRESS, NEEDS-QA, FAILED-QA и VERIFIED (например), у вас есть простой конечный автомат.

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

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

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

Шаблон проектирования Состояние - это объектно-ориентированный способ представления состояния объекта с помощью конечного автомата. Обычно это помогает снизить логическую сложность реализации этого объекта (вложенные if, много флагов и т. д.)

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

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

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

Если вам интересно узнать больше, вы можете ознакомиться с Конечная морфология состояния от Бисли и Карттунена, а также с Xerox Finite State Toolkit, разработанным в PARC.

Что за задача?

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

Почему?

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

Как?

Что ж, вы ограничены только своим воображением.

Я видел это с операторы case и циклы.

Я видел это с помощью операторов метки и goto

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

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

int a[10] = {some unsorted integers};

not_sorted_state:;
    z = -1;
    while (z < (sizeof(a) / sizeof(a[0]) - 1)
    {
        z = z + 1
        if (a[z] > a[z + 1])
        {
            // ASSERT The array is not in order
            swap(a[z], a[z + 1];        // make the array more sorted
            goto not_sorted_state;      // change state to sort the array
        }
    }
    // ASSERT the array is in order

Переменных состояния нет, но сам код представляет состояние

Регулярные выражения - еще один пример того, где в игру вступают конечные автоматы (или «конечные автоматы»).

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

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

Автомат используется везде, где у вас есть несколько состояний, и вам нужно перейти в другое состояние при воздействии стимула.

(оказывается, что это охватывает большинство проблем, по крайней мере, теоретически)

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

• Состояние определяет, какой бит кода фактически выполняется в данной точке (т.е. состояние неявно присутствует в фрагменте кода, который вы пишете). Парсеры с рекурсивным спуском - хороший пример этого типа кода.

• Состояние определяет, что делать в условном выражении, таком как оператор switch.

• Явные конечные автоматы, такие как генерируемые инструментами создания синтаксического анализатора, такими как Лекс и Yacc.

Не весь код, управляемый состоянием, используется для синтаксического анализа. Генератор общего конечного автомата - smc. Он вдыхает определение конечного автомата (на своем языке) и выводит код для конечного автомата на различных языках.

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

В каких областях программирования я бы использовал конечный автомат?

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

Зачем мне использовать конечный автомат?

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

Как я могу его реализовать?

Банальный пример:

enum states {      // Define the states in the state machine.
  NO_PIZZA,        // Exit state machine.
  COUNT_PEOPLE,    // Ask user for # of people.
  COUNT_SLICES,    // Ask user for # slices.
  SERVE_PIZZA,     // Validate and serve.
  EAT_PIZZA        // Task is complete.
} STATE;

STATE state = COUNT_PEOPLE;
int nPeople, nSlices, nSlicesPerPerson;

// Serve slices of pizza to people, so that each person gets
/// the same number of slices.   
while (state != NO_PIZZA)  {
   switch (state)  {
   case COUNT_PEOPLE:  
       if (promptForPeople(&nPeople))  // If input is valid..
           state = COUNT_SLICES;       // .. go to next state..
       break;                          // .. else remain in this state.
   case COUNT_SLICES:  
       if (promptForSlices(&nSlices))
          state = SERVE_PIZZA;
        break;
   case SERVE_PIZZA:
       if (nSlices % nPeople != 0)    // Can't divide the pizza evenly.
       {                             
           getMorePizzaOrFriends();   // Do something about it.
           state = COUNT_PEOPLE;      // Start over.
       }
       else
       {
           nSlicesPerPerson = nSlices/nPeople;
           state = EAT_PIZZA;
       }
       break;
   case EAT_PIZZA:
       // etc...
       state = NO_PIZZA;  // Exit the state machine.
       break;
   } // switch
} // while

Заметки:

• В примере для простоты используется switch() с явными состояниями case / break. На практике case часто «проваливается» в следующее состояние.

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

• Для компактности весь switch() можно заменить массивом указателей на функции. Каждое состояние воплощено функцией, возвращаемое значение которой является указателем на следующее состояние. Предупреждение: Это может упростить конечный автомат или сделать его полностью недостижимым, поэтому внимательно рассмотрите реализацию!

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

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

Рассмотрим следующий вызов метода:

very_long_text = "Bereshit bara Elohim et hashamayim ve'et ha'arets." …
word = "Elohim"
position = find_in_string(very_long_text, word)

Как бы вы реализовали find_in_string? Простой подход будет использовать вложенный цикл, примерно так:

for i in 0 … length(very_long_text) - length(word):
    found = true
    for j in 0 … length(word):
        if (very_long_text[i] != word[j]):
            found = false
            break
    if found: return i
return -1

Помимо того, что это неэффективно, это формирует государственную машину! Состояния здесь несколько скрыты; позвольте мне немного переписать код, чтобы сделать их более заметными:

state = 0
for i in 0 … length(very_long_text) - length(word):
    if very_long_text[i] == word[state]:
        state += 1
        if state == length(word) + 1: return i
    else:
        state = 0
return -1

Различные состояния здесь напрямую представляют все разные позиции в слове, которое мы ищем. Для каждого узла графа есть два перехода: если буквы совпадают, перейти к следующему состоянию; для каждого другого ввода (т.е. для каждой второй буквы в текущей позиции) вернуться к нулю.

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

Вот проверенный и работающий пример конечного автомата. Допустим, вы используете последовательный поток (типичные примеры - последовательный порт, данные TCP / IP или файл). В этом случае я ищу конкретную структуру пакета, которую можно разбить на три части: синхронизацию, длину и полезную нагрузку. У меня есть три состояния: одно бездействует, ожидает синхронизации, второе - у нас хорошая синхронизация, следующий байт должен быть длиной, а третье состояние - накопление полезной нагрузки.

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

Я использую этот вид конечного автомата постоянно, будь то потоки последовательных данных, TCP / IP, файловый ввод-вывод. Или, возможно, сами протоколы tcp / ip, скажем, вы хотите отправить электронное письмо, открыть порт, дождаться, пока сервер отправит ответ, отправить HELO, дождаться, пока сервер отправит пакет, отправить пакет, дождаться ответа, и т. д. По сути, в этом случае, а также в приведенном ниже случае вы можете простаивать, ожидая поступления следующего байта / пакета. Чтобы запомнить, чего вы ждали, также повторно используйте код, который ждет чего-то, что вы можете использовать переменные состояния. Точно так же, как конечные автоматы используются в логике (ожидание следующих часов, чего я ждал).

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

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

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

хороший пакет: FA0712345678EB Неверный шаблон синхронизации 0x12 Неверный шаблон синхронизации 0x34 Неверный шаблон синхронизации 0x56 Ошибка контрольной суммы 0xBF Неверная длина пакета 0 Неверный шаблон синхронизации 0x12 Неверный шаблон синхронизации 0x34 Неверный шаблон синхронизации 0x56 Неверный шаблон синхронизации 0x78 Неверный шаблон синхронизации 0xEB хороший пакет: FA081234567800EA больше нет тестовых данных

Два хороших пакета в потоке были извлечены, несмотря на плохие данные. И плохие данные были обнаружены и обработаны.

 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>

unsigned char testdata[] =
{
    0xFA,0x07,0x12,0x34,0x56,0x78,0xEB,  
    0x12,0x34,0x56,  
    0xFA,0x07,0x12,0x34,0x56,0x78,0xAA,  
    0xFA,0x00,0x12,0x34,0x56,0x78,0xEB,  
    0xFA,0x08,0x12,0x34,0x56,0x78,0x00,0xEA  
};

unsigned int testoff=0;

//packet structure  
// [0] packet header 0xFA  
// [1] bytes in packet (n)  
// [2] payload  
// ... payload  
// [n-1] checksum  
//  

unsigned int state;

unsigned int packlen;  
unsigned int packoff;  
unsigned char packet[256];  
unsigned int checksum;  

int process_packet( unsigned char *data, unsigned int len )  
{  
    unsigned int ra;  

    printf("good packet:");
    for(ra=0;ra<len;ra++) printf("%02X",data[ra]);
    printf("\n");
}  
int getbyte ( unsigned char *d )  
{  
    //check peripheral for a new byte  
    //or serialize a packet or file  

    if (testoff<sizeof(testdata))
    {
        *d=testdata[testoff++];
        return(1);
    }
    else
    {
        printf("no more test data\n");
        exit(0);
    }
    return(0);
}

int main ( void )  
{  
    unsigned char b;

    state=0; //idle

    while(1)
    {
        if (getbyte(&b))
        {
            switch(state)
            {
                case 0: //idle
                    if (b!=0xFA)
                    {
                        printf("Invalid sync pattern 0x%02X\n",b);
                        break;
                    }
                    packoff=0;
                    checksum=b;
                    packet[packoff++]=b;

                    state++;
                    break;
                case 1: //packet length
                    checksum+=b;
                    packet[packoff++]=b;

                    packlen=b;
                    if (packlen<3)
                    {
                        printf("Invalid packet length %u\n",packlen);
                        state=0;
                        break;
                    }

                    state++;
                    break;
                case 2: //payload
                    checksum+=b;
                    packet[packoff++]=b;

                    if (packoff>=packlen)
                    {
                        state=0;
                        checksum=checksum&0xFF;
                        if (checksum)
                        {
                            printf("Checksum error 0x%02X\n",checksum);
                        }
                        else
                        {
                            process_packet(packet,packlen);
                        }
                    }
                    break;
            }
        }

        //do other stuff, handle other devices/interfaces

    }
}

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

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

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

Show form 1
process form 1
show form 2
process form 2

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

Размещение прерывания в коде и возврат потока обычно выполняется с помощью оператора switch и создает то, что называется конечным автоматом (очень простая версия).

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

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

Хорошие ответы. Вот мои 2 цента. Конечные автоматы - это теоретическая идея, которая может быть реализована несколькими различными способами, такими как таблица или как переключатель while (но никому не говорите, что это способ сказать goto ужасы). Это теорема, что любой автомат соответствует регулярному выражению, и наоборот. Поскольку регулярное выражение соответствует структурированной программе, вы можете иногда просто написать структурированную программу для реализации вашего конечного автомата. Например, простой синтаксический анализатор чисел может быть записан в следующих строках:

/* implement dd*[.d*] */
if (isdigit(*p)){
    while(isdigit(*p)) p++;
    if (*p=='.'){
        p++;
        while(isdigit(*p)) p++;
    }
    /* got it! */
}

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

Типичный вариант использования - светофор.

Относительно реализации: перечисления Java 5 могут иметь абстрактные методы, что является отличным способом инкапсулировать поведение, зависящее от состояния.