Эквивалентность состояний

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

При этом автоматы, которые различаются лишь именами состояний можно считать «одинаковыми». Поэтому в нашем случае – единственный с точностью до имён состояний. Этот единственный автомат будем называть минимальным автоматом. Минимальный автомат – это компактный вариант автоматов большого объёма, а не автомат, у которого случайно оказалось меньше состояний. Следовательно он главный кандидат на реализацию.

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

Определение: Состояние S в КР М ~ (эквивалентно) состоянию t КР N ó когда автомат М, начав работу в состоянии S, будет допускать в точности те же цепочки, что и автомат N, начавший работу в состоянии t.

	a	b
x	x	x x

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

	a	b

	a	b
x x	x	x x

Обычно эквивалентность менее очевидна.

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

Определение: Автомат M и N эквиваленты ó, когда ~ их начальные состояния.

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

Определение: 2 состояния ~ó, когда не существует различающей их цепочки.

Понятие эквивалентности состояний является отношением эквивалентности в математическом смысле: это отношение рефлексивно (каждое состояние эквивалентно себе), симметрично (из того, что S~t=>t~S) и транзитивно (если S~t, а t~u,то S~u).

Дата добавления: 2014-01-11