КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Машини щитоносна и Мур 1 страница




Абстрактни машини

1.1. Определяне на абстрактна машина
1.2. Методи за определяне на автоматичното
1.2.1. плосък
1.2.2. графичен
1.2.3. матрица
1.3. Връзката между Мур и бледен модели
1.3.1. Реакция на една миля
1.3.2. Реакция на Мур
1.3.3. пример
1.3.4. Преходът от А до А Майлс Мур
1.3.5. Преходът от А до А Майлс Мур
1.3.6. Един пример за превръщането на автомата щитоносна в Moore автомат
1.3.7. Един пример за прехода от щитоносна автомат с преминаване състояние да автомата Мур
1.4. Минимизиране непълно определени автомати
1.4.1. Теоретични основи на минимизиране
1.4.2. минимизиране на алгоритъм
1.4.3. Пример минимизиране щитоносна автомат
1.4.4. Пример минимизира Мур машина
1.5. Комбинирана машина модели (с автоматична)

1.1. Определяне на абстрактна машина

Математическият модел на дискретни блок за управление е абстрактна машина, която се определя от набор от шест елемента: S = {A, Z, W, , , А1}, където
А = {1, ..., и м, ..., и M} - комплект (държавите от 1 азбука);
Z = {Z 1, ..., Z е, ..., Z F} - множество от входни сигнали (вход азбука);
W = W {1, ..., W д, ..., W G} - множество изходни сигнали (продукция азбука);
- Функция на прехода, който реализира картографирането на D А х Z в A (а = а (М, Z е), и S А);
- Функция на изхода, който реализира картографирането на D А х Z в W (w г = (М, Z е));
и 1 A - началното състояние на автомата.
Machine 2 се нарича краен случай крайно множество A, Z, W. В бъдеще ние ще разгледаме само крайни автомати и терминът <дестинация> почти винаги се пропуска. Машината се нарича напълно квалифицирана, ако D б = D п = А х Z .Inymi думи, напълно квалифицирана областта на функцията машината и съвпадне с комплект A х Z - съвкупност от всички възможни: двойки на формата м, Z F). В частична функция машина или не е определено за всички двойки (М, Z е) А х Z.
Концепцията на държавите в дефиницията на автомат, въведена с факта, че: това е необходимо, за да опише поведението на системи, чиито изходи не зависи само от състоянието на входовете в даден момент, но от известно история, че е от сигналите, които се получават при системни входове .. рано. Състоянията, съответстват точно на паметта за миналото, което ви позволява да се елиминира времето, тъй като изрично променлива и изрази изходните сигнали като функция на държави и входове в даден момент.
Анотация машина (фиг. 1-1) има един вход и един изход канал. На всяко време Т = 0, 1, 2 ,. , , дискретна машина на времето е в определено състояние на (т) на множество състояния на автомат А, и в началния момент Т = 0, то е винаги в първоначалното състояние на (0) = a1. Във време, в състояние на съществуване в един (т), че машината е в състояние да приеме входен канал сигнал Z (т) Z и изход на сигнала на изхода на канала w (т) = (А (т), Z (Т) ), в състояние на движение и (т + 1) = (А (т), Z (T) ); и (т) И, w (т) W. Смисълът на понятието абстрактна машина е, че тя изпълнява картографиране на Z думите на вход азбука в различни думи W изходна азбука. С други думи, ако входа на машината, определен с първоначалното състояние, A1, буква по буква, за да представи поредица от писма от азбука вход стойност Z на (0), Z (1), Z (2), ... -vhodnoe дума, тогава машината ще излезете да се показва изходна азбука писмо w (0), w (1), т (2), ... - изход дума. Специфична за всеки вход дума, съответстваща на изхода дума, ние се получи карта Предизвикано от абстрактна машина.




Фиг. 1-1. В Регистъра на машина


На практика най-широко използваните машини щитоносна и Закона на Мур функционира щитоносна автомат, даден от уравненията

а (т + 1) = (А (т), Z (T) ); W (T) = (А (т), Z ( Т)), Т = 0,1,2, ... (1-1)

и функционирането на законодателството на Мур машина - уравненията

а (т + 1) = (А (т), Z (T) ); W (T) = (А (Т)), Т = 0,1,2, ...

1 Всеки ограничен набор от различни символи може да се разглежда като азбука, буквата е - тези символи на краен подредена последователност от букви, се нарича дума в азбуката.
2 в глава 2, терминът <машината> се отнася до една абстрактна машина.


1.2. Методи за определяне на автоматичното

За да посочите краен автомат S, всички необходими за описване на набор S = {A, Z, W елементи , , , A1}, т. Е. входни и изходни азбуки и азбуката на държави, както и преходни и изходни функции. Вие трябва да изберете състояние a1 Сред многото състояния, в които машината е в момент = 0. Има няколко начина да настроите работи на машината, но най-често се използва електронна таблица, графика и матрицата.


1.2.1. плосък

Описание на длъжността щитоносна автоматните преход и изходни таблици илюстрирани в таблици 1-1 и 1-2. Редовете на тези таблици съответстват на входните сигнали, и колони - членки, и най-лявата колона означава първоначалното състояние на държавите A1.

T 1-1 Общ изглед на таблицата преход на щитоносна автомат T 1-2 Общ изглед на изход масата за щитоносна автомат

Пресечната точка на колони и редове и м Z F преходи в таблицата и постави държавните S = м, Z е), в която преминава от държавната машина под влиянието на AM сигнал Z F, и масата на изхода е съответните изходи на този преход W г = (М, Z е). Пример задача табличен напълно квалифициран S Майлс 1 машина с три състояния, два входа и два изходни сигнали е показано в таблици 1-3 и 1-4.

T Таблица 1-3 преходи щитоносна машина S 1 T Таблица 1-4 щитоносна автоматните изходи S 1

За частичен автомати, чиято функция или не е определено за всички двойки (М, Z е) А х Z, на мястото на неопределени състояния и изходни сигнали поставя тире (частична автомат S 2 е настроен на таблици 1-5 и 1-6).

T Таблица 1-5 преминава частично щитоносна автомат S 2 T Таблица 1-6 извежда частично щитоносна автомат S 2

T 1-7 Общ изглед на маркиран преход масата на Мур FSM T 1-8 Award-маса .Change Мур машина S 2

От изходния сигнал на машината Мур зависи само от състоянието на машината Мур дал една маркирана преход таблица (Таблица 1-7), който се определя на всеки на своята колона, а състояние м, и по-изходния сигнал w г = м), което съответства на това състояние. Един пример на таблица, описваща Мур машина S 3 е показано в Таблица 1-8.


1.2.2. графичен

Граф машина - ориентиран свързан граф, чиито върхове съответстват на щатите, и дъгата - преходите между тях.

Фиг. 1-2 Брой щитоносна автомат S 1 Фиг. 1-3 Брой 2 Майлс S машина

Два върха на машината, както и м и S (първоначалното състояние и преходно състояние) са свързани дъга насочено от до м и е, ако машината е с преход от м в с S, T. Д. дали и S = (М, Z е) в някои Z е Z. Arc м и и), графът се дължи на входа на машината Z F и изходния сигнал w г = (М, Z е), ако е определено, и пробив се поставя друго. Ако се появи на прехода на автомата от състояние на държавната м и е под действието на няколко входни сигнали, дъгата м и и) приписва всичко на входа и на съответните изходи. В описанието Мур машината под формата на графика изход W G = м) се записва в горната или в непосредствена близост до него. На Фигура 1-2, 1-3 и 1-4 покажи маси, които бяха създадени автоматични графики S 1, S 2, S 3.


Фиг. 1-4. Машина граф Майлс S 3


1.2.3. матрица

Matrix машинни връзки имат квадратна матрица Чия редове съответства на първоначалното състояние, а колоните - преходните състояния. Element с MS = Z F / W г, в пресечната точка на м-ия ред и S-то в случай, че щитоносна автомат съответства на входния сигнал Z F, на обаждащия се и преминаването от една държава в друга м и м, и на изходния сигнал w г, издаден от в този преход. За щитоносна автомат S една матрица С 1 има формата


Ако преходът от една м в един и се случва под влиянието на множество сигнали, CMS елемент е набор от двойки (вход / изход) за този преход, свързан със знака на дизюнкция. Мур елемент модел за С MS се определя на прехода на входните сигнали м и и) и на изхода на изхода вектор е описано


м-ия елемент от които е с мощност на сигнала, който бележи държавата като м. За Мур машина S 3


В тази статия, ние считаме само детерминирани машини, в които състоянието на уникалността на прехода: автоматичен, което е в определено състояние, под влияние на всякакви суровини не могат да отидат повече от една държава. Във връзка с графичен метод за автоматично задаване това означава, че автомата на всеки връх на графиката не може да излезе две или повече дъги са с един и същ входен сигнал отбелязани. По същия начин, съединения в матрицата във всяка машина линия на всеки входен сигнал не трябва да се появят повече от веднъж.

T 1-9 Award маси преходи асинхронна машина 4 S Мур


В заключение този раздел се определят синхронни и асинхронни машини. Статус и лидер на автомат S е стабилна държава, ако за всеки вход Z е Z, така че м, Z е) = и S, имат S, Z е) = а S.

S се нарича асинхронен автомат, ако всеки щат на S А стабилно. Автоматично S се нарича синхронен ако не е асинхронен. Трябва да се отбележи, че машините, построени на практика - винаги асинхронни и стабилност на състоянието им винаги е гарантирано по някакъв начин, като например въвеждането на сигнали за синхронизация (виж по-долу, § 3-1.).


Фиг. 1-5. Ърл Мур асинхронен автомат S 4


Въпреки това, на нивото на абстрактна теория, когато машината е само математически модел, който не отразява много от особеностите на възможно прилагането му, често е по-удобно да се работи с синхронизирани картечници, които ние ще се прави в тази глава. Пример за асинхронен автомат Мур S 4 е показан в таблица. 1-9 и Фиг. 1-5 Лесно е да се види, че всички от състоянието му стабилно.

Очевидно е, че ако масата на преходи асинхронна машина и състояние и е в пресечната точка на ред и колона Z е и м (м <S>), това състояние и е трябва да отговарят по същия ред и колона те години. Колоната за асинхронни машина, ако една държава има преходи от други държави, под влиянието на някои сигнали, на върха на един лидер, цикълът трябва да бъде маркиран със същата входния сигнал. Анализ на Таблици 1-3, 1-5 и 1-8 или ориз. 1-2 - 1-4 показва, че машините S 1, S 2 и S 3 са синхронни.


1.3. Връзката между Мур и бледен модели

1.3.1. Реакция на една миля

В § 1-1 отбележи, че абстрактната машината работи като конвертор вход азбука, дума по дума в изходна азбука. Нека разгледаме този въпрос по-подробно, като за пример S 1 щитоносна автомат на фиг. 1-2 (и Таблица 1-3. 1-4). Нека на входа на тази машина, определен в първоначалното състояние, приема входни дума Z = 1, Z 1 Z 2 Z 1 Z 2 Z 2. тъй като (1, Z 1) = 3 и (1, § 1) = W 1, под действието на първата буква от думата - Z 1 машина ще отидат в един 3 и му изходен сигнал ще бъде 1 w вход. Освен това, (3, Z 1) = 1 (3, Z 1) = W 2 и следователно на пристигането на втория сигнал Z 1 ще бъде в състояние да машина 1, и се появява в изходния сигнал W 2. След като проследи директно върху графиката или таблица на преходите и изходите на последващото поведение на машината, тя ще опише трите линии, първата от които съответства на вход думата Второто - последователността на държави, които преминават на машината под влиянието на буквите на думата , Третият - W изходна дума, която се появява на изхода на автомата:


Ние казваме, че W = (1, ) Реакция на щитоносна автомат в щата и 1 във входната дума , Както се вижда от примера, в отговор на въвеждане на думата дължина К дава щитоносна състояние последователност с дължина к + 1 и изходящ дължина к. Като цяло поведението на машината и да се установи състоянието м, може да се опише по следния начин:


1.3.2. Реакция на Мур

По същия начин, можете да се опише поведението на Мур ФЩМ в състояние на благополучие м, при пристигането на входната дума Z i1, Z i2,:, Z ик. Припомнете си, че според (1-2) на изхода на машината Мур в момент (w (т)) зависи само от състоянието, в което машината е в момента тон (а (т)):


разширение


Очевидно е, че изходният сигнал W = I1 м) по време аз 1 не зависи от входния сигнал Z i1, и се определя само от държавен м. Така сигналът W 1 не е свързан с входа за въвеждане на дума на машината, от момента, в който 1. В тази връзка, при реакция инсталиран Мур машина в състояние м, на входно-думата = Z i1 Z i2: Z IK имаме предвид изходната дума със същата дължина W = (М, ) = W i2 w i3: w IK + 1.


1.3.3. пример

Като пример, разгледа Мур автомат S 5, графиката на която е показана на Фиг. 1-6 и да намерят своя отговор в първоначалното състояние на 1 на същия вход думата Z = 1, Z 1 Z 2 Z 1 Z 2 Z 2, които са използвани за анализ на поведението на щитоносна автомат S 1:


Както се вижда от този и предишните примери, реакционната автомати S 5 и S 1 в първоначалното състояние на вход думата до промяна в същия часовник цикъл 1. Ние сега дават строга дефиниция на еквивалентност напълно дефиниран автомати.
Две машина S A и S B със същите входни и изходни азбуки се наричат еквивалентни, ако след установяване на техните първоначални състояния на техния отговор на всеки вход дума съвпадат.


1.3.4. Преходът от А до А Майлс Мур

Може да се покаже [7], че за всяко щитоносна автомат съществува еквивалентно Мур автомат и обратно, за всяка машина има еквивалентно Мур щитоносна. При описанието на взаимна трансформация алгоритми щитоносна машина и Мур, в съответствие с посоченото по-горе, ние ще незаинтересованост Мур автомат изходен сигнал, свързан с първоначалното състояние (1).
Нека първо разгледаме преобразуването Мур ФЩМ в бледен. Получавайки Мур автомат

S A = {A A, Z A, W A, А, А, 1А},


където

A A = {1: и м,:, а M},
Z A = {Z 1,:, Z е,:, Z F},
W A = {W 1: W д,: W G};


A - сечива картографиране A A х Z А в A A, A - A A дисплей на W А, и 1А = 1 - първоначалното състояние.


Фиг. 1-6. Ърл Мур машина S 5


Фиг. 1-7. Илюстрация на прехода от модел към Мур щитоносна модел


Ние се изгради щитоносна

S B = {A B, Z B, W B, B, B, а 1B},

в които

A B = A A = {1: и м,:, а M},
Z B = Z A = {Z 1,:, Z е,:, Z F},
W B = W A = {W 1: W д,: W G};
В = А, 1B = а 1A = на 1


Функцията извежда Майлс Б се определя, както следва. Ако машината Мур А (m, Z е) = а S и А (и) = W г , щитоносна машина в В (М, Z е) = W г.
Преходът от машината Мур машина при настройка графичен режим миля е илюстрирано Фигура 1-7: изходен сигнал г), записани в горната част и), се прехвърля към всички дъги, които са в горната част. Фиг. 1-8 е графика на брашнената автомат S 6, еквивалентна Мур автомат S 3 (Фиг. 1-4).
Когато метод табличен за определяне на машината S A преход маса на автомата S B съвпада с преход маса S А, и масата на изхода S B се получава от таблицата на преходите на S подмяна характер, стоящи в пресечната точка на ред Z е и колона м, символът w г изходен сигнал, маркиране на колоната с S, в таблицата на преходите е една машина.
Поради метод за изграждане Майлс S B машина е очевидно, че да е равен Мур автомат S A. В действителност, ако някои вода сигнал Z е Z е входен автомат S A, и в състояние на м, след това той отива в състояние на S = А (m, Z е) и показва входния сигнал W G = А (S). Но съответния щитоносна S B от състоянието на м, също отиде в една и състояние, защото В (М, Z е) = А (m, Z е) = и S - и ще даде същия изходен сигнал W гр съгласно метода на конструиране на функцията В. Така, за въвеждане на последователност с дължина един поведение машина S А и В е S идентични. Чрез индукция, че е лесно да се покаже, че всеки вход дума за ограничен дължина, е въвеждане на автомати S A и S B, установен в състояние на м, ще предизвика същия изход думите и, следователно, автоматична S A и S A и M са еквивалентни.