Использует для государственных машин

Ответ 1

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

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

Почему я должен использовать конечный автомат?

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

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

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

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 для простоты. На практике a case часто "проваливается" в следующее состояние.

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

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

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

Ответ 2

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

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

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

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

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

Ответ 3

Какая задача?

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

Почему?

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

Как?

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

Я видел это с помощью операторов 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

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

Ответ 4

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

Ответ 5

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

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

Ответ 6

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

Ответ 7

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

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

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

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

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

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

хороший пакет: 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

    }
}

Ответ 8

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

Ответ 9

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

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

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

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

Ответ 10

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

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

Ответ 11

Многие цифровые аппаратные средства предусматривают создание состояний машин для определения поведения ваших схем. Это приносит довольно много, если вы пишете VHDL.

Ответ 12

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

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

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

Ответ 13

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

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

Ответ 14

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

Ответ 15

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

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

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

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

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

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

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

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

Ответ 16

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

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

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

• Явные машины состояний, такие как те, которые генерируются средствами генерации парсеров, такие как Lex и Yacc.

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

Ответ 17

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

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

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

Ответ 18

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

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