Минимизация структуры конечного автомата.

Основные положения (до 15 минут)

Преобразование структуры автомата, которое уменьшает число его элементов (функциональных и запоминающих) без нарушения алгоритма функционирования,называется минимизацией.Методы минимизации различаются в зависимости от того,к каким элементам они применяются.

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

Ниже рассмотрим минимизацию конечных автоматов.

· Методы абстрактной минимизации конечных автоматов. (до 35 минут)

Специфика методов отыскания минимального (приведенного) автомата связана с формой задания и типом его поведения (акцептор, генератор)

Формальная постановка минимизации может быть следующей:

Из заданного множества автоматов Mu, имеющих один и тот же автоматный оператор Т:А*®В*,т.е. Mu={UiÎM: li(q0,a)=lj(q0,a)=b,|Qi|=|Qj|,aÎA*,bÎB*}. Найти автомат

UN=<A,Qn,B,d,l> с наименьшим числом состояний Qn (говорят,что | Qn | есть числа внутренних состояний приведенного автомата Un).

Теорема Для любого конечного автомата UN=<A,|Q|=n,B,d,l> минимальный автомат UN=<A,|Q|=l,B,d,l>,единственный с точностью до изоморфизма(т.е. множество состояний автомата U разбивается на l классов эквивалентности (l<=n),то UN имеет l состояний).

Пояснения

1)Из теоремы следует,что минимизация числа состояний полного конечного автомата связана отношением эквивалентности.

Пусть U1=<A,Q1,B,d1,l1> и U2=<A,Q2,B,d,l> два автомата с одинаковыми входными и выходными алфавитами. Состояния qiÎQ1 автомата U1 и состояния qjÎQ2 автомата U2 называются неотличимыми,если для любого входного слова aÎА*: l1(qi,a)=l2(qj,a)=b. В частности, если U₁=U₂,то говорят о не отличных состояниях U.Это означает что инициальные автоматы <U,q₀^|>,< U,q₀^||> реализуют один и тот же автоматный оператор Т_u:А*®В*.

Автоматы U_{1 b} U₂ называются не отличными (эквивалентными),если для любого состояния автомата U₁ найдется неотличимое состояние автомата U₂ и,наоборот, для любого состояния U₂ найдется неотличимое от него состояние U₁.

Переход от автомата U_i к эквивалентному U_n называется эквивалентным преобразованием автомата U_i.

2)Эта теорема не указывает алгоритма нахождения эквивалентных состояний автомата.

3) Из теоремы следует,что избыточность памяти конечного автомата, устраняется, склеиванием эквивалентных состояний (итак), если каждый класс эквивалентных состояний заменить одним состоянием, склеивая соответствующие вершины-состояния, то полученный граф переходов будет задавать приведенный автомат U_n).

Замечание

1)Автомат U,все состояния которого эквивалентны, сводится к автомату U_n с одним состоянием (автомат без памяти), т.е. U представляет собой по существу комбинационную схему.

2)Автомат,среди состояний которого нет эквивалентных, является несократимым.

3)Тривиальный метод определения (но не вычисления!) неотличимых состояний предполагает перебор по бесконечному множеству исходных слов.

Для эквивалентного разбиения множества состояния Q автомата предложено ряд практических методов.

Рассмотрим на примере метод Мили для абстрактной минимизации конечного автомата. Этот метод основан на склеивании эквивалентных состояний и состоит в последовательном выделении классов эквивалентных состояний с помощью n таблиц выходов и переходов. Шаги этого алгоритма следующие:

Шаг1: Два состояния q_li,q_jnÎQ относят в один класс С_1p, если и только если для любого аÎА: l1(qil,a)=l2(qjn,a).

Шаг1+n:Два состояния из одного класса С_ij, если и только если для любого аÎА:d(q^||,a),d(q^|,a) принадлежит одному и тому же классу С_ij.

Шаг i+2: Если (1+i)-ый шаг не изменяет разбиению, т.е. состояния из одного класса С_ij принадлежат одному классу С_i+j,j,что алгоритм заканчивается и полученное разбиение на классы эквивалентных (неразличимых) постоянных является искомым.

Дата добавления: 2015-12-01