double arrow

Метод Хафмена

Этот метод работает как для лингвистических автоматов, так и для автоматов Мили.

Идея: объединение предположительно эквивалентных состояний, а затем проверка, являются ли состояния действительно эквивалентными. Затем, если состояния не эквивалентны, классы разбиваем на подклассы, и проверка повторяется. Если состояния ведут себя одинаково, то процедура закончена, и получившиеся классы являются состояниями минимизированного автомата.

Два состояния называются эквивалентными, если автомат, находясь в этих состояниях, вырабатывает для любой входной последовательности одну и ту же выходную.

Например, рассмотрим автомат, диаграмма которого представлена на рис. 18

Рис.18

1. Составляем таблицы переходов и выходов.

  A B C D E F G
  B   D   E   D   A   G   D  
  F   C   G   C   F   E   C  

2. Составляем классы предположительно эквивалентных состояний (т.е. состояний, при переходе из которых на одинаковые входы выдаются одинаковые выходы).

В данном случае это классы K1= {A, B, D}, K2= {C, E, F, G}

3. Составляем таблицу переходов, в которой вместо состояний указываются классы, которым принадлежат состояния.

  A B C D E F G
  K1 K1 K2 K1 K1 K2 K1
  K2 K2 K2 K2 K2 K2 K2

Если в пределах одного класса состояния ведут себя по-разному, то класс разбивается на соответствующие подклассы, и возвращаемся к шагу 3.

(В нашем случае классы разбиваются, таблицы приводятся после алгоритма).

4. Если во всех классах состояния ведут себя одинаково, то это действительно классы эквивалентности.

Строится автомат, состояниями которого являются классы эквивалентности исходного автомата.

В нашем примере класс К2 разбивается на 2 класса - К3= {C, F}, К4 = {E,G}

  A B C D E F G
  K1 K1 К4 K1 К4 К4 К4
  К3 К3 К4 К3 К3 К4 К3

После этого разбиения состояния в классах действительно эквиваленты, Диаграмма полученного автомата представлена на рис. 19.

Рис.19

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

Применение метода к автомату, диаграмма которого представлена на рис. 16, имеющему таблицу переходов

           
a          
b          

и конечные состояния 3, 5, на первом шаге дает классы К1 = {3, 5}, K2= {1, 2, 4} и, соответственно, получаем таблицу переходов:

           
a K2 K2 K2 K2 K2
b К1 K2 K2 К1 K2

Видно, что класс K2 разбивается на два класса K3= {1, 4}, K4={2}. Получается таблица переходов

           
a K4 K4 K3 K4 K3
b К1 K3 K4 К1 K4

Очевидно, что, как и следовало ожидать, получившийся минимальный автомат совпадает с тем, который получен в пункте 9.1. Диаграмма полученного автомата приведена на рис. 17.

9.3. Минимизация не полностью определенных автоматов (на примере лингвистического автомата, диаграмма которого представлена на рис. 15).

Повторение, рис. 15.

При минимизации не полностью определенных лингвистических автоматов начальное разбиение множества состояний делается так же, как для полностью определённого автомата, на конечные и не конечные состояния. Для данного случая классы K1={B, C, F} – конечные состояния, K2= {A, D, E, G} – не конечные. Приведем таблицы переходов состояний для этого автомата:

Исходная таблица:


  A B C D E F G
a C B B F - F F
b E E G E - E E
c - - - - D - D

Проставляем классы состояний (в верхней строке указываем номер класса состояния):

             
  A B C D E F G
a K1 K1 K1 K1 - K1 K1
b K2 K2 K2 K2 - K2 K2
c - - - - K2 - K2

Далее разбиваем классы на подклассы в соответствии с одинаковостью- различием столбцов. Класс K2 разбивается на 3 класса K3 = {A, D}, K4 = {E}, K5 = {G}.

             
  A B C D E F G
a K1 K1 K1 K1 - K1 K1
b K4 K4 K5 K4 - K4 K4
c - - - - K3 - K3

Получившаяся таблица показывает, что класс K1 так же разбивается на два класса K6= {B, F}, K7 = {C}.

             
  A B C D E F G
a K7 K6 K6 K6 - K6 K6
b K4 K4 K5 K4 - K4 K4
c - - - - K3 - K3

И, наконец, разбивается класс K3 : K8= {A}, K9={D}.

             
  A B C D E F G
a K7 K6 K6 K6 - K6 K6
b K4 K4 K5 K4 - K4 K4
c - - - - K9 - K9

Это разбиение не приводит в дальнейшему разбиению классов и получившийся автомат – минимальный. Диаграмма автомата, на которой все классы, кроме 6-го, поименованы единственным входящим в них состоянием, а класс K6 – символом B, представлена на рис. 20.

Рис.20


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



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