5.1. Основные понятия, определения и алгоритмы

Определение 1. Под конечным автоматом будем понимать математическую модель вычислительного устройства с фиксированным и конечным объемом памяти, которое «читает» последовательность входных символов из некоторого конечного множества.

Определение 2. Конечные автоматы, определяющие допустима или недопустима данная последовательность символов, называются конечными распознавателями. Конечный распознаватель задается следующим образом:

1. На вход конечного распознавателя подается цепочка символов из некоторого конечного множества, называемого входным алфавитом.

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

3. Одно из состояний автомата выделяется в качестве начального – S₀.

4. При чтении очередного входного символа состояние автомата меняется, причем новое состояние зависит от входного символа и текущего состояния автомата. Этот переход задается с помощью функции переходов.

5. Некоторые состояния автомата выбираются в качестве допускающих. Если автомат, начав работу в состоянии S₀, после прочтения всей цепочки переходит в одно из допускающих состояний, будем говорить, что входная цепочка допускается автоматом. Если последнее состояние не является допускающим, то цепочка отвергается.

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

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

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

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

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

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

Определение 4. Цепочка, под действием которой, одно из пары состояний переходит в допускающее, а другое – в отвергающее называется различающей для этих состояний.

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

Алгоритм поиска эквивалентных состояний основан на двух условиях:

а) условие подобия – состояния S и T подобны, если они оба или отвергающие, или допускающие;

б) условие преемственности – состояния S и T преемственны, если для любых входных символов они переходят в эквивалентные состояния.

Утверждение. Состояния S и T эквивалентны, если они подобны и преемственны.

Алгоритм поиска эквивалентных состояний (алгоритм а)

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

1. Строим таблицу эквивалентности для пары проверяемых состояний, отводя столбец под каждый входной символ, а проверяемую пару заносим в виде метки первой строки.

2. Выбираем в таблице строку, ячейки которой еще не заполнены и ставим справа знак «+», если проверяемые состояния подобны или знак «-» в противном случае. При появлении первого знака «-» процедуру заканчиваем.

Если для некоторой строки был поставлен знак «+», записываем в ячейки преемников для пары-метки строки.

3. Для каждой ячейки таблицы на шаге 2 существует три возможности:

1. получена пара одинаковых состояний – помечаем ее одним символом и никаких действий не производим.

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

3. если появилась пара новых различных состояний – заводим для нее новую строку.

4. Если все строки заполнены, то исходная пара состояний и все остальные, порожденные в ходе проверки, эквивалентны.

5. Если заполнены не все строки – возвращаемся к шагу 2.

6. Конец алгоритма.

Алгоритм поиска эквивалентных состояний (алгоритм б)

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

1. Строим разбиение P₀, содержащее два подмножества состояний (или блока разбиения) так, что одно подмножество состоит из всех допускающих, а другое – из всех отвергающих состояний.

2. Исследуем все переходы каждого блока разбиения по каждому входному символу и если преемники двух состояний находятся в разных блоках, то эти состояния помещаем в разные блоки.

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

4. Конец алгоритма

Эквивалентные состояния можно объединить в одно. Для этого нужно заменить все имена эквивалентных состояний одним символом.

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

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

Алгоритм определения достижимых состояний

1. Поместить в подмножество достижимых состояний начальное состояние.

2. Для каждого состояния, добавленного в подмножество на предыдущем шаге, определить всех преемников и добавить во множество тех из них, которые там еще не представлены.

3. Повторять шаг 2 до тех пор, пока алгоритм не перестанет поставлять новые состояния.

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

5. Конец алгоритма.

Определение 6. Минимальный автомат – это автомат, который не содержит недостижимых состояний и никакие два его состояния не являются эквивалентными.

Заметим, что наряду с конечными распознавателями рассматривают и так называемые процессоры. В этом случае во входной алфавит добавляется символ «–|» – маркер конца цепочки, а в соответствующий столбец заносится команда (либо вызов специальной функции обработки) „да”, если это допускающее состояние, и „нет”, если состояние отвергающее. Например:

0

1

0

1

–|

A

B

C

0

A

B

C

нет

B

A

C

0

B

A

C

нет

C

A

F

0

C

A

F

нет

D

B

C

0

D

B

C

нет

E

B

C

1

E

B

C

да

F

D

A

1

F

D

A

да

Таблица переходов для Таблица переходов

конечного распознавателя для процессора