Выбрать книгу по жанру
Фантастика и фэнтези
- Боевая фантастика
- Героическая фантастика
- Городское фэнтези
- Готический роман
- Детективная фантастика
- Ироническая фантастика
- Ироническое фэнтези
- Историческое фэнтези
- Киберпанк
- Космическая фантастика
- Космоопера
- ЛитРПГ
- Мистика
- Научная фантастика
- Ненаучная фантастика
- Попаданцы
- Постапокалипсис
- Сказочная фантастика
- Социально-философская фантастика
- Стимпанк
- Технофэнтези
- Ужасы и мистика
- Фантастика: прочее
- Фэнтези
- Эпическая фантастика
- Юмористическая фантастика
- Юмористическое фэнтези
- Альтернативная история
Детективы и триллеры
- Боевики
- Дамский детективный роман
- Иронические детективы
- Исторические детективы
- Классические детективы
- Криминальные детективы
- Крутой детектив
- Маньяки
- Медицинский триллер
- Политические детективы
- Полицейские детективы
- Прочие Детективы
- Триллеры
- Шпионские детективы
Проза
- Афоризмы
- Военная проза
- Историческая проза
- Классическая проза
- Контркультура
- Магический реализм
- Новелла
- Повесть
- Проза прочее
- Рассказ
- Роман
- Русская классическая проза
- Семейный роман/Семейная сага
- Сентиментальная проза
- Советская классическая проза
- Современная проза
- Эпистолярная проза
- Эссе, очерк, этюд, набросок
- Феерия
Любовные романы
- Исторические любовные романы
- Короткие любовные романы
- Любовно-фантастические романы
- Остросюжетные любовные романы
- Порно
- Прочие любовные романы
- Слеш
- Современные любовные романы
- Эротика
- Фемслеш
Приключения
- Вестерны
- Исторические приключения
- Морские приключения
- Приключения про индейцев
- Природа и животные
- Прочие приключения
- Путешествия и география
Детские
- Детская образовательная литература
- Детская проза
- Детская фантастика
- Детские остросюжетные
- Детские приключения
- Детские стихи
- Детский фольклор
- Книга-игра
- Прочая детская литература
- Сказки
Поэзия и драматургия
- Басни
- Верлибры
- Визуальная поэзия
- В стихах
- Драматургия
- Лирика
- Палиндромы
- Песенная поэзия
- Поэзия
- Экспериментальная поэзия
- Эпическая поэзия
Старинная литература
- Античная литература
- Древневосточная литература
- Древнерусская литература
- Европейская старинная литература
- Мифы. Легенды. Эпос
- Прочая старинная литература
Научно-образовательная
- Альтернативная медицина
- Астрономия и космос
- Биология
- Биофизика
- Биохимия
- Ботаника
- Ветеринария
- Военная история
- Геология и география
- Государство и право
- Детская психология
- Зоология
- Иностранные языки
- История
- Культурология
- Литературоведение
- Математика
- Медицина
- Обществознание
- Органическая химия
- Педагогика
- Политика
- Прочая научная литература
- Психология
- Психотерапия и консультирование
- Религиоведение
- Рефераты
- Секс и семейная психология
- Технические науки
- Учебники
- Физика
- Физическая химия
- Философия
- Химия
- Шпаргалки
- Экология
- Юриспруденция
- Языкознание
- Аналитическая химия
Компьютеры и интернет
- Базы данных
- Интернет
- Компьютерное «железо»
- ОС и сети
- Программирование
- Программное обеспечение
- Прочая компьютерная литература
Справочная литература
Документальная литература
- Биографии и мемуары
- Военная документалистика
- Искусство и Дизайн
- Критика
- Научпоп
- Прочая документальная литература
- Публицистика
Религия и духовность
- Астрология
- Индуизм
- Православие
- Протестантизм
- Прочая религиозная литература
- Религия
- Самосовершенствование
- Христианство
- Эзотерика
- Язычество
- Хиромантия
Юмор
Дом и семья
- Домашние животные
- Здоровье и красота
- Кулинария
- Прочее домоводство
- Развлечения
- Сад и огород
- Сделай сам
- Спорт
- Хобби и ремесла
- Эротика и секс
Деловая литература
- Банковское дело
- Внешнеэкономическая деятельность
- Деловая литература
- Делопроизводство
- Корпоративная культура
- Личные финансы
- Малый бизнес
- Маркетинг, PR, реклама
- О бизнесе популярно
- Поиск работы, карьера
- Торговля
- Управление, подбор персонала
- Ценные бумаги, инвестиции
- Экономика
Жанр не определен
Техника
Прочее
Драматургия
Фольклор
Военное дело
Математический аппарат инженера - Сигорский Виталий Петрович - Страница 30
6. Синтез конечных автоматов. Реализация конечных автоматов сводится к синтезу соответствующей комбинационной схемы, преобразующей входные переменные x(ν) и s(ν) в выходные переменные y(ν) и s(ν + 1) в соответствии с заданными характеристическими функциями s(ν + 1) = δ (x(ν), s(ν)) и y(ν)= λ (x(ν), s(ν)). Для сохранения состояний s(ν + 1) до следующего такта в цепь обратной связи вводится необходимое количество элементов памяти.
При реализации автоматов в двоичном структурном алфавите можно использовать рассмотренные ранее методы синтеза
- 571 -
комбинационных схем. Но для этого необходимо закодировать состояния схемы н представить характеристические функции в виде булевых функций двоичных переменных. Такое кодирование можно осуществить преобразованием общей таблицы перехода автомата к таблице соответствия в двоичном структурном алфавите. Если элементы множеств X, Y и S пронумерованы порядковыми числами, начиная с нуля, то им соответствуют коды, представляющие собой двоичные эквиваленты этих чисел. Например, для автомата, заданного в (4), таблицу переходов можно преобразовать к виду:
Заменяя десятичные числа их двоичными эквивалентами, читаемыми сверху вниз, получаем таблицу соответствия, в которой значения функций s(ν + 1) и у(ν) представлены двоичными кодами:
Рис. 239. Структурная схема конечного автомата
Отсюда видно, что комбинационная схема должна иметь четыре входа, соответствующие входным переменным x1(ν), х2(ν) и переменным состояния s(ν), s2(ν), а также три выхода, соответствующие переменным состояния s1(ν + 1), s2(ν + 1) и выходной переменной у1(ν). Синтезировав комбинационную схему, соответствующую полученной таблице и введя два элемента задержки З1 и З2, получим структурную схему автомата (рис. 239).
7. Минимизация автоматов. С утилитарной точки зрения интерес представляет только зависимость между входами и выходами автомата, а роль его состоянии сводится исключительно к участию в формировании этих зависимостей в качестве промежуточных переменных. Следовательно, любая совокупность состояний, обеспечивающая требуемые зависимости между входом и выходом, может быть выбрана в качестве множества состоянии автомата. В то же
- 572 -
время этот выбор естественно подчинить определенным целям, например, минимизации числа состояний или оптимизации автомата в каком-либо смысле. Следует иметь в виду, что с уменьшением числа состоянии уменьшается и количество требуемых элементов памяти, но это может привести к усложнению комбинационной схемы автомата. Поэтому синтез наиболее экономичного автомата часто требует поиска удачного компромисса между сложностью его комбинационной и запоминающих частей.
Рис. 240. Граф конечного автомата (а) и его сокращенная форма (б)
Минимизация числа состоянии полных автоматов связана с отношением эквивалентности. Пусть автоматы М1 и М2, находящиеся соответственно в начальных состояниях, σi и σj (обозначения М1 и М2 могут относиться к одному и тому же автомату), под воздействием любой входной последовательности выдают одинаковые выходные последовательности, т. е. автоматы М1 и М2 в данных состояниях σi и σj неразличимы по внешним выходам. Такое отношение между состояниями одного и того же или двух различных автоматов обладает свойствами рефлексивности, симметричности и транзитивности, следовательно, оно является отношением эквивалентности состояний. Если состояния не эквивалентны, то их называют различимыми. Легко доказать справедливость следующих положений:
1) состояния σi и σj автомата явно различимы, если различаются соответствующие, им строки в таблице выходов;
2) состояния σi и σj автомата явно эквививалентны, если соответствующие им строки в таблице переходов и таблице выходов одинаковы или становятся одинаковыми при замене каждого номера σi на номер σj (или наоборот).
Например, для автомата, граф которого изображен на рис. 240, а, общая таблица переходов имеет вид:
- 573 -
Из этой таблицы следует, что состояния из множества {0, 3, 4}являются явно различимыми с любым состоянием из множества {1, 2, 5, 6}. Поэтому следует искать эквивалентные состояния только среди элементов, принадлежащих одному из этих множеств. Так как строки 0 и 4 одинаковы, а строки 1 и 5 становятся одинаковыми при замене цифры в числителе 1 на 5 (или 5 на 1), то явно эквивалентными являются пары состояний {0,4} И {1,5}.
Объединяя эквивалентные состояния в автомате М1, получаем эквивалентный автомат М2 с меньшим числом состоянии, который в любом состоянии нельзя отличить от исходного, наблюдая сигналы на выходах. Очевидно, автоматы М1 и М2 являются эквивалентными, если каждому состоянию σi , автомата М1 соответствует, по крайней мере, одно эквивалентное ему состояние автомата M2, и если каждому состоянию σj , автомата М2 соответствует хотя бы одно эквивалентное ему состояние автомата М1.
Эквивалентные состояния, например, σi и σj , удобно объединять по общей таблице переходов, вычеркивая строку σj , и заменяя везде в числителе числа σj на σi . После объединения пар явно эквивалентных состояний может оказаться возможным снова обнаружить такие состояния, которые также объединяются с помощью аналогичной процедуры. В результате последовательного объединения приходим к сокращенной таблице переходов, которой соответствует сокращенный автомат, эквивалентный исходному, но имеющий меньшее число состоянии. Так, для рассматриваемого примера получаем последовательно:
- 574 -
Первая таблица соответствует объединению пар эквивалентных состоянии {0,4} и {1, 5}, а вторая - объединению пары {2, 6}. Сокращенный автомат содержит только четыре состояния (рис.240, б).
8. Эквивалентное разбиение. Если известны все пары эквивалентных состояний конечного автомата, то тем самым на множестве S его состояний определено отношение эквивалентности, которому соответствует некоторое разбиение на классы эквивалентности S = {S1, S2 ..., Sν}. При этом состояние, не имеющее эквивалентного ему состояния, составляет класс эквивалентности, единственным элементом которого является это состояние. Обозначим через σ'0, σ'1, ..., σ'ν представители классов эквивалентности и через М' – автомат, множеством состояний которого является семейство представителей S' = {σ'0, σ'1, ..., σ'ν}. Можно утверждать, что автоматы М и М' эквивалентны (М ~ М'), причем М' имеет минимальное число состояний, т. е. является минцмальной формой автомата.
- Предыдущая
- 30/32
- Следующая