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

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

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

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

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

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

какие задачи?

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

почему?

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

Как?

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

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

Я видел, как это происходило с метки и goto заявления

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

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

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

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

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

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

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

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

вот проверенный и рабочий пример конечного автомата. Допустим, вы находитесь в последовательном потоке (типичные примеры-последовательный порт, данные 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

    }
}

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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