Анализ и синтез на логически схеми
Изтегляне 1.14 Mb.
|
Свързани:
an-architectural-reassessment-of-a-villa-rustica-near-serdica, New Microsoft PowerPoint Presentation, кр цсх
- Навигация на страницата:
- 1999-03-18 15:20:11+02 1. Алгоритъм за минимизация на напълно определен автомат на Мили, предложен от Ауфенкамп и Хон[5].
| Въпроси и задачи:
1) Какви автоматни модели на последователностни схеми познавате? Какво е общото и какви са различията между тях? 2) Какви методи за задаване на абстрактните автомати познавате? 3) Каква е структурата на таблицата на преходите и на таблицата на изходите? 4) Как се задава абстрактен автомат с граф? Какви са разликите в задаването на автомат на Мили и автомат на Мур? 5) Защо изходната реакция на автомата на Мур се записва във възела на графа? 6) Каква е структурата на матрицата на преходите и изходите за двата модела автомати? 7) Кои автомати са еквивалентни? 8) На фиг.6.12. са дадени таблиците на преходите и изходите на автомат на Мили. Съставете графа на автомата. Представете автомата чрез матрица на преходите и изходите. 9) На фиг.6.13. е дадена таблицата на преходите и изходите на автомат на Мур. Съставете графа на автомата. Представете автомата чрез матрица на преходите и изходите. 10) Зададеният на фиг.6.14. таблично автомат на Мили преобразувайте в следната последователност: - в автомат на Мили - графично зададен; - в автомат на Мур - графично зададен; - в автомат на Мили - графично зададен; - в автомат на Мили - таблично зададен. На всеки етап на преобразуване доказвайте еквивалентност на автоматите. Сравнете първата и последната таблица на преходите и изходите и направете изводи. 11) Приложете горното условие към таблично зададените автомати от фиг.6.12. и фиг.6.13. Автор: С. Иванов, Ю. Петкова, С. Каров 7. Минимизация на напълно определени автомати1999-03-18 15:20:11+02 1. Алгоритъм за минимизация на напълно определен автомат на Мили, предложен от Ауфенкамп и Хон[5]. Основната идея на този метод се състои в разбиването на всичките състояния на изходния абстрактен автомат на взаимно непресичащи се класове от еквивалентни състояния и замяна на всеки клас от еквивалентни състояния с едно състояние. По този начин новополученият еквивалентен минимален автомат ще има толкова състояния, на колкото класа от еквивалентни състояния може да се разбие изходният автомат. - Две състояния на автомата am и as се наричат еквивалентни, ако , където a е произволна входна дума, т.е. намирайки се в кое да е състояние, при произволно входно въздействие автоматът генерира еднакви изходни реакции. Алгоритъм за минимизация на броя на състоянията. 1). Разбиване на множеството А на подкласове от първи, втори и т.н. класове от еквивалентни състояния, отбелязвани с и т.н. - Първи еквивалентни състояния - Ако автоматът се намира в някое от тези състояния, при еднакви входни въздействия генерира еднакви изходни реакции. Всички първи еквивалентни състояния образуват първи клас еквивалентност . - Втори еквивалентни състояния - Ако автоматът се намира в някое от тези състояния, при еднакви входни въздействия се оказва в еднакви първи еквивалентни класове. Това разбиване продължава, докато в к-тата и к+1 -та стъпка се получат еднакви класове еквивалентност . 2). От всяко подмножество от еквивалентни състояния се избира едно и тези състояния образуват множеството Amin на минималния автомат. 3). Функциите на прехода и на изхода се определят, като в таблицата на преходите и изходите се зачеркнат колонките на излишните състояния, а се оставят само състоянията, включени в Amin. В таблицата на преходите отпадналите състояния се заменят с еквивалентните им. 4). За начално състояние a1min се избира кое да е от групата, в която е a1 или самото то. Пример: 1). Определяне на първи клас на еквивалентност , състоящ се от подкласове от едноеквивалентни състояния. , където и Построяване на таблица , заменяйки състоянията от предходната таблица със съответния клас от първи еквивалентни състояния. Втори еквивалентни са състоянията, от които, под въздействието на z1 и z2, се преминава в първи еквивалентни групи състояния. , където , , и . Аналогично: , където , , и . и , т.е. процедурата по разбиването на еквивалентни класове е завършена. 2). От всеки клас от еквивалентни състояния се избира произволно по едно състояние, например първото. Amin={a1a5a8a3a10} 3). Построяват се новите таблици на преходите и изходите. Изтегляне 1.14 Mb. Сподели с приятели:
|