Общие условия выбора системы дренажа: Система дренажа выбирается в зависимости от характера защищаемого...
Археология об основании Рима: Новые раскопки проясняют и такой острый дискуссионный вопрос, как дата самого возникновения Рима...
Топ:
Оснащения врачебно-сестринской бригады.
Установка замедленного коксования: Чем выше температура и ниже давление, тем место разрыва углеродной цепи всё больше смещается к её концу и значительно возрастает...
Когда производится ограждение поезда, остановившегося на перегоне: Во всех случаях немедленно должно быть ограждено место препятствия для движения поездов на смежном пути двухпутного...
Интересное:
Лечение прогрессирующих форм рака: Одним из наиболее важных достижений экспериментальной химиотерапии опухолей, начатой в 60-х и реализованной в 70-х годах, является...
Искусственное повышение поверхности территории: Варианты искусственного повышения поверхности территории необходимо выбирать на основе анализа следующих характеристик защищаемой территории...
Принципы управления денежными потоками: одним из методов контроля за состоянием денежной наличности является...
Дисциплины:
2017-11-22 | 314 |
5.00
из
|
Заказать работу |
|
|
Два состояния qi и qj называются эквивалентными, если выполняется равенство: S (qi, a) = S (qj, a) для произвольного a.
В простейшем случае, когда входящее слово состоит из одной буквы, эквивалентность имеет вид: l (qi,a) = l (qj,a)
Множестваво всех эквивалентных состояниях называются классом эквивалентности К.
Допустим qi и qj принадлежит классу К0,сформируем слово a следующим образом a = а0а1, тогда согласно определению эквивалентности мы можем записать.
S (qi, а0, а1) = S (qj, а0, а1)
Полученное равенство запишем в ином виде:
l (qi, а0 ) l (qi, а0, а1) = l (qj, а0 ) l (qj, а0, а1)
Исходя из определения эквивалентности: выполняется равенство:
l (qi, а0 ) = l (qj, а0 ),
а значит выполняется и равенство:
l (qi, а0, а1) = l (qj, а0, a1 )
Преобразовав получим равенство:
l (d (qi, а0), а1) = l (d (qj, а0), а1)
Для того, чтобы две составляющие qi и qj были эквивалентны, должны выполнятся следующие условия:
l (qi, а) = l (qj, а)
d (qi, а) = d (qj, а) Î K
Используя свойства эквивалентных состояний, множество сост. заданного автомата всегда может быть разбито на соответствующие классы эквивалентности.
Рассмотрим следующий пример:
Автомат задан графом вида:
А = {0, 1}; V = {0, 1}
Q = { q1, q2, q3, q4, q5, q6, q7 }
q2 q6
q1 q4 q7
q3 q5
Составим таблицы выходов и функции перехода:
l | q1 | q2 | q3 | q4 | q5 | q6 | q7 |
d | q1 | q2 | q3 | q4 | q5 | q6 | q7 |
q2 | q5 | q7 | q1 | q5 | q4 | q5 | |
q3 | q6 | q4 | q3 | q6 | q7 | q6 |
Используя два условия эквивалентности разобьем множество сост. автоматов на классы эквивалентности:
1. Получение класса условно эквивалентных сост. (проверяем условие выполнения первого равенства). Используя таблицу выходов мы можем записать два условно эквивалентных класса.
|
к0 = {q1 q2 q5}
к1 = {q3 q4 q6 q7}
2. Проверка эквивалентности полученных классов:
d | q1 | q2 | q3 | q4 | q5 | q6 | q7 |
к0 | к0 | к1 | к0 | к0 | к1 | к0 | |
к1 | к1 | к1 | к1 | к1 | к1 | к1 |
На основании полученной таблицы и второго условия эквивалентности
делаем вывод: класс к1 распадается на два класса:
к1, = {q3 q6} к1” = { q4 q7}
3. С учетом нового разбиения на классы опять заполняется таблмца перехода:
d | q1 | q2 | q3 | q4 | q5 | q6 | q7 |
к0 | к0 | к1” | к0 | к0 | к1” | к0 | |
к1’ | к1’ | к0 | к1’ | к1’ | к1” | к1’ |
В результате решения задачи получены три класса эквивалентности:
к0 = { q1, q2, q5}
к1’ = { q3 q6}
к1” = { q4 q7}
Для проверки подадим на вход последовательность:
q1 | q2 | q6 | q7 | q6 | q4 | q3 | q4 | q1 | q2 | |
a | ||||||||||
w |
q5 | q3 | q6 | q7 | q6 | q4 | q3 | q4 | q1 | q2 | |
a | ||||||||||
w |
Автоматы S и Т называются эквивалентными, если любому сост. автомата S найдется сост. автомата Т. (и наоборот)
Если автомат S0 эквивалентен автомату S и количество сост. S0 > S, то S0 – минимальный автомат (единственный).
Построим мин. автомат S0 для нашего примера:
q01 ® k0 q02 ® k1’ q03 ® k1”
q02
q01
q03
l0 | q01 | q02 | q03 |
d | q01 | q02 | q03 |
q01 | q03 | q01 | |
q02 | q03 | q02 |
РЕАЛИЗАЦИЯ КА.
КА состоит из двух остальных блоков:
1. реализует функцию переходов;
2. реализует функцию выходов.
t
qi d (qi, aj)
aj
qi
aj aj l (qi, aj) vk
В этой схеме используют устройство, реализующее задержку перехода автомата в новое состояние на время t.
Если t одинаково для любых состояний, то автомат синхронный, иначе асинхронный.
Блок функций выходов и переходовмогут быть реализованы комбинаторными системами.
|
|
Эмиссия газов от очистных сооружений канализации: В последние годы внимание мирового сообщества сосредоточено на экологических проблемах...
Опора деревянной одностоечной и способы укрепление угловых опор: Опоры ВЛ - конструкции, предназначенные для поддерживания проводов на необходимой высоте над землей, водой...
Индивидуальные и групповые автопоилки: для животных. Схемы и конструкции...
Историки об Елизавете Петровне: Елизавета попала между двумя встречными культурными течениями, воспитывалась среди новых европейских веяний и преданий...
© cyberpedia.su 2017-2024 - Не является автором материалов. Исключительное право сохранено за автором текста.
Если вы не хотите, чтобы данный материал был у нас на сайте, перейдите по ссылке: Нарушение авторских прав. Мы поможем в написании вашей работы!