double arrow

Лингвистический автомат

Минимизация числа состояний автомата

Алгоритм на основании языка 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


Понравилась статья? Добавь ее в закладку (CTRL+D) и не забудь поделиться с друзьями:  



Сейчас читают про: