Пред. страница   След. страница   Раздел     Содержание

2.5 Минимизация числа состояний распознавателя

 

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

Определение. Два состояния si и sj называются эквивалентными, если переходы из этих состояний под действием любого входного слова α Î P* происходят в одно и то же состояние или в эквивалентные состояния.

Это отношение позволяет для каждой пары состояний si и sj установить, являются ли они эквивалентными или нет. Таким образом, множество состояний автомата может быть разделено на группы эквивалентных состояний, которые называются классами эквивалентности. Состояния, входящие в каждый класс эквивалентности, реагируют на входные воздействия одинаковым образом, поэтому каждому классу эквивалентности можно поставить в соответствие одно состояние и построить новый автомат с меньшим числом состояний.

Для выявления эквивалентных состояний используют входные цепочки ограниченной длины k = 0,1,2,…,r-1, а состояния эквивалентные для цепочек длины k называют k-эквивалентными состояниями.

Определение. Два состояния si и sj называются k-эквивалентными, если переходы из этих состояний под действием каждой входной цепочки длины k происходят  в одно и то же состояние или в k-эквивалентные состояния.

С помощью отношения k-эквивалентности множество состояний автомата разбивается на множества k-эквивалентных классов E1,E2,…Eq, а каждое такое множество в свою очередь разделяется на классы:

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

Построение классов k-эквивалентности выполняется последовательно для входных цепочек длины k = 0,1,2,….

Порядок построения классов k-эквивалентности можно представить в следующем виде:

  1. Разбиение множества состояний автомата S на 0-эквивалентные классы выполняется так. В первый класс включаются все состояния автомата, не являющиеся конечными:  = S – F, а в остальные класс включаются все заключительные состояния  = Z1,  = Z2 и так далее.
  2. В каждом классе  найдем группы таких состояний, из которых под действием одинаковых входных символов выполняется переход в k-эквивалентные состояния. Каждая такая группа представляет собой класс k+1-эквивалентных состояний. В результате получаем разбиение множества состояний на классы k+1-эквивалентности:
                                              
  3. Изменим значение k = k+1.
  4. Если при выполнении k-го шага новых классов эквивалентности не образуется , то это означает, что классов k-эквивалентности у автомата нет, и что построение закончено.
  5. Если же появились новые классы , то построение нужно продолжить, вернувшись к пункту 2.

После построения классов эквивалентности  каждому классу эквивалентности  нужно поставить в соответствие новое состояние автомата . Функции переходов для новых состояний  определяются следующим образом: если из состояний класса  под действием входного символа pj автомат переходит в состояния класса , то строится функция переходов j( pj, ) = .

 

В качестве примера минимизации числа состояний рассмотрим построение классов эквивалентности для автомата, изображенного на рис. 2.12.

  1. В качестве начального разбиения для k = 0, примем классы:
    ={I, A, B, C, D, E}, = {Z},  = {U}.
  2. Обозначим классы строчными латинскими буквами a, b, c и для каждого состояния определим, в какие классы переходит автомат под действием входных символов 0 и 1. Таким образом, для каждого состояния определим две буквы, обозначающие класс, в которые переходит автомат, и запишем эти буквы под каждым состоянием.
    ={ I,  A,  B,  C,  D,  E}, = {Z},  = {U}.
              aa    aa     aa     cb     cb     cb
    В классе  состояния разделяются на две группы. Из всех состояний первой группы выполняется переход в состояния группы , а из состояний второй группы в состояния классов  и . Следовательно, получаем множество 1-эквивалентных классов в виде:
                    ={I, A, B }, = { C, D, E },  = { Z},  = {U}.
  3. Снова обозначим новые 1-эквивалентные классы строчными латинскими буквами a, b, c, d и определим, в какие классы происходят переходы из различных состояний. В результате получаем:
                    ={I,  A,  B }, = { C,  D,  E },  = { Z},  = {U}.
                            aa   bd   bb                   dc   dc    cd
    После разделения класса  и , получаем два новых класса эквивалентности:
    ={I}, = {A},  = {B},  = {C, D},  = {E},  = {U}, = {U}.
  4. Попытка дальнейшего разделения классов не приводит к успеху.
    ={I}, = {A},  = {B},  = {C, D},  = {E},  = {U}, = {U}.
                                                                            fg    fg
    Получаем , что говорит о том, что классы эквивалентности построены.
  5. Обозначим класс эквивалентности  символом нового состояния C’ и построим диаграмму переходов искомого автомата, заменяя состояния C и D новым состоянием C’. Окончательно получаем диаграмму переходов автомата в виде.

Рис. 2.14. Диаграмма переходов распознавателя, определяющего принадлежность цепочки к языку L1, после минимизации

Итак, в результате минимизации на удалось сократить число состояний автомата на1.Если же выполнить построение классов эквивалентности для распознавателя, приведенного на рис. 2.13, то окажется, что он не имеет эквивалентных состояний. Несмотря на малый выигрыш, полученный в рассмотренном примере, процедура минимизации во многих случаях оказывается достаточно эффективной

 

Пред. страница   След. страница   Раздел     Содержание