О конечных автоматах

Время от времени нетвердыми умом "программистами" поднимается вопрос о программировании конечных автоматов. Хотелось бы, конечно, сразу отсылать к дебилизмам, но, к сожалению, к FORTH этот вопрос никак не относится...
Чего же не понимают люди раз за разом предлагающие "красивые реализации автоматов"?
1. Языки программирования сами по себе являются практической реализацией Теории конечных автоматов и любой конечный автомат легко "компилируется" в конструкции нормального языка программирования.
2. В Теории конечных автоматов самое интересное не "кружочки и стрелочки", а математика, связанная с преобразованием одного автомата в другой.

ИЗБЫТОЧНОСТЬ УПРАВЛЕНИЯ

Мы так привыкли к потомкам ALGOL 60, что воспринимаем как должное возможность записать один и тот же алгоритм многими способами. Но всегда ли это полезно? Рассмотрим простейший пример:

ПРОГРАММА:
- ДЕЙСТВИЕ-1;
- ЦИКЛ-ПО-I
- - ДЕЙСТВИЕ-2(I);
- ДЕЙСТВИЕ-3;

Допустим, наши ДЕЙСТВИЯ получились достаточно сложными, и нам захотелось разбить ПРОГРАММУ на части:

Вариант 1:

ПРОГРАММА:
- ДЕЙСТВИЕ-1;
- ЦИКЛ-ПО-I
- - ПРОЦЕДУРА-1(I);
- ДЕЙСТВИЕ-3;

ПРОЦЕДУРА-1(I):
- ДЕЙСТВИЕ-2(I);

Вариант 2:

ПРОГРАММА:
- ДЕЙСТВИЕ-1;
- ПРОЦЕДУРА-2;
- ДЕЙСТВИЕ-3;

ПРОЦЕДУРА-2:
- ЦИКЛ-ПО-I
- - ДЕЙСТВИЕ-2(I);

Казалось бы, какая разница?
Во-первых, может оказаться что был выбран Вариант 2, а в других местах программы понадобится ПРОЦЕДУРА-1. Переразбивать?
Во-вторых, когда таких "вложений" в ПРОГРАММЕ много, программист разбивает их то так, то этак, и результирующий код становится исключительно неопрятным (хотя и совершенно структурированным). Сам черт ногу сломит в попытках выяснить, в области видимости которой из I мы находимся в данной точке.
Для переразбития программ в целях достижения большей удобоваримости даже термин специальный придумали - "РЕФАКТОРИНГ".
***

Можно ли как-то избавится от управления, "размазанного" по всему коду, и сосредоточить его (управление) в каком-либо определенном месте? Написать его на каком-то специальном "управленческом" языке, обособить от обычных вычислений?
Ответ дает тот же Мур: пишем простой Цикл Управления и обрабатываем остальное как ввод, после выполнения каждого действия возвращаясь в цикл для выбора следующего.
По-сути, предлагается обычный конечный автомат, занимающийся "чистым управлением" действиями, до которых ему совершенно нет дела.

КАК ЭТО РАБОТАЕТ

Построю такой автомат для решения простой задачи.
Задача, предложенная на кошачьем около-Форт-форуме, состоит в распознавании чисел, вводимых пользователем в формате ГРАДУСОВ*МИНУТ'СЕКУНД" (я заменил нелюбимый мной символ "градус" на звездочку, чтобы не мучиться с набиванием) и переводе их в общее число секунд (зачем это понадобилось, мне неведомо). Решение, предложенное на форуме на псевдокоде выглядит так:

СЕКУНДЫ = 0
СЕКУНДЫ' = ВВОД-ЧИСЛА
IF ВВЕЛОСЬ
- CASE СЛЕДУЮЩИЙ-СИМВОЛ
- * : СЕКУНДЫ += СЕКУНДЫ' * 3600
- - СЕКУНДЫ' = ВВОД-ЧИСЛА
- - IF ВВЕЛОСЬ
- - - CASE СЛЕДУЮЩИЙ-СИМВОЛ
- - - ' : СЕКУНДЫ += СЕКУНДЫ' * 60
- - - СЕКУНДЫ' = ВВОД-ЧИСЛА
- - - IF ВВЕЛОСЬ
- - - - IF СЛЕДУЮЩИЙ-СИМВОЛ = "
- - - - - СЕКУНДЫ += СЕКУНДЫ'
- - - - ELSE
- - - - - ОШИБКА
- - - " : СЕКУНДЫ += СЕКУНДЫ'
- - - - ДРУГОЙ : ОШИБКА
- ' : СЕКУНДЫ += СЕКУНДЫ' * 60
- - СЕКУНДЫ' = ВВОД-ЧИСЛА
- - IF ВВЕЛОСЬ
- - - IF СЛЕДУЮЩИЙ-СИМВОЛ = "
- - - - СЕКУНДЫ += СЕКУНДЫ'
- - - ELSE
- - - - ОШИБКА
- " : СЕКУНДЫ += СЕКУНДЫ'
- ДРУГОЙ : ОШИБКА
ELSE
- ОШИБКА

Если вы думаете, что это опрятнее выглядит на Форт (разбитое на слова ВВОД-ЧИСЛА, ГРАДУСОВ, МИНУТ, СЕКУНД и упрятыванием СЕКУНДЫ и СЕКУНДЫ' в стек), вы глубоко ошибаетесь. Помните, как в таких случаях громко ругался Броуди?
***

Как из этого сделать конечный автомат? Взять и сделать! В скобках номера состояний, СИМВОЛ->(СОСТОЯНИЕ)[ДЕЙСТВИЕ] обозначает: получив СИМВОЛ, выполни ДЕЙСТВИЕ и перейди к СОСТОЯНИЮ, ввод неожиданного СИМВОЛА - ОШИБКА.

(СТАРТ)
ЧИСЛО->(1)[СЕКУНДЫ' = ЧИСЛО]

(1)
*->(2)[СЕКУНДЫ += СЕКУНДЫ' * 3600]
'->(4)[СЕКУНДЫ += СЕКУНДЫ' * 60]
"->(6)[СЕКУНДЫ += СЕКУНДЫ']

(2)
ЧИСЛО->(3)[СЕКУНДЫ' = ЧИСЛО]
ПРОБЕЛ->КОНЕЦ

(3)
'->(4)[СЕКУНДЫ += СЕКУНДЫ' * 60]
"->(6)[СЕКУНДЫ += СЕКУНДЫ']

(4)
ЧИСЛО->(5)[СЕКУНДЫ' = ЧИСЛО]
ПРОБЕЛ->КОНЕЦ

(5)
"->(6)[СЕКУНДЫ += СЕКУНДЫ']

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

(СТАРТ)
ЧИСЛО->(1)[СЕКУНДЫ' = ЧИСЛО]

(1)
*->(2)[СЕКУНДЫ += СЕКУНДЫ' * 3600]
ДРУГОЙ->(3)

(2)
ЧИСЛО->(3)[СЕКУНДЫ' = ЧИСЛО]

(3)
'->(4)[СЕКУНДЫ += СЕКУНДЫ' * 60]
ДРУГОЙ->(5)

(4)
ЧИСЛО->(5)[СЕКУНДЫ' = ЧИСЛО]

(5)
"->(6)[СЕКУНДЫ += СЕКУНДЫ']

Не правда ли, так лучше? Только надо следить, чтобы КОНЕЦ с ОШИБКОЙ не перепутались.
***

Да, но, где-то за скобками маячат страшные типовые операции конечного автомата... Да полно вам, не такие уж они и страшные. Я даже их уже описывал в FOBOS. Одно разнесчастное слово RECEPTING:

Алгоритм О. УНИВЕРСАЛЬНЫЙ ОБРАБОТЧИК ...
О1. [Защелка.] Если КОД равен ЭТАЛОНУ, перейти к шагу 2, иначе - к 5.
О2. [Лист?] Если обработчик конечный, перейти к шагу 3, иначе - к шагу 4.
О3. [Вернуть результат.] Выполнить обработчик, вернуть его результат. Закончить работу.
О4. [Подобработчик.] Получить новый КОД. Безвозвратно перейти к обработчику-СЫНУ.
О5. [Следующий?] Если обработчика-БРАТА нет - перейти к шагу 3, иначе - к 6.
O6. [Переход.] Безвозвратно перейти к обработчику-БРАТУ. []

Сам же автомат описывается простейшим шитым кодом (странно, да)?

ЭТАЛОН БРАТ СЫН ДЕЙСТВИЕ...

Т.е. в нашем случае (начальный ввод выносим за скобки; символ 9 возвращается при успешном считывании числа):

( СТ) 9 ОШ 1 CЛЕДУЮЩИЙ-СИМВОЛ
( 1) * 3 2 OK! СЕКУНДЫ' 3600 * СЕКУНДЫ +! ВВОД-ЧИСЛА ( помните, он заполняет СЕКУНДЫ' ?)
( 2) 9 КЦ 3 CЛЕДУЮЩИЙ-СИМВОЛ
( 3) ' 5 4 OK! СЕКУНДЫ' 60 * СЕКУНДЫ +! ВВОД-ЧИСЛА
( 4) 9 КЦ 5 CЛЕДУЮЩИЙ-СИМВОЛ
( 5) " ОШ 0 СЕКУНДЫ' СЕКУНДЫ +! КОНЕЦ
( КЦ) ПРОБЕЛ ОШ 0 OK? IF КОНЕЦ ELSE ОШИБКА THEN
( ОШ) 0 0 0 ОШИБКА

РЕАЛИЗАЦИЯ

Как я понял, многие фортеры страдают жуткой непереносимостью псевдокода. Наверное, это гипертрофированная ревность к своей версии FORTH.
Специально для них - макет конечного автомата для данной задачи. Почему макет? Потому, что механизм RECEPTING и чтения строки, очевидно, имеет смысл писать на языке ассемблера (не то чтобы быстрее, но банально проще) и вставлять в то место, где они нужнее FORTH-системе. Не писать же все это ради одних несчастных "градусов"! Да и большинство использованных переменных, на самом деле, удобнее спрятать в стеке. Я им присвоил имена для наглядности. Код проверялся на Win32FORTH.
***

СЛОВА РЕЦЕПТИРОВАНИЯ:

: RECEPTOR  ( <WORD> KEY,BROTHER,SON -- ...)
CREATE ROT , SWAP , ,  ] ;
: BROTHER   CELL + ;
: SON CELL 2* + ;
: DOES CELL 3 * + ;
VARIABLE RETURN
: RECEPTING  ( SYM,S -- ...)
BEGIN DUP BROTHER @ IF \ А ЕСТЬ ЛИ ЕЩЕ ВАРИАНТЫ? (O5)
2DUP @ - ELSE 0 THEN WHILE \ ПОДХОДИТ ЭТОТ? (O1)
BROTHER @ REPEAT NIP \ НАШЛИ ПОДХОДЯЩИЙ УЗЕЛ (O3)
DUP SON @ ?DUP IF \ БУДЕМ ВОЗВРАЩАТЬСЯ К СЫНУ? (O2)
SWAP RETURN @ >R THEN \ ПРЯЧЕМ СЫНА И ДОСТАЕМ ВОЗВРАТ (O4)
DOES >R EXIT \ ЗАПУСКАЕМ ДЕЙСТВИЕ (O3, O4)
[ HERE RETURN ! ] \ СЮДА НАДЕЕМСЯ ВЕРНУТЬСЯ (O4)
SWAP RECURSE ; \ ДОСТАЕМ СЫНА (O4)
\ ДЕЙСТВИЕ УЗЛА: S -- S, SYM
\ ДЕЙСТВИЕ КОНЕЧНОГО: -- ...

Видно, что буквального следования алгоритму УНИВЕРСАЛЬНОГО ОБРАБОТЧИКА не наблюдается. Издержки высокоуровнего программирования... Зато, по функционалу соответствует.
***

СЛОВА РАБОТЫ СО СТРОКОЙ:

ASCII E CONSTANT E \ ДОСТИГНУТ КОНЕЦ ЛЕКСЕМЫ
ASCII 9 CONSTANT D \ СЧИТАНО ЧИСЛО
ASCII X CONSTANT X \ ЗАВЕДОМАЯ ОШИБКА
VARIABLE STR
VARIABLE #STR
: GET-NUM ( -- SYM,U)
0 0 STR @ #STR @ >NUMBER ( UD2,CA2,U2)
#STR @ OVER = IF \ НИЧЕГО НЕ СЧИТАЛОСЬ?
>R DROP 2DROP R>
IF X ELSE E THEN 0 ELSE \ КОНЕЦ?
#STR ! STR ! DROP D SWAP THEN ;   \ CЧИТАЛОСЬ
: NEXT-SYM ( -- S)
#STR @ 0= IF E ELSE
-1 #STR +!
STR @ DUP 1+ STR ! C@ THEN ;

Кодовые аналоги этих слов я использовал в NUMBER .
***

СЛОВА ОКРУЖЕНИЯ ГРАДУСОВ:

ASCII g CONSTANT G
ASCII m CONSTANT M
ASCII s CONSTANT S
VARIABLE SEC
VARIABLE SEC'
VARIABLE OK?
: ERROR CR ." НЕ ПОЛУЧИЛОСЬ" CR ;
: DONE CR ." ПОЛУЧИЛОСЬ = " SEC @ DUP 3600 / . 3600 MOD DUP 60 / . 60 MOD . CR ;
: PREPARE  ( CA,U)
#STR ! STR ! 0 SEC ! 0 OK? ! ;

Тут я заменил окружение задачи с форума на что-то более наглядное.
***

САМ ГРАДУС:

\ SYM BR. SON S DOES
0 0 0 RECEPTOR ERR ERROR ;
E ERR 0 RECEPTOR END OK? @ IF DONE ELSE ERROR THEN ;
S ERR 0 RECEPTOR S5 SEC' @ SEC +! DONE ;
D END S5 RECEPTOR S4 NEXT-SYM ;
M S5 S4 RECEPTOR S3 -1 OK? ! SEC' @ 60 * SEC +! GET-NUM SEC' ! ;
D END S3 RECEPTOR S2 NEXT-SYM ;
G S3 S2 RECEPTOR S1 -1 OK? ! SEC' @ 3600 * SEC +! GET-NUM SEC' ! ;
D ERR S1 RECEPTOR ST NEXT-SYM ;
: GO ( CA,U) CR PREPARE GET-NUM SEC' ! ST RECEPTING CR ;
\ ПРИМЕР ИСПОЛЬЗОВАНИЯ: S" 12g12m12s" GO

Вот эти 9 строчек заменяют все эти CASE, с которых мы начали решать задачу. Насколько это читабельно - судить вам. Конечно, если автомат сложен, то без бумажки для рисования кружочков и стрелочек не обойтись. Из плюсов данного подхода можно упомянуть легкость его модификации. Нетрудно, например, добавить отрицательные углы, проверку углов на нормированность, довески типа "С.Ш." (северной широты)...

САМОЕ ГЛАВНОЕ

Конечно, заставлять от понятных IF-ов переходить к какому-то там шитому коду страшно. Да и область применимости конечных автоматов вовсе не такая уж всеохватывающая. Они естественно применяются обычно там, где вводимая строка описывается т.н. регулярным выражением. В нашем случае:

[0-9]+\*([0-9]+\')?([0-9]+\")?|[0-9]+\'([0-9]+\")?|[0-9]+\"

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

У меня в FOBOS конечные автоматы работают на распознании чисел (в NUMBER им самое место) и командной строки (а еще при распознании WIN-сообщений).
***

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

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

ПОСТРОЕНИЕ НКА

Сначала надо перевести регулярное выражение в канонический вид. Разновидностей не счесть, поэтому процесс может отличаться значительно. В каноническом представлении допускаются только три операции (в порядке уменьшения приоритета): * (0 и более раз), конкатенация, + (или). Допускается заключение в скобки. Обратите внимание, что "плюс", который мы в нашем регулярном выражении понимали как "1 и более раз", с каноническим представлением никак не связан.

Наше выражение	Каноническая форма
[0-9]	0+1+2+3+4+5+6+7+8+9
<выражение>+	<выражение><выражение>*
<выражение>?	<выражение>+<пусто>
<выражение1>|<выражение2>	<выражение1>+<выражение2>

Прямая подстановка даст, очевидно слишком длинное выражение, поэтому мы воспользуемся замечательным свойством регулярных выражений: Они могут "вкладываться" друг в друга, и то, что для части - регулярное выражение, для общего - лишь символ. Нам удобно считать "одним символом" [0-9]+, т.е. в каноническом виде (0+1+2+3+4+5+6+7+8+9)(0+1+2+3+4+5+6+7+8+9)*. Обозначим его D. Заменю (как в коде) все эти градусы-кавычки на символы G, M, S, чтобы не возникало двусмысленности. Тогда имеем: DG(DM+e)(DS+e)+DM(DS+e)+DS, где е - пустой символ.
***

Теперь из канонического выражения делаем НКА. Пусть r и s - регулярные выражения, а R и S - допускающие их НКА. Тогда:

Регулярное выражение	Конечный автомат
r*	добавляем два новых узла R1 (стартовый) и R2 (конечный), от R1 рисуем стрелки (помеченные пустым символом, в этой таблице другие не понадобятся) на вход R и к R2, от выхода R - к его входу и к R2. Т.е. замыкаем R в кольцо и добавляем обходной путь
r+s	опять добавляем стартовый R1 и конечный R2, от R1 - стрелки ко входам R и S, от их выходов - к R2. Автоматы соединены параллельно
rs	просто соединяем выход R со входом S. Последовательно

Из DG(DM+e)(DS+e)+DM(DS+e)+DS мы тогда получим:

# узла	символ	# конечного узла	примечание
1	e	2	для альтернативы DG(DM+)(DS+)
1	e	3	для альтернативы DM(DS+)
1	e	4	для альтернативы DS
2	D	5	идем по пути D.G(DM+)(DS+)
5	G	6	идем по пути DG.(DM+)(DS+)
6	e	7	идем по пути DG.DM(DS+)
6	e	8	обходим DM - DG.(DS+)
7	D	9	идем по пути DGD.M(DS+)
9	M	10	идем по пути DGDM.(DS+)
10	e	8	слияние путей DGDM.(DS+) и DG.(DS+)
8	e	11	идем по пути DG(DM+).DS
8	e	12	обходим DS - DG(DM+).
11	D	13	идем по пути DG(DM+)D.S
13	S	14	идем по пути DG(DM+)DS.
14	e	12	слияние путей DG(DM+)DS. и DG(DM+).
3	D	15	идем по пути D.M(DS+)
15	M	16	идем по пути DM.(DS+)
16	e	17	идем по пути DM.DS
16	e	18	обходим DS - DM.
17	D	19	идем по пути DMD.S
19	S	20	идем по пути DMDS.
20	e	18	слияние путей DMDS. и DM.
4	D	21	идем по пути D.S
21	S	22	идем по пути DS.
12	e	23	финальное слияние путей
18	e	23	финальное слияние путей
22	e	23	финальное слияние путей
23	E	24	конец должен быть явно обозначен

Нет, пусть этим занимается сама машина!

ПОЛУЧЕНИЕ ДКА ИЗ НКА

Алгоритм (по А.Ахо, Дж.Хопкрофт, Дж.Ульман "Построение и анализ вычислительных алгоритмов"):

Сначала строим граф-замыкание (рефлексивное и транзитивное) нашего НКА по стрелкам, помеченным пустым символом:

# узла	# узлов, достижимых по стрелкам, помеченных пустым символом
1	1, 2, 3, 4
2	2
3	3
4	4
5	5
6	6, 7, 8, 11, 12, 23
7	7
8	8, 11, 12, 23
9	9
10	8, 10, 11, 12, 23
11	11
12	12, 23
13	13
14	12, 14, 23
15	15
16	16, 17, 18, 23
17	17
18	18, 23
19	19
20	18, 20, 23
21	21
22	22, 23
23	23
24	24

***

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

1. Его узлы: стартовый узел нашего НКА и все узлы, достижимые из узлов НКА по стрелкам, не помеченных пустым символом.
У нас получается: 1, 5, 6, 9, 10, 13, 14, 15, 16, 19, 20, 21, 22, 24.

2. Стрелки НКА': от каждого узла НКА' ко всем узлам достижимым по стрелкам, не помеченным пустым символом, из всех узлов, которые входят в замыкание для этого узла.

1	D->5, D->15, D->21
5	G->6
6	D->9, D->13, E->24
9	M->10
10	D->13, E->24
13	S->14
14	E->24
15	M->16
16	D->19, E->24
19	S->20
20	E->24
21	S->22
22	E->24
24	-

3. Конечными узлами НКА' будут все узлы, в замыкание которых входят конечные узлы НКА.
У нас как было, так и осталось: 24. Вот если, бы мы не включили стрелку от 23 E->24, то финальных стало бы намного больше: 6, 10, 14, 16, 20, 22.
***

Теперь самое хитрое, момент, когда с таким трудом подсократившееся количество состояний может вырасти экспоненциально! Строим ДКА.

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

#узла	D	G	M	S	E
1	5-15-21	0	0	0	0
5-15-21	0	6	16	22	0
6	9-13	0	0	0	24
9-13	0	0	10	14	0
10	13	0	0	0	24
13	0	0	0	14	0
14	0	0	0	0	24
16	19	0	0	0	24
19	0	0	0	20	0
20	0	0	0	0	24
22	0	0	0	0	24
24	0	0	0	0	0
0	0	0	0	0	0

2. Конечными состояниями будут все, помеченные подмножествами, в которое входят конечные состояния НКА'.
Наше вечное 24...
***

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

А ЕСЛИ, ДЕЙСТВИТЕЛЬНО, ЭКСПОНЕНЦИАЛЬНО?

Если вы (обоснованно) подозреваете, что при переходе от НКА' к ДКА размер автомата перестанет быть обозримым, то на построении НКА можно и остановиться. Причем, не надо даже удалять стрелки, помеченные пустыми символами, и никоим образом не оптимизировать, даже, как это делал я (объединив три альтернативы в одну развилку: 1->2,3,4). Наоборот, доказательство быстродействия приведенной программы базируется на том, что из одного узла выходит не более двух стрелок! Т.е. строить НКА надо строго по инструкции.
Моделирование НКА не такая уж трудоемкая вещь. Вот алгоритм от Ахо и компании. Нахождение множества состояний Sn, достижимых НКА после чтения цепочки a1a2...an. s0 - стартовое состояние.

for i := 0 until n do
- begin
- - if i = 0 then Si := {s0}
- - else Si := все узлы, достижимые по стрелке из Si-1;
- - пометить каждое состояние в Si как "рассмотренное";
- - пометить остальные состояния как "нерассмотренные";
- - ОЧЕРЕДЬ := Si;
- - while ОЧЕРЕДЬ не пуста do
- - - begin
- - - - найти и удалить из ОЧЕРЕДИ первый элемент t;
- - - - for все u достижимые из t по стрелке, помеченной пустым символом do
- - - - - if u "нерассмотренное" then
- - - - - - begin
- - - - - - - пометить u как "рассмотренное";
- - - - - - - добавить u в ОЧЕРЕДЬ и в Si
- - - - - - end
- - - end
- end

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