- •Оглавление
- •Глава 1. Алгебраические системы 17
- •Глава 2. Элементы комбинаторики 88
- •Глава 3. Основы теории графов 101
- •Глава 4. Основы математической логики 169
- •4.1.1.4. Эквивалентные преобразования формул 179
- •4.1.4. Выполнить подстановку: 247
- •Глава 5. Основы теории алгоритмов 252
- •Глава 6. Конечные автоматы 289
- •Введение
- •Глава 1. Алгебраические системы
- •1.1 Множества
- •1.1.1. Четкие множества
- •1.1.2. Нечеткие множества
- •1.2. Соответствия, отображения и функции
- •1.2.1. Четкие отображения и функции
- •1.2.2. Нечеткие отображения
- •1.3. Отношение
- •1.3.1. Четкие отношения
- •1.3.2. Нечеткое отношение
- •1.4. Элементы общей алгебры
- •1.5. Булева алгебра
- •1.5.1. Булевы операции
- •1.5.2. Законы булевой алгебры
- •1.5.3. Формула булевой функции
- •1.5.4. Описание булевой функции
- •1.5.5. Суперпозиция булевых функций
- •1.5.6. Свойства булевых функций
- •1.5.6.1. Самодвойственные булевы функции
- •1.5.6.2. Монотонные булевы функции
- •1.5.6.3. Линейные булевы функции
- •1.5.6.4. Функции, сохраняющие “0”
- •1.5.6.5. Функции, сохраняющие “1”
- •1.5.6.6. Функционально полные системы
- •1.5.7. Разложение булевых функции
- •1.5.7.1. Днф булевой функции
- •1.5.7.2. Кнф булевой функции
- •Алгоритм преобразования формулы к скнф:
- •1.5.8. Минимизация булевых функций.
- •1.5.8.1.Минимизация днф булевой функции
- •1.5.8.2. Минимизация кнф булевой функции
- •1.6. Алгебра четких множеств
- •1.6.1. Операции над множествами
- •1.6.2. Законы алгебры множеств
- •1.6.3. Эквивалентные преобразования формул
- •1.6.4. Композиция отображений и отношений
- •1.6.5. Поиск неизвестного множества
- •1.7. Алгебра нечетких множеств
- •1.7.1. Операции над нечеткими множествами
- •1.7.2. Композиция нечетких отображений
- •1.7.3. Композиция нечетких отношений
- •1.7.4. Свойства нечетких отношений
- •Вопросы и задачи
- •Глава 2. Элементы комбинаторики
- •2.1. Размещение из n элементов по k
- •2.2. Перестановка элементов
- •2.3 Сочетание из n элементов по k
- •2.4. Разбиение множества
- •2. 5 Правила комбинаторики
- •Вопросы и задачи
- •Глава 3. Основы теории графов
- •3.1. Граф и его характеристики
- •3.2. Описание графа
- •3. 3. Числа графа
- •3.4. Операции над графами
- •3.4.1. Унарные операции
- •3.4.1.1 Поиск дополнительного графа
- •3.4.1.2. Введение и удаление вершин графа
- •3.4.1.3. Стягивание вершин графа
- •3.4.1.4. Введение и удаление ребер графа
- •3.4.1.5. Поиск плотности и неплотности графа
- •3.4.1.6. Поиск числа компонент связности графа
- •3.4.1.7. Поиск устойчивости графа
- •3.4.1.8. Поиск цикломатического числа графа
- •3.4.1.9. Поиск хроматического числа графа
- •3.4.2. Бинарные операции
- •3.4.2.1. Объединение графов
- •3.4.2.2. Пересечение графов
- •3.4.2.3. Композиция графов
- •3.4.2.4. Соединение графов
- •3.4.2.5. Прямое произведение графов
- •3.4.2.6. Изоморфизм графов
- •3.5. Некоторые алгоритмы на графах
- •3.5.1. Построение покрывающего остова
- •3.5.2. Построение остова минимального веса
- •3.5.3. Поиск кратчайших путей в сети.
- •3.5.4. Поиск максимального потока в сети
- •3.5.5. Метод критического пути в управлении
- •3.6. Нечеткие графы
- •Вопросы и задачи
- •Глава 4. Основы математической логики
- •4.1. Логика высказываний
- •4.1.1. Алгебра высказываний
- •4.1.1.1. Логические операции
- •4.1.1.2. Правила записи сложных формул.
- •4.1.1.3. Законы алгебры высказываний
- •4.1.1.4. Эквивалентные преобразования формул
- •4.1.1.5. Нормальные формы формул
- •4.1.2. Исчисление высказываний
- •4.1.2.1. Интерпретация формул
- •4.1.2.2. Аксиомы и правила введения и удаления логических связок
- •4.1.2.3. Метод дедуктивного вывода
- •4.1.2.4. Принцип резолюции
- •4. 2. Логика предикатов
- •4.2.1. Алгебра предикатов
- •4.2.1.1. Законы алгебры предикатов
- •4.2.1.2. Предваренная нормальная форма формулы
- •4.2.1.3 Сколемовская стандартная форма формулы
- •4. 2. 2. Исчисление предикатов
- •4.2.2.1. Правила подстановки
- •4.2.2.2. Правила введения и удаления кванторов
- •4.2.2.3. Правила заключения
- •4.2.2.4. Метод дедуктивного вывода
- •4.2.2.5. Принцип резолюции
- •4.2.2.6. Логическое программирование
- •4.3. Логика реляционная
- •4.3.1 Реляционная алгебра
- •4.3.1.1. Унарные операции
- •4.3.1.2. Бинарные операции
- •4.3.1.3. Правила реляционной алгебры
- •4.3.2. Реляционное исчисление
- •4.3.3. Языки реляционной логики
- •4.4. Нечеткая логика
- •4.4.1. Нечеткое исчисление
- •4.4.2. Экспертные системы
- •Вопросы и задачи
- •Глава 5. Основы теории алгоритмов
- •5.1. Рекурсивные функции
- •5.1.1. Базовые функции
- •5.1.2. Элементарные операции
- •5.2. Машина Тьюринга
- •5.2.1. Описание машины Тьюринга
- •5.2.2. Примеры машин Тьюринга
- •5.2.3. Композиция машин Тьюринга
- •5.3. Нормальные алгоритмы Маркова
- •5.4 Сложность вычислений
- •Вопросы и задачи
- •Глава 6. Конечные автоматы
- •6.1. Абстрактный автомат
- •6.1.1. Типы конечных автоматов
- •6.1.2. Описание автоматов
- •6.1.3. Автоматное моделирование алгоритмов
- •6.1.3.1. Автомат Мили - модель управляющего автомата
- •6.1.3.2. Автомат Мура - модель управляющего автомата
- •6.1.3.3. Микропрограммный автомат
- •6.1.4. Эквивалентность автоматов
- •6.1.5. Эквивалентность внутренних состояний автомата
- •6.1.5.1. Детерминированный автомат
- •6.1.5.2. Недетерминированный автомат
- •6.2. Структурный автомат
- •6.2.1. Произведение автоматов
- •6.2.1.1. Последовательное соединение автоматов
- •6.2.1.2. Параллельное соединение автоматов
- •Обратная связь автоматов
- •6.2.3. Сумма автоматов
- •6.2.4. Структурный автомат и кодирование
- •6.3. Логическое проектирование автоматов
- •6.3.1. Кодирование алфавитов автомата
- •6.3.2. Автоматы без “памяти”.
- •6.3.2.1. Формирование оператора
- •6.3.2.2. Формирование системы операторов
- •Логическая схема комбинационного автомата
- •6.3.3. Автоматы с “памятью”
- •6.3.3.1. Формирование оператора
- •6.3.3.2. Формирование оператора
- •.3.3.3. Логическая схема автомата с “памятью”
- •Вопросы и задачи
- •Литература
- •Предметный указатель
6.1.5.2. Недетерминированный автомат
При проектировании автоматов часто возникают ситуации, когда для некоторых символов входного алфавита не заданы значения функций выходов и/или переходов. Это приводит к тому, что в таблицах выхода и/или переходов не определены отдельные позиции. В такую позицию можно поместить любой символ выходного алфавита или алфавита состояний. Пусть таблицами 6.21 и 6.22 дано описание недетерминированного автомата.
Таблица 6.21. |
|
Таблица 6.22. |
|||||||||||
текущее состояние |
xX |
|
текущее состояние |
xX |
|
||||||||
x1 |
x2 |
… |
xn |
|
x1 |
x2 |
… |
xn |
|
||||
… |
… |
… |
… |
… |
|
… |
… |
… |
… |
… |
|
||
qp |
ys |
* |
… |
yt |
|
qp |
qr |
* |
… |
qt |
|
||
qr |
yi |
yj |
… |
yp |
|
qr |
qp |
qt |
… |
qr |
|
||
qs |
yi |
* |
… |
yp |
|
qs |
* |
qp |
… |
* |
|
||
qt |
ys |
yp |
… |
yt |
|
qt |
qs |
qr |
… |
qp |
|
||
qu |
* |
yj |
… |
yp |
|
qu |
qp |
qv |
… |
qt |
|
||
qv |
ys |
yj |
… |
* |
|
qv |
* |
qv |
… |
qp |
|
||
… |
… |
… |
… |
… |
|
… |
… |
… |
… |
… |
|
||
Эквивалентность состояний автомата определяют по реакции автомата на входную последовательность =(x1x2...xp).
Если существуют qi и qj, для которых значения функций выходов (qi;xk) и (qj; xk) определены для некоторых xkX и они совпадают, или значение одной из функций покрывает безразличную позицию другой или значения обеих функций не определены для некоторых xkX, то состояния qi и qj называются неотличимыми. Например, такими парами по таблице 6.21 являются (qp; qt), (qp; qv), (qr; qu), (qr; qs), (qs; qu), (qu;qv).
Если существуют состояния qi и qj, значения функции выходов которых различны хотя бы для одного xkX, т. е. (qi; xk)(qj;xk), то такие состояния называются отличимыми. Например, такими парами являются (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 (условие транзитивности). Например, Q'1={qr; qs; qu}.
Если множеству неотличимых пар принадлежат (qi; qj), (qj; qk), но не принадлежит (qi; qk), то формируются два класса неотличимых состояний {qi; qj} и {qj; qk}. При этом одно состояние qj принадлежит двум классам неотличимости. Например, Q'2={qp; qt}, Q'3={qp; qv} и Q'4={qu; qv}.
Выходные последовательности i и j с неопределенными символами считаются неотличимыми, если в каждой позиции, где выходные символы определены, они совпадают.
Например, неотличимыми являются 1=(0*1*1*), 2=(011***), 3=(*1*01*) и 4=(***011).
Выходная последовательность i=(y1y2... yp) покрывает выходную последовательность j=(y1*...*yp), в которой могут быть неопределенные символы, если всякий определенный символ в последовательности j равен соответствующему символу в слове i.
Например, i=(100100) покрывает j=(1*0**0) или k=(**0*0*).
Это условие записывают так: ij.
Если функция переходов определена для всех символов слова =(x1x2...xp), кроме, возможно, последнего - xn, то есть qp= (...(( (q0;x1);x2);...xp-1), то последовательность =(x1x2...xp) называется допустимой для автомата, находящегося в состоянии q0.
Например, для q0=qp последовательность =(x1xnx2x1x2x1) является допустимой, т. к. qp[1]qr[2]qr[3]qt[4]qs[5]*[6], а последовательность =(x1xnx2x2xnx1) - недопустимой, т. к. qp[1]qr[2]qr[3]*[4].
Состояния qi и qj называют совместимыми для допустимой последовательности , если (qi; ) неотличима от (qj; ).
Если автомат, начав работу в состоянии qi или qj, формирует на выходе одинаковые последовательности, то состояния qi и qj можно заменить эквивалентным состоянием q.
Например, состояния qp и qt (см. таблицы) являются совместимыми для входной последовательности = (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 - *,
то есть 1=(ysyjytysyiys). то есть 2=( ys*yt ys yi*).
При этом последовательность 1 покрывает последовательность 2, т. е. 12.
Состояния qr и qu (cм. таблицы) не являются совместимыми для входной последовательности = (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.
то есть 1=(yjypyjytysyj). то есть =( yjyiyi*ysyi).
Следовательно, состояния qr и qu не эквивалентны.
Для поиска совместимых состояний следует использовать таблицу переходов пар неотличимых состояний. Левый столбец этой таблицы предназначен для указания пар неотличимых состояний. Позициями этой таблицы являются пары состояний, которые определяются по таблице переходов при приеме символа xkX, т.е. ((qi; xk); (qj; xk)). Если одна или обе функции переходов имеют неопределенное значение для xkX, то в соответствующей позиции ставится знак "*".
Пусть таблица переходов пар неотличимых состояний представлена таблицей 6.23.
Таблица 6.23. |
||||
неотличимые состояния (qi;qj) |
xX |
|||
x1 |
x2 |
… |
xn |
|
(qp; qt)Q'2 |
(qr; qs) |
* |
... |
(qp; qt) |
(qp; qv)Q'3 |
* |
* |
... |
(qp; qt) |
(qr; qu)Q'1 |
(qp; qp) |
(qt; qv) |
... |
(qr; qt) |
(qr; qs)Q'1 |
* |
(qp; qt) |
... |
* |
(qs; qu)Q'1 |
* |
(qp; qv) |
... |
* |
(qu; qv)Q'4 |
* |
(qv; qv) |
... |
(qp; qt) |
Анализ таблицы показывает, что
состояния qp и qv совместимы, так как при приеме символа xn переходят в неотличимую пару состояний (qp; qt);
состояния qr и qs совместимы, так как. при приеме символа x2 переходят в неотличимую пару состояний (qp; qt);
состояния qs и qu совместимы, так как при приеме символа x2 переходят в неотличимую пару состояний (qp; qv);
состояния qp и qt совместимы, так как при приеме символа x1 переходят в неотличимую пару состояний (qr; qs);
состояния qu и qv совместимы, так как при приеме символа x2 переходят в одно состояние qv, а при приеме символа xn переходят в неотличимую пару состояний (qp; qt);
состояния qr и qu не совместимы, так как при приеме символа xn переходят в пару отличимых состояний (qr; qt), а при приеме символа x2 - в пару отличимых состояний (qt; qv); следовательно, класс Q'1 следует разложить на два класса совместимых состояний Q'5={qr; qs} и Q'6={qs; qu}.
Если есть совместимые пары (qi; qj), (qj; qk) и (qi; 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 значения функций переходов (qi; xk) и (qj; xk) принадлежат только одному совместимому классу или одному состоянию для любого символа xk. В данном примере это условие выполняется (см. таблицу 6.24).
Таблица 6.24. |
||||
Совместимые классы Q'i |
xX |
|||
x1 |
x2 |
… |
xn |
|
Q'2 |
Q'5 |
* |
... |
Q'2 |
Q'3 |
* |
* |
... |
Q'2 |
Q'4 |
* |
Q'7 |
... |
Q'2 |
Q'5 |
* |
Q'2 |
* |
... |
Q'6 |
* |
Q'3 |
... |
* |
Множество совместимых и согласованных классов называется замкнутым, если любое состояние автомата принадлежит хотя бы одному из этих классов. В данном примере это условие также выполняется.
Замкнутое множество совместимых и согласованных классов называется минимальным, если все внутренние состояния автомата принадлежат минимальному числу согласованных классов. В данном примере минимальный автомат могут представлять три согласованных класса: Q'2={qp; qt}, Q'4={qu; qv} и Q'5={qr; qs}. Состояния каждого класса можно представить эквивалентным состоянием.
Пусть q'1{qp; qt}, q'2{qu; qv}, q'3{qr; qs}.
Поведение минимального автомата описано таблицами 6.25 и 6.26.
Таблица 6.25 Таблица 6.26
текущее состояние q'i |
xX |
|
текущее состояние q'i |
xX |
||||||
x1 |
x2 |
... |
xn |
|
x1 |
x2 |
... |
xn |
||
q'1 |
ys |
yp |
... |
yt |
|
q'1 |
q'3 |
q'3 |
... |
q'1 |
q'2 |
ys |
yj |
... |
yp |
|
q'2 |
q'3 |
q'2 |
... |
q'1 |
q'3 |
yi |
yj |
... |
yp |
|
q'3 |
q'1 |
q'1 |
... |
q'3 |
Анализ показывает, что в результате поиска неотличимых и совместимых состояний, их согласования и склеивания получен детерминированный автомат, имеющий меньшее число состояний.
Для проверки эквивалентности заданного недетерминированного и минимального детерминированного автоматов следует рассмотреть их реакцию на допустимую входную последовательность.
Пусть =(x1x2x1x2xnx1x2x1).
Для недетерминированного автомата имеем
вход: x1 - x2 - x1 - x2 - xn - x1 - x2 - x1;
q: qp - qr - qt - qs - qp - qt - qs - qp;
выход: ys - yj - ys - * - yt - ys - * - ys.
Для минимального автомата имеем:
вход: 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.
Так найден минимальный автомат, который покрывает исходный недетерминированный автомат.
Алгоритм минимизации числа внутренних состояний недетерминированного автомата:
шаг 1: выделить в таблице выходов автомата множества неотличимых и отличимых пар по правилу:
"а) если среди множества пар состояний автомата (qi; qj)(QQ) найти такие qi и qj, для которых значения функций выходов (qi;xk) и (qj;xk) определены и они совпадают, или значение одной из функций покрывает безразличную позицию другой или значения обеих функций не определены, то пару (qi; qj) считать неотличимой;
b) если среди множества пар (qi; qj)(QQ) найти такие qi и qj, для которых значения функции выходов (qi; xk) и (qj;xk) различны хотя бы для одного xkX, то пару (qi; qj) считать отличимой ";
в результате анализа таблицы 6.21 пары неотличимых состояний есть (qp; qt), (qp; qv), (qr; qu), (qr; qs), (qs; qu), а пары отличимых состояний - (qp; qr), (qp; qs), (qp; qu), (qr; qt), (qr; qv), (qs; qt), (qs; qv), (qt; qu), (qt; qv).
шаг 2: на множестве пар неотличимых состояний определить классы неотличимых состояний по правилу:
"а) если среди множества пар неотличимых состояний существуют пары (qi; qj), (qj; qk) и (qi; qk), то по условию транзитивности формируют класс неотличимых состояний Q'i ={qi; qj; qk };
b) если среди множества пар неотличимых состояний существуют пары (qi; qj), (qj; qk) и не существует пара (qi; qk), то формируют два класса неотличимых состояний Q'l={qi; qj} и Q'k={qj; qk}, при этом состояние qj принадлежит двум классам";
в результате анализа множества неотличимых пар сформированы классы неотличимых состояний Q'1={qr; qs; qu}, Q'2={qp; qt} и Q'3={qp; qv}; при этом Q'1Q'2Q'3=Q, Q'1Q'2=, Q'1Q'3=, но Q'2Q'3;
шаг 3: составить таблицу переходов для пар неотличимых состояний:
"левый столбец таблицы представить парами неотличимых состояний, которые сгруппированы по классам неотличимости; позиции таблицы заполнить по таблице переходов для каждой неотличимой пары (qi; qj) и для каждого символа xkX парами значений ((qi; xk);(qj; xk)); если хотя бы одно из значений функции переходов (qi;xk) или (qj;xk) имеет значение "", то паре ((qi;xk);(qj;xk)) присвоить значение """;
шаг 4: на множестве пар неотличимых состояний по таблице переходов определить пары совместимых состояний:
"если для пары неотличимых состояний (qi; qj) значения функции переходов ((qi; xk);(qj; xk)) для xkX принадлежат также множеству пар неотличимых состояний (левому столбцу таблицы), то состояния qi и qj совместимы, иначе пару (qi; qj) удалить из множества пар неотличимых состояний ( из левого столбца таблицы)";
в результате анализа можно установить, что совместимыми парами являются (qp; qv), (qr; qs), (qs; qu), (qp; qt) и (qr; qu).
шаг 5: на множестве пар совместимых состояний найти классы совместимых состояний:
"а) если множеству совместимых пар принадлежат пары (qi; qj), (qj; qk) и (qi; qk), то по условию транзитивности формируют класс совместимых состояний Q'i={qi; qj; qk..};
b) если множеству совместимых пар принадлежат (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}.
шаг 6: найти наименьшее множество совместимых классов, покрывающих все исходные состояния автомата: (Q'2Q'4Q'5) = {qp; qr; qs; qt; qu; qv}.
шаг 7: на множестве классов совместимых состояний, выбранных на шаге 6, найти согласованные состояния:
"если для любого класса наименьшего множества совместимых состояний и любых его элементов qi и qj значения функций переходов (qi; xk) и (qj; xk) принадлежат одному совместимому классу для всех символов xkX, то такие классы являются согласованными и следует перейти к шагу 8, иначе перейти к шагу 6 и найти другое наименьшее множество классов совместимых состояний, покрывающее все исходные состояния автомата";
в результате анализа таблицы 6.23 установлено, что все состояния согласованы в минимальном наборе классов совместимых состояний Q'2, Q'4, Q'5;
шаг 8: состояния каждого класса согласованных состояний заместить эквивалентным состоянием: q'1{qp; qt}, q'2{qp; qv}, q'3{qu; qv}, q'4{qr; qs} и q'5{qs; qu}; отличимые состояния сохраняют свое значение в описании минимального автомат; составить таблицы переходов и выходов.
Пример: дан недетерминированный автомат M = X; Y; Q; ; , где X={x1; x2; x3; x4}, Y={0; 1}, Q={q1; q2; q3; q4; q5}, функции и заданы таблицей. Найти минимальный автомат.
Множество неотличимых пар: (q1; q2), (q1; q3), (q1; q4)), (q1; q5), (q2; q3), (q2; q4), (q3; q4), (q3; q5), (q4; q5). Классы неотличимых состояний:Q’1={q1; q2; q3; q4} и Q’2={q1; q3; q4; q5}. |
|
текущие сост-я |
xX |
|||
|
x1 |
x2 |
x3 |
x4 |
||
|
q1 |
q2; 0 |
* ; * |
q3; * |
q2; * |
|
|
q2 |
q3; 0 |
q5; 1 |
q2; 0 |
* ; * |
|
|
q3 |
q3; 0 |
q4; 1 |
* ; * |
q5; 0 |
|
|
q4 |
* ; * |
q1; 1 |
q2; * |
* ; * |
|
|
q5 |
* ; * |
* ; * |
q1;1 |
* ; * |
|
.
Анализ таблицы а) пока- зывает, что для символа "x4" пара неотличимых состояний (q1; q3) перехо- дит в пару отличимых состояний (q2; q5); следовательно, пара (q1; q3) не претен- дует на совместимость, ее следует удалить и составить новую таблицу b).
|
|
Таблица а) |
||||
|
Неотл-е сост-я |
xX |
||||
|
x1 |
x2 |
x3 |
x4 |
||
|
(q1; q2) |
(q2; q3) |
* |
(q2; q3) |
* |
|
|
(q1; q3) |
(q2; q3) |
* |
* |
(q2; q5) |
|
|
(q1; q4) |
* |
* |
(q2; q3) |
* |
|
|
(q1; q5) |
* |
* |
(q1; q3) |
* |
|
|
(q2; q3) |
(q3; q3) |
(q4; q5) |
* |
* |
|
|
(q2; q4) |
* |
(q1; q5) |
(q2; q2) |
* |
|
|
(q3; q4) |
* |
(q1; q4) |
* |
* |
|
|
(q3; q5) |
* |
* |
* |
* |
|
|
(q4; q5) |
* |
* |
(q1; q2) |
* |
|
|
|
Таблица b) |
||||
Анализ таблицы b) показы- вает, что для символа "x2" пара неотличимых состоя- ний (q2; q4) переходит в пару отличимых состояний (q1; q5); следовательно, (q2; q4) не претендует на совместимость, ее следует удалить и составить таблицу c). |
|
Неотл-е сост-я |
xX |
|||
|
x1 |
x2 |
x3 |
x4 |
||
|
(q1;q2) |
(q2;q3) |
* |
(q2;q3) |
* |
|
|
(q1;q4) |
* |
* |
(q2;q3) |
* |
|
|
(q2;q3) |
(q3;q3) |
(q4;q5) |
* |
* |
|
|
(q2;q4) |
* |
(q1;q5) |
(q2;q2) |
* |
|
|
(q3;q4) |
* |
(q1;q4) |
* |
* |
|
|
(q3;q5) |
* |
* |
* |
* |
|
|
(q4;q5) |
* |
* |
(q1;q2) |
* |
|
|
|
Таблица c) |
||||
Анализ таблицы c) пока- зывает, что для символа "x2" пара неотличимых состояний (q2; q4) перехо- дит в удаленную пару (q1; q5); следовательно, пару (q2; q4) следует удалить и составить таблицу d).
|
|
Неотл-е сост-я |
xX |
|||
|
x1 |
x2 |
x3 |
x4 |
||
|
(q1;q2) |
(q2;q3) |
* |
(q2;q3) |
* |
|
|
(q1;q4) |
* |
* |
(q2;q3) |
* |
|
|
(q2;q3) |
(q3;q3) |
(q4;q5) |
* |
* |
|
|
(q3;q4) |
* |
(q1;q4) |
* |
* |
|
|
(q3;q5) |
* |
* |
* |
* |
|
|
(q4;q5) |
* |
* |
(q1;q2) |
* |
|
|
|
Таблица d) |
||||
Анализ таблицы d) показы- вает, что для всех символов входного алфавита пары неотличимых состояний переходят в пары неотли- чимых состояний; cледова- тельно, в левом столбце остались пары совмести- мых состояний..
|
|
Неотл-е сост-я |
xX |
|||
|
x1 |
x2 |
x3 |
x4 |
||
|
(q1; q2) |
(q2; q3) |
* |
(q2; q3) |
* |
|
|
(q1; q4) |
* |
* |
(q2; q3) |
* |
|
|
(q2; q3) |
(q3; q3) |
(q4; q5) |
* |
* |
|
|
(q3; q4) |
* |
(q1; q4) |
* |
* |
|
|
(q3; q5) |
* |
* |
* |
* |
|
|
(q4; q5) |
* |
* |
(q1; q2) |
* |
|
Проверим согласование на различных наборах классов совместимых состояний:
а) пусть Q''1={q1; q2} и Q''4={q3; q4; q5}.
Таблица е). |
||||
Классы состояний |
xX |
|||
x1 |
x2 |
x3 |
x4 |
|
Q''1 |
Q''1; Q''4 |
* |
Q''1; Q''4 |
* |
Q''4 |
* |
Q''1; Q''4 |
Q''1 |
* |
Анализ показывает, что выбранные классы не согласованы, так как для x1 и x3 класс совместимых состояний Q''1 переходит в различные классы Q''1 и Q''4.
b) пусть Q''1={q1; q2}, Q''2={q1; q4} и Q''41={q3;q5}.
Таблица f) |
||||
Классы состояний |
xX |
|||
x1 |
x2 |
x3 |
x4 |
|
Q''1 |
Q''1;Q''41 |
* |
Q''1;Q''41 |
* |
Q''2 |
* |
* |
Q''1;Q''41 |
* |
Q''41 |
* |
* |
* |
* |
Анализ показывает, что выбранные классы также не согласованы, так как для x1 и x3 класс совместимых состояний Q''1 переходит в различные классы Q''1 и Q''41.
c) пусть Q''1={q1; q2}, Q''3={q2; q3} и Q''42={q4; q5}.
Таблица g) |
||||
Классы состояний |
xX |
|||
x1 |
x2 |
x3 |
x4 |
|
Q''1 |
Q''3 |
* |
Q''3 |
* |
Q''3 |
Q''3 |
Q''42 |
* |
* |
Q''42 |
* |
* |
Q''1 |
* |
Анализ показывает, что выбранные классы согласованы, так как для любого символа все классы совместимых состояний переходят в один класс совместимых состояний.
Введем обозначения состояний, замещающих согласованные классы: q'1{q1; q2}, q'2{q2; q3}, q'3{q4; q5}.
Таблица h) |
||||
текущее состояние |
xX |
|||
x1 |
x2 |
x3 |
x4 |
|
q'1 |
q'2; 0 |
q'3; 1 |
q'2; 0 |
q'1; * |
q'2 |
q'2; 0 |
q'3; 1 |
q'1; 0 |
q'3;0 |
q'3 |
* ; * |
q'1; 1 |
q'1; 1 |
* ; * |
Для проверки эквивалентности автоматов подадим на вход каждого из них одинаковую последовательность символов:
а) пусть = (x1x2x3x4)
для исходного автомата: для минимального автомата:
вход: x1- x2- x3- x4; вход: x1- x2- x3- x4;
q: q1- q2- q5- q1- q2; q: q'1-q'2- q'3- q'1 - q'1;
выход: 0- 1- 1- *; выход: 0- 1- 1- *;
то есть =(011*). то есть =(011*).
b) пусть = (x4x3x2x1)
для исходного автомата: для минимального автомата:
вход: x4- x3- x2- x1; вход: x4- x3- x2- x1;
q: q1- q2- q2- q5- *; q: q'1- q'1- q'2- q'3- *;
выход: *- 0- 1- *; выход: *- 0 -1- *;
то есть = (*01*). то есть = (*01*).
Так подтверждается эквивалентность исходного и минимального недетерминированных автоматов.