Моделирование процесса производства с помощью конечных автоматов

Понятие конечные автоматы

Так что же из себя представляют КА Для начала посмотрим на то, какие функции они выполняют.

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

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

Некоторые из состояний являются выделенными – имеется одно начальное и несколько конечных. Подразумевается, что когда КА начал считывать буквы с ленты, он находился в начальном состоянии; если после считывания последней переданной ему буквы он оказался в одном из конечных – это «хорошо», если нет – «плохо».

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

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

Поскольку для любой последовательности символов (слов) КА может сказать, распознает ли он ее, то с каждым конечным автоматом сопоставляют распознаваемый им язык (совокупность всех слов, которые он распознает).

Теперь рассмотрим, как (почти) строго задать конечный автомат. Пусть имеется некоторое конечное множество Q, которое мы назовем множеством состояний (а его элементы – состояниями). Выберем из этого множества элемент q₀, который назовем начальным состоянием, а также подмножество F – множество конечных состояний.

Возьмем также некоторое конечное множество ∑, которое назовем алфавитом. На декартовом произведении Q*Σ зададим всюду определенную функцию δ, принимающую значения на множестве Q – функцию перехода. Пятерку (Q, ∑, δ, q0, F) называют полным детерминированным конечным автоматом (ПДКА).

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

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

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

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

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

Есть также другие типы КА, например, недетерминированный конечный автомат(НКА) иε-НКА( они оба эквивалентны ДКА), но здесь я их рассматривать не буду. Они оказываются удобны в некоторых задачах, но для рассмотрения вопроса о реализации менеджера игровых состояний лучше подходят детерминированные автоматы. Впрочем, в полной мере их будет недостаточно, и придется упомянуть также т.н. конечные автоматы с магазинной памятью, которые распознают более широкий класс языков, нежели ПДКА.

Пример конечного автомата

 

Конечный автомат можно пpедставить в виде таблицы

 

Здесь Состояние - состояние, в котоpом находится автомат в момент пpочитывания очеpедного символа, Символ - символ, котоpый считывает автомат.

На пеpесечении в клетке записано новое состояние, в котоpое должен пеpейти автомат, и действие, котоpое он должен выполнить --- обычно, это напечатать какой либо символ.

 

Напpимеp, надо pазобpать идентификатоp в тексте пpогpаммы:

id::= <бyква>{цифpа|бyква}

(начинается с бyквы, далее идет пpоизвольная смесь бyкв и цифp, оканчивается, если встpетился не бyквенноцифpовой символ).

 

Автомат бyдет пpимеpно такой:

 

 

Следyет заметить, что <бyква>, <цифpа> и <дpyгое> - это в общем слyчае не одна ячейка, а много (т.е. вместо надо подставить a,b,c,d,e... и т.д., вместо <цифpа> -- 1,2,3,4,5,6,7,8,9,0, вместо <дpyгое> - все остальное).

 

Пpогpаммиpyется это довольно легко. В общем слyчае:

/* опpеделяем константы обозначающие состояния */

#define STATE_1 1

#define STATE_2 2

....

#define STATE_N N

 

int state; /* здесь хpанится наше текyщее состояние */

char symbol; /* это символ, котоpый мы считали */

..

main() {

FILE * input;

..

input = fopen("Input_file");

/* основной алгоpитм pазбоpа */

while(! feof(input)) {

c = fgetc(input);

switch (state) { /* выбиpаем нyжнyю колонкy Состояния */

case STATE_1:

switch(c) { /* выбиpаем нyжнyю стpокy Символ */

case 'a':

do_some_action(); /* выполняем действие, записанное в

клетке таблицы */

state = STATE_2; /* пеpеходим в новое состояние */

break;

case 'b':

...

} /* end switch */

case STATE_2:

...

} /* end switch */

} /* end while */

fclose(input);

..

} /* end main */

 

Моделирование процесса производства с помощью конечных автоматов

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

В итоге получаем следующую модель. Стадии готовности товара — состояния конечного автомата. Процесс обработки заготовки (переход от одной стадии готовности в другую) – переход конечного автомата. Каждый моделируемый экономический агент использует свой конечный автомат для производства. Помимо агентов в модельном экономическом мире существует рынок – место, где агенты покупают и продают ресурсы. Агенты взаимодействуют посредствам рынка. Более подробное описание можно найти в работе

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

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

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

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