|
|||||||||||||||||||||||||||||
Меню:
Главная
Форум
Литература: Программирование и ремонт Импульсные блоки питания Неисправности и замена Радиоэлектронная аппаратура Микросхема в ТА Рубрикатор ТА Кабельные линии Обмотки и изоляция Радиоаппаратура Гибкие диски часть 2 часть 3 часть 4 часть 5 Ремонт компьютера часть 2 Аналитика: Монтаж Справочник Электроника Мощные высокочастотные транзисторы 200 микросхем Полупроводники ч.1 Часть 2 Алгоритмические проблемы 500 микросхем 500 микросхем Сортировка и поиск Монады Передача сигнала Электроника Прием сигнала Телевидиние Проектирование Эвм Оптимизация Автомобильная электроника Поляковтрансиверы Форт Тензодатчик Силовые полевые транзисторы Распределение частот Резисторные и термопарные Оберон Открытые системы шифрования Удк |
[28] v(sj,x) = v(Sj,x) \/x eX . При этом пишут st Ej sj или (Si,Sj) gG(Ei). В том случае, если sh Sj неэквивалентны, записывают st Er Sj либо Si E sj, либо Si Ej Sj и соответственно (sb Sj) e G( Er), (sit Sj) e G( E), (st, sj) e G(E}) и т.д. Очевидно, что здесь и в общем случае отношение эквивалентности и неэквивалентности образуют при : -объединении все множество S*S, т.е. G(Er){jG( Er)=S*S; -пересечении нулевое множество, т.е. G(Er) f] G( Er) = 0; -взаимно дополняют друг друга до множества S*S, т.е. G( Ёг) = S*S \ G(Er). Для примера рассмотрим эквивалентные и неэквивалентные состояния, их графики и первое разбиение на классы эквивалентности для автомата, заданного общей таблицей переходов-таблица 3.8 Таблица 3-8 Общая таблица переходов
Для указанного автомата имеем : X = Y={0,1} , S = {s0,Sj,s2j . Из таблицы 3.8 видно, что состояния s0 и s2 1-эквивалентны, т.к. v(s0,0)=v(s2,0) = 0] v(s0,l)=v(s2,l) = l J При этом график 1-эквивалентности имеет вид G(E1) = {(s0,s2),(s2,s0),(s0,s0),(s1,s1),(s2,s2)} , а график 1 -неэквивалентности найдется как G(E1) = {(s0,s1),(sI,s0),(s1,s2),(s2,sI)} , и в него войдут все пары состояний, не попавшие в G(E1) [4]. 3.12. МИНИМИЗАЦИЯ КОНЕЧНЫХ АВТОМАТОВ С практической точки зрения при функционировании автомата представляет интерес только зависимость между входами и выходами автомата, а роль его состояний сводится исключительно к участию в формировании этих зависимостей в качестве промежуточных переменных. Следовательно, любая совокупность состояний, обеспечивающая требуемые зависимости между входом и выходом, может быть выбрана в качестве множества состояний автомата. В то же время этот выбор естественно подчинить определенным целям, например, минимизации числа состояний, что уменьшает количество требуемых элементов памяти, однако может привести к усложнению комбинационной схемы автомата. Задача минимизации количества состояний в полностью описанном автомате сводится к определению попарно эквивалентных состояний и последующему их объединению. Так, для автомата, заданного таблицей переходов (см. таблицу 3.8), состояния s0 и s2 являются эквивалентными и объединяются в одно, например s0 ,при этом общая таблица переходов принимает вид табл.3.9, а исходный граф автомата, изображенный на рис.3.12, преобразуется к виду, показанному на рис.3.13. Таблица 3.9 Общая таблица переходов
Рис.3.12. Граф исходного автоматаРис.3.13. Граф эквивалентного автомата Однако все эквивалентные состояния автомата не исчерпываются 1-эквивалентностью, поэтому для их выявления требуется более сложная, чем рассмотренная выше, процедура. Оказывается, что в этом случае эффективнее всего начать с выявления неэквивалентных состояний, после определения которых легко находятся эквивалентные состояния, как дополнение к множеству неэквивалентных состояний до полного множества внутренних состояний автомата, т.е. G(E) = fS*S)\G(E) . Здесь приобретают важное значение следующие теоремы: Теорема 1. Состояние si, и sj, эквивалентные относительно всех входных слов длины г-7, могут стать неэквивалентными относительно слов длины г только тогда, когда имеется символ хк, где k<r, переводящий sh Sj соответственно в состояния se, sm, не эквивалентные относительно некоторого входного слова длины г-1. Это означает, что на г - м шаге достаточно исследовать состояние в г-1 графике эквивалентности G(Er.i) и установить, найдется ли там пара состояний (su Sj), переходящая в пару (se, s,,) со свойством se Er.i sm. В этом случае sh sj не эквивалентны (st Er Sj). Таким образом, условие теоремы можно записать следующим образом: SjEjSj, Vxr j еХ (y/(sitxK), y/(Sj,xK)) = (se,sm), хк eX,k<r, seEr jSm\ s.E.s, . (3.14) r j Теорема 2. Множество неэквивалентных пар состояний G( Ег) состоит из множества неэквивалентных пар G( Ег.}) и таких пар (suSj), что для некоторого символа хг входного слова длиной г имеем v(si, xr)*v(Sj, xr), т.е. v(st,хг)фу(Sj,xr), xr eX,=> stErSj G(Er) = G(Er ])[jsiErsJ. |
Среды: 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 | |||||||||||||||||||||||||||