Минимизация конечных автоматов

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

В этом разделе мы установим, что для каждого конечного распознавателя существует единственный КА, распознающий то же самое множество цепочек, при этом число его состояний не больше числа состояний любого другого КА для этого множества. То есть существует единственный конечный автомат M^½, имеющий наименьшее число состояний среди всех КА, допускающих язык L(M). Такой автомат будем называть минимальным.

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

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

Состояние s конечного распознавателя M эквивалентно состоянию t конечного распознавателя N тогда и только тогда, когда автомат M, начав работу в состоянии s будет допускать в точности те же цепочки, что и автомат N, начавший работу в состоянии t.

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

Пример 3.2. На рис. 3.6 (а) представлен автомат, у которого состояния q₄ и q₅ явно

эквивалентны, так как оба они допускающие, при чтении символа a переходят в q₂, а при чтении b переходят в q₃. Объединяя q₄ и q₅ в одно состояние x, получим автомат, представленный на рис. 3.6 (б). Обычно, эквивалентность состояний менее очевидна, чем в этом примере, и необходим специальный тест на эквивалентность. •

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

Таким образом автоматы M и N эквивалентны тогда и только тогда, когда эквивалентны их начальные состояния.

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

Пример 3.3. На рис. 3.7 представлены два автомата, у которых состояния X и A неэквивалентны, так как различающая их цепочка - 101:

,

причем C - допускающее состояние, а Z - нет.

Поскольку A и X начальные состояния двух автоматов, то они неэквивалентны. •

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

Эквивалентность состояний является отношением эквивалентности в математическом смысле: оно рефлексивно (каждое состояние эквивалентно самому себе), симметрично (из s º t следует, что t º s ) и транзитивно (если s º t и t º u, то s º u ).

Дата добавления: 2015-06-27