Минимизация числа состояний автомата
Алгоритм на основании языка L, порождаемого автоматом.
Идея: разбить множество состояний на непересекающиеся множества неразличимых состояний.
Строятся матрицы D0, D1,… указывающие различимость состояний по строкам длины n. Состояния qi и qj различимы по строке длины 0(1 на пересечении строки i и столбца j матрицы D0): qi D0 qj Û (qiÎK) & (qjÏ K) Ú (qiÏ K)&(qjÎK).
Далее определение по индукции: при i > 0 состояния qk и qj различимы по строке длины i, т.е. (qk Di qj)Û qk Di-1 qj или $aÎVT, такой, что F(qk,a) Di-1 F(qj,a).
Состояние qk различимо от состояния qj, если $ i³ 0, такое, что qk Di qj.
Очевидно, что qk Di qj Û существует строка Х, ½Х½£ i, что (F(qi, X)ÎK) & (F(qj, X)Ï K) Ú (F(qi, X)Ï K)&(F(qj,, X)ÎK).
Пример.
Диаграмма автомата представлена на рис. 16.
Рис.16
Матрицы, получающиеся при анализе автомата:
D0 | F T F T T F T T F T | D1 | F T F T T T T T F T | D1=D2 |
Из анализа полученной матрицы получаем три класса эквивалентных состояний:
K1 = {1, 4}, K2 = {2}, K3 = {3,5}. Диаграмма полученного автомата представлена на рис. 17.
|
|
Рис.17