Анализ и синтез на логически схеми
Еквивалентни автомати и връзка между моделите на автоматите на Мили и Мур
Изтегляне 1.14 Mb.
|
Свързани:
an-architectural-reassessment-of-a-villa-rustica-near-serdica, New Microsoft PowerPoint Presentation, кр цсх
| 4. Еквивалентни автомати и връзка между моделите на автоматите на Мили и Мур.
Нека да разгледаме автомат на Мили, зададен чрез своя граф на преходите и таблици на преходите и изходите. Нека на входа на този автомат, установен в начално състояние, постъпва входната дума . Тъй като a , то под действието на първата буква z1 на думата, автоматът ще премине в състояние a3 и ще генерира изходна реакция w1. При постъпване на втората буква z1 автоматът ще премине в a1 и ще генерира w2. Имайки предвид графа или таблицата на преходите и изходите, може да се проследи пълната реакция на автомата на входната дума . Това изглежда така:
- това ще е реакцията на автомата на Мили на входно въздействие . Както се вижда от примера, като отговор на входна дума с дължина k, автоматът на Мили преминава в k+1 състояния и генерира изходни реакции - дума с дължина k. В общия случай поведението на автомата на Мили, установен в състояние am, може да се опише по следния начин: Базирайки се на горните разсъждения, можем по аналогия да опишем поведението на автомат на Мур, намиращ се в състояние am и под въздействието на входна дума zi1,zi2,...,zik. Очевидно е, че изходният сигнал не зависи от zi1, а се определя само от състоянието am. Можем да кажем, че реакцията на автомата на Мур на входна дума zi1,zi2,...,zik е изходната дума . Д а разгледаме автомат на Мур, зададен чрез граф на преходите и изходите (фиг.6.4.). Нека на входа на този автомат бъде подадена същата входна дума .
Ако сравним реакциите на автоматите на Мили и Мур, но изместена на един такт, ще видим, че те съвпадат и не зависят от дължината на входната дума, т.е. те са еквивалентни автомати. Два напълно определени автомата SA и SB, които имат еднакви входни и изходни азбуки, се наричат еквивалентни, ако, след като са установени в начално състояние, реакциите им на едно и също, произволно входно въздействие съвпадат. Доказано е, че за всеки автомат на Мили съществува еквивалентен автомат на Мур и обратно. При описване на алгоритмите за трансформация на автомат на Мили в автомат на Мур и обратно ще бъде пренебрегвана изходната реакция на автомата на Мур, когато той се намира в начално състояние . 4.1. Трансформиране на автомат на Мур в еквивалентен автомат на Мили. Нека е даден автоматът на Мур . Той трябва да се преобразува в автомат на Мили , при който ; ; ; ; Неизвестна е само функцията на изходите . Ако в автомата на Мур и , то при автомата на Мили . При графично зададен автомат преходът Мур -> Мили изглежда както е показано на фиг.6.5., т.е. изходната реакция от възела се присвоява на всички входящи в него дъги. При табличен метод на задаване таблицата на преходите на SB съвпада с тази на SA. Таблицата на изходите на SB се получава от таблицата на преходите на SA като се замества a5, стоящ на пресечната на линия zf и стълб am с изходната реакция wg, съответстващ на състоянието as от изходната таблица на SA. Пример: 4.2. Трансформиране на автомат на Мили в еквивалентен автомат на Мур. На автомата на Мили се налагат следните ограничения: - от всеки връх (всяко състояние) трябва да има поне една изходяща дъга (поне един преход); - не трябва да има състояния, в които не се преминава от никое друго състояние. Даден е автомат на Мили - . Трябва да се построи еквивалентен автомат на Мур - . От определението за еквивалентност следва, че: Трябва да се определят . - Множеството от състояния AB се определя по следното правило (фиг.6.7.): На всяко състояние as от множеството AA се съпоставя множество от състояния AS от всевъзможни двойки (as,wi)(as,wj), където wi и wj са изходните реакции, присвоени на входящите в as дъги. Броят на двойките е равен на броя на различните изходни реакции, присвоени на всички входящи в as дъги (фиг.6.3.). Множеството AB на автомата на Мур е равно на сумата от множествата AS, т.е. . - Изходната функция се определя по следния начин - на всяко състояние от автомата на Мур, представено като двойка (as,wi)(as,wj) и т.н. се присвоява съответно изходната реакция wi, wj и т.н. ( виж фиг.6.7.). - Функция на преходите - ако при автомата на Мили се извършва преход от състояние в състояние = и се издава изходна реакция , то при автомата на Мур се извършва преход от всяко едно от състоянията на множеството AS - в състояние под действието на (фиг.6.7.). - Начално състояние - за такова може да бъде избрано кое да е от множеството от начални състояния A1. Пример: Даден е автомат на Мили. Да се преобразува в еквивалентен автомат на Мур. Възможна е транс-формация на автомат на Мили в еквивалентен автомат на Мур, ако има състояние, в което не се преминава от друго, само ако то е начално. A1={(a1-)}=b1 A2={(a2w1)(a2w2)}={b2b3} A3={(a3w1)(a2w2)}={b4b5} От изложените методи за взаимна трансформация на автоматите на Мили и на Мур се вижда, че при преход от автомат на Мур към автомат на Мили броят на състоянията не се променя, а при обратната трансформация броят на състоянията се запазва или се увеличава. Ако се извърши преобразуване от автомат на Мили в автомат на Мур и отново в автомат на Мили, първият и последният ще са еквивалентни, но най-вероятно последният ще има по-голям брой състояния. Следователно възниква необходимост от минимизация на броя на състоянията на автомата. Мур е доказал, че за кой да е абстрактен автомат S съществува еквивалентен на него Smin автомат с минимален брой състояния. Изтегляне 1.14 Mb. Сподели с приятели:
|