3.4. Программная реализация конечных автоматов

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

Представление входных символов

В большинстве случаев текст, который будут обрабатывать на конечном автомате, находится в одной из стандартных кодировок: ASCII, ANSI или Unicode. Перед подачей на автомат текст необходимо перекодировать по следующим причинам.

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

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

2) другой вариант – буквы не менять. Входной алфавит будет включать и заглавные, и строчные буквы. Таблица переходов составляется таким образом, чтобы переход по большой и маленькой одноименной букве был одинаков. При этом варианте таблица переходов будет занимать больше места в памяти по сравнению с вариантом 1.

Вторая причина – недопустимые входные символы. Кодировки ASCII и ANSI состоят из 256 различных кодов, Unicode – из 65536. Входной алфавит конечного автомата обычно гораздо меньше. Если на вход автомата может попасть символ, который не известен автомату, для предотвращения неопределенной реакции автомата, можно:

1) перед подачей на автомат проверять на "допустимость" каждый символ текста; если найден символ, не входящий в автоматный алфавит, работа программы прекращается;

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

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

Представление состояний

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

• номер текущего состояния запоминается в специальной переменной (явный способ);

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

Выбор переходов

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

При явном способе наиболее эффективны два метода:

1. Метод вектора переходов. Этот метод выгодно применять там, где в большинстве состояний автомат выполняет какие-либо действия, причем различные ². Номер текущего состояния запоминается в специальной переменной. Каждому состоянию соответствует участок программы. Таблица переходов конечного автомата оформляется в программе в виде двумерного массива. Каждая строка массива соответствует номеру состояния, а столбец – входному символу алфавита. В элементах массива записываются адреса меток программы, соответствующих нужному состоянию.

1 Procedure encode( in A, out B ) // Подпрограмма перекодировки

2 switch( A ) of

3 'a' : B  0

4 'b' : B  1

5 'c' : B  2

6 else: B  3

7 end switch

8 return B

// Подпрограммы, представляющие состояния автомата:…

// …содержат действия, выполняемые автоматом в этом состоянии

9 Procedure state_0 // состояние 0 (действий нет)

10 s  0 // s – номер текущего состояния автомата

11 return

12 Procedure state_1 // состояние 1 (действий нет)

13 s  1

14 return

15 Procedure state_3 // состояние 3 (выходное)

16 s  3

17 print "Вхождение образца Р₁ со сдвигом" k–length[P₁]

18 return

… // остальные процедуры state_2, sate_4 … state_10 аналогично

главная программа:

// таблица векторов перехода, символ & означает взятие адреса

19 jump_vectors : array[0..9, 0..3]= (( &state_1, &state_0, &state_6),

( &state_2, &state_4, &state_6), и т.д. )

20 n  length[T] // Т – входной текст, n – его длина

21 call state_0 ;

22 for k  1 to n do

23 call encode( T[k], c ) // с – код символа после перекодировки

24 if c3

25 then call jump_vectors[ s, c ] // вызов процедуры по адресу

26 else call error

27 end for

Листинг 2. Алгоритм программной реализации конечного автомата из примера 2 методом векторов перехода.

В листинге 2 номер состояния автомата хранится в глобальной переменной s. Процедура encode перекодирует символы текста Т перед подачей на автомат: a0, b1, c2, прочие символы в код 3. При обнаружении “недопустимого” входного символа с кодом 3 автомат вызывает процедуру error.

2. Метод таблицы переходов. Этот метод применяется в автоматах, выполняющих однотипные действия в нескольких состояниях. От предыдущего метода отличается тем, что хранит в массиве номерá состояний. Каждая строка массива представляет состояние j, а столбец – входной символ алфавита. Номер следующего состояния выбирается по координатам (Номер_Текущего_Состояния, Код_Символа).

В листинге 3 приведен алгоритм работы конечного автомата из примера 2 методом таблицы переходов. Номер текущего состояния хранится в переменной s. Процедура encode перекодирует символы текста Т перед подачей на автомат: a0, b1, c2, прочие в код 3 (реализацию процедуры encode см. в листинге 2, строки 1–8) . Вводится новое состояние автомата с номером 10, в которое переходит автомат при поступлении “недопустимого” входного символа с кодом 3. Номера состояний переходов хранятся в таблице jump_table.

1 jump_table : array[0..10,0..3] = ((1,0,6,10), (2,4,6,10), (2,3,6,10), (1,0,5,10), (1,0,5,10),

(1,0,7,10), (1,0,7,10), (1,8,7,10),(9,0,6,10), (2,4,6,10), (1,0,6,10))

2 n  length[T] // Т – входной текст

3 s  0 // s – номер текущего состояния автомата

4 for k   1 to n do

5 call encode( T[k], c ) // с – код символа после перекодировки

6 s  jump_table[ s, c ]

// действия выполняются только в выходных состояниях 3,5,9,10

7 switch( s ) of

8 3: print "Вхождение образца Р₁ со сдвигом" k–length[P₁]

9 5: print "Вхождение образца Р₂ со сдвигом" k–length[P₂]

10 9: print "Вхождение образца Р₃ со сдвигом" k–length[P₃]

11 10: print "Недопустимый символ" T[k]

12 end switch

13 end for

Листинг 3. Алгоритм программной реализации конечного автомата

из примера 2 методом таблицы переходов