ВУЗ:
Составители:
184
правилам: все состояния, принадлежащие к одному подмножеству S
i
,
должны быть k-эквивалентными и их называют смежными; все со-
стояния, принадлежащие к различным S
i
, должны быть k-
различимыми и их называют разобщёнными, то такое разбиение на-
зывают k-эквивалентным разбиением.
Эквивалентным разбиением (обозначается P*), называют k-
эквивалентное разбиение автомата, если во всех подмножествах это-
го разбиения состояния являются эквивалентными.
В теории автоматов доказывается следующая теорема.
Для автомата с q состояниями эквивалентное разбиение
равно q-1 эквивалентному разбиению, т.е. P
q-1
=P*.
Другими словами, процесс определения эквивалентного раз-
биения с q состояниями путём последовательного построения k-
разбиений для k=1,2,3… требует не более q-1 шагов.
Зачем нужно эквивалентное разбиение? Если оно получено, то
минимальный автомат может быть получен простым способом, а
именно: из каждого подмножества эквивалентного разбиения выби-
рается одно любое состояние, и
функции
λ
и
δ
определяются из ис-
ходной автоматной таблицы путем вычеркивания столбцов, соответ-
ствующих всем невыбранным состояниям.
Известно несколько регулярных методов нахождения эквива-
лентных разбиений. Большинство из них построено на последова-
тельном получении k-эквивалентных разбиений. Данная последова-
тельность конечна на основании вышеприведённой теоремы. Её ос-
танавливают при истинности следующего утверждения: P
k-1
=P
k
, т.е.
система множеств в разбиении на k-1 шаге равна системе множеств
на k-м шаге, и тогда P
k
=P*. Рассмотрим наиболее распространённый
алгоритм, решающий задачу минимизации числа состояний автома-
та. Будем делать это на конкретном примере. Пусть автомат Мили
Страницы
- « первая
- ‹ предыдущая
- …
- 186
- 187
- 188
- 189
- 190
- …
- следующая ›
- последняя »
