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

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

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

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

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

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

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

• Явные конечные автоматы, такие как сгенерированные генерирующимися инструментами синтаксического анализатора такой как Lex и Yacc.

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

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

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

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

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

, Если Вы интересуетесь узнаванием больше, можно проверить Морфология Конечного состояния Бисли и Karttunen и Инструментарием Конечного состояния ксерокса, который они разработали в PARC.

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

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

, Например, если у Вас есть Запрос HTTP со многими состояниями, у Вас мог бы быть серверный код, который похож на это:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

хороший packet:FA0712345678EB Недопустимый синхронизирующий шаблон 0x12 Недопустимый синхронизирующий шаблон 0x34 Недопустимый синхронизирующий шаблон 0x56 ошибка Контрольной суммы 0xBF длина Недопустимого пакета 0 Недопустимых синхронизирующих шаблонов 0x12 Недопустимый синхронизирующий шаблон 0x34 Недопустимый синхронизирующий шаблон 0x56 Недопустимый синхронизирующий шаблон 0x78 Недопустимый синхронизирующий шаблон 0xEB хороший packet: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

    }
}

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

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

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

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

, Какой задача?

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

, Почему?

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

, Как?

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

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

я видел сделанный с маркировки и 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

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

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

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

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

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

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

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

Билет - управление процессами и системы организации технологических процессов - если Ваш билет имеет ряд правил, определяющий его перемещение между НОВЫМ, СОРТИРОВАННЫМ, ПРОИСХОДЯЩИМ, QA потребностей, неудавшимся QA и ПРОВЕРЕННЫЙ (например), у Вас есть простой конечный автомат.

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

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

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

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