2. Алгоритъм за минимизация на броя на състоянията на автомат на Мур.
1). Въвежда се понятие нулево еквивалентни състояния и разбиване на подкласове от нулево еквивалентни състояния .
Нулево еквивалентни състояния са тези, при които автоматът генерира едни и същи изходни реакции, намирайки се в тях.
2). Ако от две нулево еквивалентни състояния при еднакви входни въздействия автоматът преминава в еднакви подкласове нулево еквивалентни състояния, то те са първи еквивалентни.
Всичко по-нататък е сходно с горния алгоритъм.
Пример:
Въпроси:
1. Каква е основната идея, заложена в алгоритъма за минимизация , предложен от Ауфенкамп и Хон?
Задачи:
1. Минимизирайте броя на състоянията на автоматите, получени след преобразуванията от задачи 3 и 4 от предходната тема.
Автор: С. Иванов, Ю. Петкова, С. Каров
8. Структурен модел на автомата. Преход от абстрактен модел на автомата към структурен. Синтез на краен автомат
1999-03-18 15:28:11+02
1. Структурен модел на автомата.
След етапа на абстрактния синтез, заключаващ се в минимизация на броя на състоянията, следва етап на структурен синтез. Целта на този синтез е да се построи логическа схема, реализираща функциите на автомата, осъществена с определен тип логически елементи[5,11,12].
Ако абстрактният модел беше само математически модел на дискретна система, то в структурния автомат се отчита характера на входните и изходните сигнали на автомата, а също и вътрешното решение на ниво структурна схема.
Със структурен синтез се занимава структурната теория на автоматите, чиято основна задача е намиране на общи принципи за построяване на структурните схеми на автомата на базата на предварително известни елементарни автомати и типове логически елементи.
А ко абстрактният автомат се задава с множество от шест елемента (фиг.8.1.), то при прехода към структурен автомат (фиг.8.2.) вместо множество от входни въздействия Z има входни сигнали x1,x2,...,xn, които приемат стойности “0” или “1”. Вместо изходна реакция W в структурния модел има изходни сигнали y1,y2,...,ym, приемащи стойност “0” или “1”. Входните и изходните сигнали трябва да са определени като брой и логически нива, като се има предвид и обекта, който ще бъде управляван от автомата.
Вътрешната структура на автомата (фиг.8.3.а) е изградена от памет, в която се съхраняват състоянията A={a1...ak} и комбинационна схема, която реализира функцията на преходите и функцията на изходите или .
Условно комбинационната схема може да се раздели на две части - първата (КС1), реализираща функцията на преходите чрез генериране на т.нар. функции на възбуждане на паметта и втората (КС2), реализираща функцията на изходите (фиг.8.3.б).Това разделяне е условно и се прави с цел по-лесно усвояване на синтеза на структурния автомат.
Съществуват няколко метода за синтез на структурен автомат.
Сподели с приятели: |
