|
|||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[25] Автомат М называется самонастраивающимся, если существует такое натуральное число щ, что для любого входного слова ап, где п>по, апеХ* любых начальных состояний Sj, steS имеетместо v(s0,ocn)z=v(Sj,an), т.е. в самонастраивающимся автомате выходная буква у в любой такт h>no не зависит от начального состояния. Граф такого автомата для щ=3 показан на рис. 3.4. Автомат называется автоматом без потери информации, если для любого состояния seS vl двух любых различных слов ап и сх2п:а!п, о?пеХ одинаковой длины выходные слова различны, т.е. v(s,d1 nfvisy). Автомат M]={X],Si,Y],if/i,V]} называется подавтоматом автомата M={X,S,Y,y/,Vi}, если подавтомат имеет подмножество состояний исходного автомата и в соответствующих состояниях перерабатывает входные слова в те же слова состояний и выходные слова, что и исходный автомат, т.е. выполняется: Рис.3.4. Граф самонастраивающегося автомата S<SA y/1(s,x) = y/(s,x) х < X J Vj (s, x) = v(s, x) На рис.3.5 изображен граф автоматаМ, анарис.3.6 его подавтоматМ}. (3.7) 3.8. АНАЛИЗ КОНЕЧНЫХ АВТОМАТОВ Анализ конечных автоматов заключается в определении последовательности выходных сигналов при возбуждении их в тактовые моменты времени некоторой последовательностью входных сигналов. Входная и выходная последовательности представляются наборами символов (или их номеров) из алфавитов Хи Y одинаковой длины. Для такого описания, кроме функций выходов и переходов, необходимо определить или задать начальное состояние автомата [2]. Наиболее удобно определять реакцию автомата на входную последовательность по его графу. Для этого достаточно проследить путь в графе, начиная от вершины начального состояния, по направлению дуг, которые отмечены очередными номерами из входной последовательности. Выходная последовательность определяется номерами, которыми отмечены дуги в порядке их следования по пройденному пути, а последовательность состояний автомата - номерами вершин, через которые проходит этот путь. С помощью графа автомата легко выделить следующие характерные типы его состояний: -преходящее состояние, из которого можно перейти, по крайней мере в одно другое состояние, но после этого уже нельзя возвратиться в него ни при каком воздействии, т.е. соответствующая вершина не имеет заходящих дуг, но имеет хотя бы одну исходящую дугу; -тупиковое состояние, в которое можно перейти, по крайней мере из одного состояния, но после этого уже нельзя выйти из него ни при каком воздействии, т.е. соответствующая вершина не имеет исходящих дуг в другие вершины, но имеет хотя бы одну, входящую из другой вершины; - изолированное состояние, из которого нельзя перейти ни в какое другое состояние и в него нельзя попасть ни из какого другого состояния ,т.е. соответствующая вершина содержит только петлю. Аналогичные определения можно дать и для некоторых совокупностей состояний, рассматриваемых как подавтоматы. Если начальное состояние автомата М принадлежит непустому множеству S состояний, которое составляет тупиковый или изолированный подавтомат, то М можно упростить, исключив все состояния, которые не принадлежат множеству S и всех дуг, начинающихся в этих состояниях. Пусть М], М2, М3 - соответственно преходящий , тупиковый и изолированный подавтоматы, составляющие автомат М, обобщенный граф которого показан на рис.3.7. Подавтоматы Mh М2, М3 характеризуются множествами состояний Si, S2, S3. Очевидно, выделение таких подавтоматов соответствует разбиению множества S состояний автомата М на непересекающиеся подмножества S}, S2, S3 и представляющие собой классы эквивалентности (S1\JS2\JS3=S, Sif)S2nS3=0). Как следует из обобщенного графа (см. рис.3.7), матрица соединений автомата может быть представлена в виде Рис.3.7. Обобщенный граф конечного автомата М =
(3.8) где jUjj - матрица подавтомата М}; состояний преходящего /л]2 - матрица, характеризующая переход от автомата М] к состояниям тупикового автомата М2, >и22 - матрица подавтомата М2 /и33 - матрица подавтомата М3. Отсюда следует, что разделение автомата М на подавтоматы М], М2, М3 можно осуществить преобразованием его матрицы соединений к стандартному виду путем перестановки соответствующих строк и столбцов. Эта операция достаточно легко формализуется и может быть выполнена с помощью ЭВМ. |
Среды: Smalltalk80 MicroCap Local bus Bios Pci 12С ML Микроконтроллеры: Atmel Intel Holtek AVR MSP430 Microchip Книги: Емкостный датчик 500 схем для радиолюбителей часть 2 (4) Структура компьютерных программ Автоматическая коммутация Кондиционирование и вентиляция Ошибки при монтаже Схемы звуковоспроизведения Дроссели для питания Блоки питания Детекторы перемещения Теория электропривода Адаптивное управление Измерение параметров Печатная плата pcad pcb Физика цвета Управлении софтверными проектами Математический аппарат Битовые строки Микроконтроллер nios Команды управления выполнением программы Перехода от ahdl к vhdl Холодный спай Усилители hi-fi Электронные часы Сердечники из распылённого железа Анализ алгоритмов 8-разрядные КМОП Классификация МПК История Устройства автоматики Системы и сети Частотность Справочник микросхем Вторичного электропитания Типы видеомониторов Радиобиблиотека Электронные системы Бесконтекстный язык Управление техническими системами Монтаж печатных плат Работа с коммуникациями Создание библиотечного компонента Нейрокомпьютерная техника Parser Пи-регулятор ч.1 ПИ-регулятор ч.2 Обработка списков Интегральные схемы Шина ISAВ Шина PCI Прикладная криптография Нетематическое: Взрывной автогидролиз Нечеткая логика Бытовые установки (укр) Автоматизация проектирования Сбор и защита Дискретная математика Kb радиостанция Энергетика Ретро: Прием в автомобиле Управление шаговым двигателем Магнитная запись Ремонт микроволновки Дискретные системы часть 2 | |||||||||