Главная страница Случайная лекция Мы поможем в написании ваших работ! Порталы: БиологияВойнаГеографияИнформатикаИскусствоИсторияКультураЛингвистикаМатематикаМедицинаОхрана трудаПолитикаПравоПсихологияРелигияТехникаФизикаФилософияЭкономика Мы поможем в написании ваших работ! |
Эквивалентность состояний недетерминированного автомата
При проектировании автоматов часто возникают ситуации, когда для заданного символа входного алфавита безразличны значения функций выходов и/или переходов. Это приводит к тому, что в таблицах выходов и/или переходов не определены отдельные позиции. Такие автоматы называют недетерминированными или частично определенными. Для фиксации неопределенных позиций в таблицах выходов и/или переходов введем знак "*". В безразличную позицию можно поместить любой символ выходного алфавита или алфавита внутренних состояний. Пусть таблицами 1.47 и 1.48 дано описание недетерминированного автомата. Эквивалентность состояний автомата определяют по реакции автомата на входной символ и по формированию выходной последовательности bi=(y1y2...уp-1yp), как реакцию автомата на входную последовательность a=(x1x2...xp). Если существуют состояния qi и qj, для которых значения функций выходов j(qi;xk) и j(qj;xk) определены для некоторых xkÎX и они совпадают или значение одной из функций j(qi;xk) покрывает безразличную позицию другой j(qj;xk) или значения обеих функций не определены для некоторых xkÎX, то состояния qi и qj называются неотличимыми. Например, такими парами неотличимых состояний по таблице 1.47 являются (qp;qt), (qp;qv), (qr;qu), (qr;qs), (qs;qu), (qu;qv). Если существуют состояния qi и qj, значения функции выходов j(qi;xk) и j(qj;xk) которых различны хотя бы для одного xkÎX, т. е. j(qi;xk)¹j(qj;xk), то такие состояния называются отличимыми. Например, такими парами отличимых состояний по таблице 1.47 являются (qp;qr), (qp;qs), (qp;qu), (qr;qt), (qr;qv), (qs;qt), (qs;qv), (qt;qu) и (qt;qv).
Если множеству неотличимых пар принадлежат (qi;qj), (qj;qk) и (qi;qk), то {qi;qj;qk} формирует класс неотличимых состояний Q'i (условие транзитивности). Например, по таблице 1.47 имеем класс Q'1={qr;qs;qu}. Если множеству неотличимых пар принадлежат (qi;qj), (qj;qk), но не принадлежит (qi;qk), то формируются два класса неотличимых состояний {qi;qj} и {qj;qk}. При этом одно состояние qj принадлежит двум классам неотличимости. Например, по таблице 1.47 для недетерминированного автомата имеем Q'2={qp;qt}, Q'3={qp;qv} и Q'4={qu;qv}. Выходные последовательности bi и bj с неопределенными символами считаются неотличимыми, если в каждой позиции, где выходные символы определены, они совпадают. Например, b1=(0*1*1*), b2=(011***), b3=(*1*01*) и b4=(***011). Выходная последовательность bi=(y1y2...уp-1yp) покрывает выходную последовательность bj=(y1*...*yp), в которой могут быть неопределенные символы, если всякий определенный символ в последовательности bj равен соответствующему символу в последовательности bi. Например, bi=(100100) покрывает bj=(1*0**0) или bk=(**0*0*). Это условие записывают так: bi³bj. Неотличимые последовательности b могут быть реакциями на различные входные последовательности или иметь различные q0. Поэтому для поиска эквивалентных состояний необходима проверка поведения автомата на различные входные последовательности. Последовательность a=(x1x2...xp) называется допустимой для автомата, находящегося в состоянии q0, если функция переходов определена для всех символов последовательности (x1x2...xp), кроме, возможно, последнего, то есть qp= y(y... (y(y(y(q0;x1);x2);...xp-1) . Начальное состояние q0 и последовательность a=(x1x2...xp) однозначно определяют последовательность изменения состояний автомата. Например, для q0=qp последовательность a=(x1xnx2x1x2x1) является допустимой, т. к. qp[1]qr[2]qr[3]qt[4]qs[5]*[6], а последовательность a=(x1xnx2x2xnx1) - недопустимой, т. к. qp[1]qr[2]qr[3]*[4] . Состояния qi и qj называют совместимыми для допустимой входной последовательности a, если j(qi; a ) неотличима от j(qj; a ). Если автомат, начав работу в состоянии qi или qj, для a дает на выходе одинаковые последовательности символов в тех позициях, в которых были определены функции выходов, или пробелы в тех позициях, в которых они не были определены, то состояния qi и qj можно заменить эквивалентным состоянием q. Например, состояния qp и qt (см. таблицы 1.47 и 1.48) являются совместимыми для входной последовательности a= (x1x2xnx1x1x1): вход: x1 - x2 - xn - x1 - x1 - x1; вход: x1 - x2 - xn - x1 - x1 - x1; q: qp - qr - qt - qp - qr - qp; q: qt - qs - qp - qt - qs - *; выход: ys - yj - yt - ys - yi - ys, выход: ys - * - yt - ys - yi - *, то есть b1=(ysyjytysyiys). то есть b2=( ys*yt ys yi*). При этом последовательность b1 покрывает последовательность b2, т. е. b1³b2. Состояния qr и qu (cм. таблицы 1.47 и 1.48) не являются совместимыми для входной последовательности a= (x2x2x2xnx1x2), так как вход: x2 - x2 - x2 - xn - x1 - x2; вход: x2 - x2 - x2 - xn - x1 - x2; q: qr - qt - qr - qt - qp - qr; q: qu - qv - qv - qv - qp - qr; выход: yj - yp - yj - yt - ys - yj; выход: yj - yi - yi - * - ys - yj. то есть b1=(yjypyjytysyj). то есть b2=( yjyiyi* ysyi). При считывании второго, третьего и четвертого символов входной последовательности для начальных состояний qr и qu автомат проходит через отличимые состояния (qr;qv) и (qt;qv) и последовательность b1 не совпадает с последовательностью b2, то есть j(qr;x2)¹j(qv;x2) и j(qt;x2)¹j(qv;x2). Следовательно, состояния qr и qu не эквивалентны. Если для неотличимой пары (qi;qj) значения функций переходов (y(qi[t];xk[t]);y(qj[t];xk[t])) формируют также пару неотличимых или неопределенных состояний, то такие состояния qi и qj называют совместимыми. Для поиска совместимых состояний следует использовать таблицу переходов пар неотличимых состояний. Левый столбец этой таблицы предназначен для указания пар неотличимых состояний, которые определяются по таблице выходов автомата по условию j(qi;xk) =j(qj;xk) для всех xkÎX. Позициями этой таблицы являются пары состояний, которые определяются по таблице переходов при приеме символа xkÎX, т.е. (y(qi;xk);y(qj;xk)). Если одна или обе функции переходов имеют для xkÎX неопределенное значение, то в соответствующей позиции ставится знак "*". Пусть таблица переходов пар неотличимых состояний представлена таблицей 1.49.
Таблица 1.49.
Анализ таблицы показывает, что 1) состояния qp и qv совместимы, так как при приеме символа xn переходят в неотличимую пару состояний (qp;qt); 2) состояния qr и qs совместимы, так как. при приеме символа x2 переходят в неотличимую пару состояний (qp;qt); 3) состояния qs и qu совместимы, так как при приеме символа x2 переходят в неотличимую пару состояний (qp;qv); 4) состояния qp и qt совместимы, так как при приеме символа x1 переходят в неотличимую пару состояний (qr;qs); 5) состояния qu и qv совместимы, так как при приеме символа x2 переходят в одно состояние qv, а при приеме символа xn переходят в неотличимую пару состояний (qp;qt); 6) состояния qr и qu не совместимы, так как при приеме символа xn переходят в пару отличимых состояний (qr;qt), а при приеме символа x2 - в пару отличимых состояний (qt;qv); следовательно, класс Q'1 следует разложить на два класса совместимых состояний Q'5={qr;qs} и Q'6={qs;qu}. Если множеству совместимых пар принадлежат пары (qi;qj), (qj;qk) и (qi;qk), то есть выполняется условие транзитивности для отношения совместимости, то {qi;qj;qk} формирует класс совместимых состояний Q'i={qi;qj;qk;...}. Таких пар в данном примере нет. Если множеству совместимых пар принадлежат пары (qi;qj), (qj;qk) и не принадлежит пара (qi;qk), то есть не выполняется условие транзитивности для отношения совместимости, то формируются два класса совместимых состояний Q'i= {qi;qj;...} и Q'j={qj;qk;...}. Таких пар в данном примере четыре. Поэтому должно быть сформировано пять классов совместимости: Q'2={qp;qt}, Q'3={qp;qv}, Q'4={qu;qv}, Q'5={qr;qs} и Q'6=(qs;qu}. Множество совместимых классов называется согласованным, если для любого класса из этого множества и любых его элементов qi и qj значения функций переходов y(qi;xk) и y(qj;xk) принадлежат только одному совместимому классу или одному внутреннему состоянию для любого символа xk. В данном примере это условие выполняется (см. таблицу 1.50).
Таблица 1.50.
Множество совместимых и согласованных классов называется замкнутым, если всякое внутреннее состояние автомата принадлежит хотя бы одному из этих классов. В данном примере это условие также выполняется. Замкнутое множество совместимых и согласованных классов называется минимальным, если все внутренние состояния автомата принадлежат минимальному числу согласованных классов. В данном примере минимальный автомат могут представлять три согласованных класса: Q'2={qp;qt}, Q'4={qu;qv} и Q'5={qr;qs}. Состояния каждого класса можно "склеить" в одно состояние q' и заполнить таблицы переходов и выходов известными значениями функций всех состояний соответствующего класса. Пусть q'1«{qp;qt}, q'2«{qu;qv}, q'3«{qr;qs}. Тогда поведение минимального автомата может быть описано таблицами 1.51 и 1.52.
Анализ показывает, что в результате поиска неотличимых и совместимых состояний недетерминированного автомата, их согласования и склеивания получен детерминированный автомат, имеющий меньшее число состояний. Для проверки эквивалентности исходного (недетерминированного) и минимального автоматов следует рассмотреть их реакцию на допустимую входную последовательность. Пусть a=(x1x2x1x2xnx1x2x1). а) для недетерминированного автомата имеем вход: x1 - x2 - x1 - x2 - xn - x1 - x2 - x1; q: qp - qr - qt - qs - qp - qt - qs - qp; выход: ys - yj - ys - * - yt - ys - * - ys; b) для минимального автомата имеем: вход: x1 - x2 - x1 - x2 - xn - x1 - x2 - x1; q: q1 - q3 - q1 - q3 - q1 - q1 - q3 - q1; выход: ys - yj - ys - yj - yt - ys - yj - ys. Cравнение последовательностей на выходе двух автоматов показывает, что найден минимальный детерминированный автомат, который покрывает исходный недетерминированный автомат. Контрольные вопросы и задачи. 1) Начертить граф и найти эквивалентные состояния недетерминированного автомата, описанного таблицей:
2) Начертить граф и найти эквивалентные состояния недетерминированного автомата, описанного таблицей:
3) Начертить граф и найти эквивалентные состояния недетерминированного автомата, описанного таблицей:
4) Начертить граф и найти эквивалентные состояния недетерминированного автомата, описанного таблицей:
Дата добавления: 2015-07-26; просмотров: 220; Нарушение авторских прав Мы поможем в написании ваших работ! |