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


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




Тема 5.1. Обработка на информация с помощта на държавни машини

Глава 5. Основи на теорията на крайните автомати

Обобщение на темите

Въпроси за повторение

1. Маршрутът ли е?

2. В какъв случай маршрутът се нарича цикличен?

3. Какво е верига?

4. В кой случай веригата е проста верига?

5. Определете цикъла на Ойлер?

6. Каква е разликата между циклите на Ойлер и Хамилтън?

7. Кога графиката се нарича дърво?

8. Какви са свързаните компоненти на гората?

9. Горната част се нарича край, ако?

В тази тема се разглеждат понятия като маршрут, цикъл, верига, схема и т.н. по отношение на графиките. Дадени са цикли на Ойлер и Хамилтън. Показана е отделна структура на графиката, която се определя като дърво. Цялостността на тези структури се характеризира като гора.

гол: разгледайте основите на теорията на крайните държавни машини.

Задачите:

1. Разгледайте концепцията за абстрактна автоматика.

2. Определете начините за определяне на машините.

3. Помислете за връзката между машините Мил и Мур.

Автоматична машина   - дискретен преобразувател на информация, способен под действието на входните сигнали да преминава от състояние в състояние и да генерира изходни сигнали.

Абстрактният автомат се дефинира с помощта на следните пет набора:

A \u003d (X, Y, S, d, l),

където X \u003d (X 1, X 2 ... X M)   - азбуката за въвеждане на машината или набора от символи за въвеждане;

Y \u003d (Y 1, Y 2 ... Y N)   - изходната азбука на машината или набора от изходни знаци;

S \u003d (S 0, S 1 ... S K-1)   - азбуката или набор от вътрешни състояния на автоматика;

S 0   - първоначалното състояние на машината (по време t \u003d 0).

г   - функция за преход;

л- функция на изходите на машината.

Машината се нарича държавна машина ако комплектите X, Y, S   са ограничени (или счетливи).

Машината работи в отделни моменти във времето t \u003d 0, 1, 2 ... n(фиг. 5.1) .

Фиг. 5.1. Държавна машина

Във всеки момент от време автоматът е в едно от състоянията на множеството S.

Преходна функция г тследващото състояние на машината в зависимост от текущото състояние и входния сигнал или символ на входната азбука. С други думи, функцията гвсяка двойка „състояние - входен сигнал“ свързва следното състояние.

d: S´X ® S; г- има картографиране на декартовия продукт S'X   в S.

Функцията на прехода може да бъде записана по следния начин: S t + 1 \u003d d (S t, X t).

Изходна функция лопределя във всеки момент във времето тизходният сигнал на машината.

Има два модела на автоматични машини - машината Miles и машината Moore. Те се различават във функцията на изходите, която се дефинира, както следва:


Y t \u003d l (S t, X t)   - за машината Miles, или l: S´X®Y.

Y t \u003d l (S t)   - за машината Moore.

В машината Miles изходният сигнал в даден момент т   зависи както от входния сигнал по време т, и от текущото състояние.

В машината Moore изходният сигнал е ясно независим от входа и се определя само от текущото състояние.

Състояние на машината- Това е паметта на машината за минали влияния на входа.

Също така се наричат \u200b\u200bавтомати последователни машини   (Последователни машини), защото входната последователност се преобразува в последователност от състояния и изходна последователност.

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

Думата   или верига   Окончателната последователност от знаци (букви) на въвежданата азбука. Следните условия трябва да бъдат изпълнени (автоматични условия):

1. Дължините на въвеждащите и изходните думи са еднакви;

2. Едни и същи начални сегменти на входните думи съответстват на същите начални сегменти на изходните думи.

  • 1.1 Основни понятия
  • заключение
  • Позоваването

въведение

Предмет на теста по дисциплината „Приложна теория на цифровите автомати“ е „Абстрактни цифрови автомати“.

Целта на работата е да се запознае с основните понятия на абстрактните цифрови автомати; видове абстрактни автомати; начини за определяне на абстрактни автомати; връзката между моделите на Майлс и Мур; еквивалентни автомати и еквивалентни трансформации на автомати; минимизиране на броя на вътрешните състояния на автоматика и алгоритъма Aufenkamp-Hon.

1. Абстрактни цифрови автомати

1.1 Основни понятия

Цифрова машина може да бъде интерпретирана като устройство, което приема, съхранява и преобразува дискретна информация според някакъв алгоритъм. От определена гледна точка, както реалните устройства (компютри), така и абстрактните системи (математически модели) могат да бъдат класифицирани като автомати.

Автоматичната машина е дискретен преобразувател на информация, способен да приема различни състояния, да преминава под въздействието на входни сигнали от едно състояние в друго и да издава изходни сигнали.

Общата теория на автоматите е разделена на абстрактна и структурна.

Абстрактната теория на автоматите, разсеяна от структурата на автомата (т.е. не се интересува от метода за конструирането му), изучава само поведението на автомата спрямо външната среда. Абстрактната теория на автоматите е близка до теорията на алгоритмите, като по същество е нейното по-нататъшно прилагане.

За разлика от абстрактната теория на автоматите, структурната теория на автоматите се интересува както от структурата на самия автомат, така и от структурата на входните действия и реакциите на автоматита върху тях. В структурната теория се изучават методи за конструиране на автомати, методи за кодиране на входни действия и автоматични реакции към тях. Структурната теория на автоматите е продължение и развитие на абстрактната теория. Въз основа на устройството на булевите функции и на абстрактната теория на автоматите, структурната теория дава ефективни препоръки за разработването на реални изчислителни устройства.

Абстрактен цифров автомат (CA) е математически модел на дискретно устройство за управление.

Абстрактният CA се определя от набор от шест елемента:

S \u003d (X, A, Y, ao),

когато:

X \u003d (x1, x2,. Xn) - набор от входни сигнали (входна азбука);

Y \u003d (y1, y2, ym) - набор от изходни сигнали (изходна азбука);

A \u003d (a0, a1, a2,. AN) е множеството състояния (азбука на състоянията);

ao - начално състояние (aoA);

е преходната функция на автоматика, определяща картата (XxA) A, т.е. свързване на всяка двойка елементи на декартовия продукт (XxA) елемент от множеството A;

- функция на изходите на автоматика, която определя или картата (XxA) Y, или картата AY.

С други думи, функцията на прехода показва, че автоматикът S, бидейки в определено състояние ajA, когато се появи входният сигнал xjX, преминава в определено състояние apA. Това може да бъде написано:

ap \u003d (ai, Xj).

Изходна функция   показва, че автоматикът S, като е в определено състояние ajA, когато се появи входният сигнал xjX, дава изходния сигнал ykY. Това може да бъде написано: ук \u003d (ai ,   Xj).

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

Абстрактен автомат функционира в дискретно автоматично време t \u003d 0,1,2,. и преходите от състояние в състояние са моментални. Във всеки момент t от дискретно време автоматът е в определено състояние a (t) от множеството A от състояния на автомата, а в началния момент t \u003d 0 винаги е в начално състояние ao. По време t, бидейки в състояние a (t), автоматът е в състояние да възприеме сигнала x (t) X на входния канал и да изведе сигнала y (t) \u003d (a (t), x (t)) на изходния канал, преминавайки до състояние a (t + 1) \u003d \u003d (a (t), x (t)). Зависимостта на изходния сигнал от входа и от състоянието означава, че той съдържа памет.

1.2 Видове абстрактни автомати

По метода на формиране на функцията на изходите се разграничават три типа абстрактни автомати: автоматът на Mealy, автомат Moore и C-автомати. Машината на Майлс се характеризира със система от уравнения:

y (t) \u003d (a (t), x (t));

a (t + 1) \u003d d (a (t), x (t)). (1-1)

Муров автомат - система от уравнения:

y (t) \u003d (a (t));

a (t + 1) \u003d d (a (t), x (t)). (1-2)

C-машина - система от уравнения:

y \u003d y1y2

y1 (t) \u003d (a (t), x (t));

Y2 (t) \u003d 2 (a (t));

a (t + 1) \u003d d (a (t), x (t)).

Произволен абстрактен автомат Mily или Moore (фиг. 1.1.) Има един вход и един изходен канал. Един произволен абстрактен С-автомат има един вход и два изходни канала (фиг. 1.2.).

Фигура 1.1 - Абстрактна автоматика

Фигура 1.2 Абстрактна машина с C състояние

Ако въвеждането на абстрактния автомат Mili или Moore е настроено на първоначално състояние ao, прилагайте буква по буква определена последователност от букви от входната азбука x (0), x (1),. е входната дума, тогава буквите на изходната азбука y (0), y (1) ще се появяват последователно на изхода на машината. - изходната дума. В случая на С-автомати, на изходите му ще се появят две последователности: y1 (0), y1 (1),. и y2 (0), y2 (1),. В абстрактна машина C - състоянието, изходният сигнал y2 (t) \u003d (a (t)) се издава през цялото време, докато машината на състоянието е в състояние a (t). Изходният сигнал y1 (t) \u003d l1 (a (t), x (t)) се издава по време на действието на входния сигнал x (t), когато C-състоятелната машина е в състояние a (t).

По този начин, на нивото на абстрактната теория, функционирането на цифров автомат се разбира като преобразуване на входните думи в изходните думи.

Разпределете напълно дефинирани и частични автомати.

Напълно дефиниран е абстрактен цифров автомат, който има преходна функция или функция на изходи, или и двете от двете функции са дефинирани за всички двойки преходи (xi, aj).

Частичен е абстрактен цифров автомат, чиято функция на преход или изходна функция или и двете от тези функции не са дефинирани за всички двойки на прехода (xi, aj).

Абстрактен цифров автомат се нарича първоначален, ако първоначалното състояние ао се разграничи от множеството на неговите състояния А.

1.3 Начини за определяне на абстрактни автомати

За да се дефинира машина с ограничено състояние S, е необходимо да се опишат всички елементи от множеството: S \u003d (X, A, Y, ao). Има няколко начина да се определи работата на машината, но най-често използваната таблица (матрица), графична, аналитична.

По табличен начин автоматът се дефинира от две таблици: преходна таблица и изходна таблица или матрица за свързване. Таблицата на прехода на произволен напълно дефиниран автомат се изгражда по следния начин: редовете на таблицата са маркирани с буквите на входната азбука на автоматика, а колоните на таблицата са маркирани с буквите на азбуката на състоянията на автомата; В клетката на преходната таблица, разположена на в пресечната точка на реда, маркиран с входния сигнал xi и колоната, маркирана от състоянието aj, се задава състоянието ak, което е резултат от прехода на автоматика от състояние aj под въздействието на входния сигнал xi, който се определя от израза ak \u003d (aj, xj).

Таблица 1.1 машина за преходи на таблица

Пример за попълване на таблицата на прехода на някои абстрактни напълно дефинирани автомати с входната азбука X \u003d (x1, x2) - и азбуката на състоянието A \u003d (a1, a2, a3) е представен в таблица 1.2.

Таблица 1.2

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

Попълването на останалите клетки е подобно на случая с напълно определен автомат. Изгледът на таблицата за преход не зависи от типа на посочения автомат (автоматичен Miley, Moore, C-automatic). Изходните таблици на машините Mily, Moore, C-automaton имат разлики.

Изходната таблица на напълно дефиниран автомат Miles е конструирана по следния начин: идентифицирането на колони и редове, както и форматът на таблицата съответстват на таблицата на прехода на напълно определен автомат. В клетката на изходната таблица, разположена в пресечната точка на реда, маркиран с входния сигнал Xj, и колоната, маркирана със състоянието ak, поставете изходния сигнал Um, който машината генерира, докато е в състояние ak в присъствието на входния сигнал Xj, който се определя от израза Ym \u003d (ak, xj ).

Таблица 1.3 Таблица на изхода на абстрактната машина на Miles.

Пример за попълване на изходната таблица на някои абстрактни напълно дефинирани автомати с входната азбука X \u003d (x1, x2), азбуката на състояния A \u003d (a1, a2, a3) и азбуката на изхода Y \u003d (y1, y2, y3) е представен в таблица 1.4.

Таблица 1.4

Очевидно абстрактният напълно дефиниран С-автомат се дефинира от две изходни таблици, първата от които е изходната таблица на автомата на Майлс, а втората е Мур. Ако автоматът е частичен, тогава в някои клетки от таблицата му може да има тире, което означава, че няма изходен сигнал.

На практика таблиците за преход и изход често се комбинират в една таблица, наречена маркирана таблица на прехода на автоматика. Примери за маркирани преходни таблици са представени в таблица 1.6. - 1.8 (Общият изглед на маркираната таблица на прехода е таблица 1.6., Маркираната таблица на прехода на автомата Milie е таблица 1.7., Маркираната таблица за преход на автомата Moore е таблица 1.8.).

В допълнение към таблиците за преход и изход, обсъдени по-горе, произволен абстрактен автомат може да бъде определен чрез матрица от съединения.

Матрицата на връзката е квадратна и съдържа толкова колони (редове), колкото много различни състояния съдържа азбуката на състоянията на даден автомат. Всяка колона (ред) на матрицата за връзка е маркирана със буквата на състоянието на машината. В клетката, разположена в пресечната точка на колоната, означена с буквата aj, и реда, отбелязан с буквата към автомата, се поставя входен сигнал (или разединение на входните сигнали), под въздействието на който се извършва този преход.

За абстрактния автомат Mily, в клетката до състоянието, се поставя и изходен сигнал, който автоматът дава в резултат на този преход (Таблица 1.9.) За автомата на Мур изходният сигнал се поставя на ред до състоянието (тези състояния съответстват на началните състояния на автоматика).

Таблица 1.6

Таблица 1.8

В графичния метод за определяне на абстрактни автомати са представени от ориентирани графики. Автоматична графика е ориентирана свързана графика, чиито върхове съответстват на състоянията на автоматика, а дъгите между тях съответстват на преходи между състояния. Два върха ak и as са свързани с дъга, ако автоматът има преход от състояние ak в състояние като. За автомата Mili входните и изходните сигнали се начертават върху дъгата, съответстваща на дадения преход (фиг. 1.3.), За автомата Moore входният сигнал е начертан върху дъгата, а изходният сигнал е близо до върха, съответстващ на състоянието (фиг. 1.4.).

Тук разглеждаме само детерминизирани автомати, за които е изпълнено условието за уникалност на преходите: автоматик, който е в определено състояние, не може при никакво действие на всеки входен сигнал да премине в повече от едно състояние. Както се прилага за графичния метод за определяне на автомат, това означава, че в графиката на автомат две или повече дъги, маркирани с един и същи входен сигнал, не могат да излязат от всяка върха.

Фигура 1.3-Графика на машината Miles Фигура 1.4-Графика на машината Mura

В аналитичния метод за определяне на абстрактни автомати се дефинират от четири обекта:

S \u003d (X, A, Y, F), където F определя за всяко състояние aj на автоматика карта (XxA) - >   (AxY). С други думи, в аналитичния метод за уточняване за всяко състояние на автомата aj се посочва картата Fai, която е множеството на всички тройки ap, xm, yk и такава, че под въздействието на входния сигнал xm автоматът преминава от състояние ик в   състояние ap, давайки изходен сигнал yk.

Както е приложено към общото определение на абстрактен автомат, последният е еквивалентен на описание на функциите g и l в съответствие с израза: ap \u003d g (ai, xm), yk \u003d l (ai, xm).

Съпоставянето Fai е написано по следния начин:

Fai (ap (Xm / yk), ai (Xf / yz) ...).

За абстрактния автомат Mily (таблица 1.7.) Аналитичната задача има следната форма:

S \u003d (X, A, Y, F), X \u003d (x1, x2), A \u003d (a1, a2, a3), Y \u003d (y1, y2, y3),

Fa1 \u003d (a2 (x1 / y2), a1 (x2 / y3)),

Fa2 \u003d (a3 (x1 / y3), a1 (x2 / y1)),

Fa3 \u003d (a1 (x1 / y3), a2 (x2 / y2)).

Трябва да се отбележи, че функцията Fai винаги се записва за първоначално състояние.

Определете синхронни и асинхронни автомати. Задните състояния на автоматиката S се наричат \u200b\u200bстабилно състояние, ако за всеки входен сигнал xjX, такъв, че ass \u003d q (ai Xm), as \u003d q (as, xm).

Автомат S се нарича асинхронен, ако всяко от неговите състояния като A е стабилно. Автомат S се нарича синхронен, ако не е асинхронен.

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

1.4 Връзка между моделите Miles и Moore

Както вече беше отбелязано, абстрактен автомат действа като преобразувател на думи от входната азбука в думи на изходната азбука.

Нека абстрактният автомат на Мили е даден от графиката на фиг. 1.5.

Въведената дума X \u003d x1, x1, x2, x1, x2, x2 идва на входа на този автомат, зададен на първоначалното му състояние.

Фигура 1.5 - Брой на машината на Майлс

И как? (a1, x1) \u003d a3, a? (a1, x1) \u003d y1, тогава под действието на първата буква на думата X на входния сигнал x1 машината ще премине в състояние a3 и сигналът y1 ще се появи на изхода си. Освен това ,? (a3, x1) \u003d a1 и? (a3, x1) \u003d y2, следователно, когато пристигне вторият сигнал x1, автоматът ще бъде в състояние a1, а сигналът y2 ще се появи на изхода си. След като директно проследим по-нататъшното поведение на автомата директно в графиката или таблиците на преходи и изходи, ние го описваме в три реда, първият от които съответства на входната дума X, вторият на последователността от състояния, които автоматът преминава под действието на буквите на думата X, а третият - на изходната дума U, която се появява на изхода автоматична машина:

x1x1 x2 x1 x2 x2

a1a3 a1a1 a3 а2   a3

y1 y2 y1 y1 y1 y2

Обадете се на = ? (a1, X) чрез реакцията на автомата на Mealy в състояние a1 към входната дума X. Както се вижда от примера, в отговор на входна дума с дължина k, автоматът Mealy произвежда последователност от състояния с дължина k + 1 и изходна дума с дължина k. Най-общо, поведението на автоматиката Mealy, настроено на състояние am, може да бъде описано по следния начин:

По същия начин може да се опише поведението на автомата на Мур, който е в състояние am, при пристигането на входната дума xi1, xi2,., Xik . Спомнете си, че в съответствие с (1-2) изходният сигнал в автомата на Мур във време t (Y (t)) зависи само от състоянието, в което автоматът е в момент t (a (t)):

Очевидно изходният сигнал yi1 \u003d l (am) във време i1 не зависи от входния сигнал xi1, а се определя само от състоянието am.

По този начин този сигнал yi1 по никакъв начин не е свързан с входната дума, влизаща в автоматичния вход, като се започне от момента i1. В тази връзка, под реакцията на автомата на Мур, зададен на състояние am на входната дума X \u003d xi1, xi2 , . ,   xik ще разберем изходна дума със същата дължина y \u003d l (am, X) \u003d yi2, yi3, ..., yik + 1.

Като пример, разгледайте автомата на Мур S5, графиката на който е показана на фигури 1-6, и намерете реакцията му в първоначално състояние на същата входна дума, която използвахме, когато анализираме поведението на автоматите на Mealy S1:

Фигура 1-6 - Брой на автомата на Мур

Както се вижда от този и предишните примери, реакциите на автоматите S5 и S1 в първоначалното състояние на входната дума X съвпадат до изместване с 1 часовник (реакцията на автомата на Мур е очертана с линия). Сега даваме строго определение за еквивалентността на напълно дефинираните автомати.

Два автомати SA и SB с еднакви азбуки за вход и изход се наричат \u200b\u200bеквивалентни, ако след установяването им в началните състояния реакциите им към всяка въвеждана дума съвпадат.

1.5 Еквивалентни автомати. Еквивалентни трансформации на автомати

Може да се покаже, че за всеки автомат Mili съществува еквивалентен на него автомат Moore и, обратно, за всеки автомат Moore съществува еквивалентен автомат Mili.

Когато описваме алгоритмите за взаимно преобразуване на автоматите на Майлс и Мур в съответствие с горното, ще пренебрегнем изходния сигнал, свързан с първоначалното състояние (? (A1)) в автоматите на Мур.

Помислете първо за преобразуването на автомата на Мур в автомата на Майлс.

Нека се даде автоматик на Мур: SA \u003d (XA, AA, UA,? A,? A, aoA), където:

XA \u003d (x1, x2,. Xn); Y \u003d (y1, y2,. Ym); A \u003d (a0, a1, a2, a.N); a0A \u003d a0 - начално състояние (a0AA); A е преходната функция на автоматика, определяща картата (XAxAA) -\u003e AA; ? A е функцията на изходите на автоматика, определяща картографирането AA-\u003e UA.

Изградете автоматиката на Mealy: SB \u003d (ХB, AB, YB, ?? B,? B ,   a0B), в която AB \u003d AA; XB \u003d XA; YB \u003d UA; ? B \u003d? A; a0B \u003d a0A. Изходната функция? B се дефинира по следния начин. Ако в автомата на Мур? A (am, x1) \u003d като и? A (as) \u003d \u200b\u200byg, тогава в автоматика на Майлс? B (am, x1) \u003d yg

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

Преходът от автомата на Мур към автомата на Майлс с графичния метод на настройка е илюстриран на фиг. 1-7: изходният сигнал yg, записан близо до върха (като), се прехвърля към всички дъги, влизащи в тази върха.

В табличния начин за уточняване на автоматика таблицата на прехода на автомата Miles съвпада с таблицата на прехода на оригиналния автомат Moore, а изходната таблица се получава от таблицата на прехода чрез замяна на символа като в пресечната точка на реда xf и колоната am, символа на изходния сигнал yg, маркиращ колоната asg в таблицата на прехода на SA автоматика.

От самия метод на конструиране на автомата на Майли SB е очевидно, че той е еквивалентен на автоматите Moore SA. Чрез индукция е лесно да се покаже, че всяка входна дума с ограничена дължина, приложена към входовете на автоматите SA и SB, зададени в състояние am, ще предизвика появата на едни и същи изходни думи и следователно автоматите SA и SB са еквивалентни.

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

SA \u003d (XA, AA, YA,? A,? A, a0A),

когато:

XA \u003d (x1, x2,. Xn); Y \u003d (y1, y2,. Ym); A \u003d (a0, a1, a2,. AN); a0A \u003d a0 - начално състояние (a0AA); A е преходната функция на автоматика, определяща картата (XAxАA) -\u003e AA; ? A е функцията на изходите на автоматика, която определя картата (XAxАA) -\u003e YA.

Конструираме автомата на Мур: SB \u003d (XB, AB, YB,? B,? B, a0B), за който XB \u003d XA; YB \u003d YA.

За да определим AB, ние присвояваме на всяко състояние катоAA множеството As на всички възможни двойки от формата (като, yg)

Изходната функция? B се дефинира по следния начин. Към всяко състояние на Moore машина SB, което е двойка от формата (като, yg), ние свързваме изходния сигнал yg.

Ако в автомата на Майли SA е имало преход? A (am, xf) \u003d както и в същото време е бил произведен изходен сигнал? A (am, xf) \u003d yg, тогава в SB ще има преход от множеството състояния Am, генерирани от am към състоянието (като, yg) под действието на входния сигнал xf.

Като първоначално състояние a0B можем да вземем всяко от състоянията на множеството A0, което се генерира от първоначалното състояние a0 на автоматичния SA. В този случай изходният сигнал във време t \u003d 0 не трябва да се взема предвид.

Помислете за пример. Нека бъде даден автоматът на Mealy (Таблица 1.10.)

Свързваме с всяка двойка ai / xk състоянието bik (i-state number, k-номер на входния сигнал), като се взема предвид b0.

Ние съставяме таблицата за преход на автоматите Moore, ръководени от следните правила:

1) Нека изпишем от таблица 1.11 състоянията на автомата на Майлс и множествата състояния на автомата на Мур (bik), съответстващи на всеки от тях:

a0 \u003d (b0, b02, b11, b21); a1 \u003d (b22); A2 \u003d (b01, b12);

2) Ако състоянието на biok automaton bik е включено в множеството, съответстващо на състоянието ap на автомата Mealy, тогава в реда на таблицата на прехода на автомата Moore за състоянието bik трябва да се напише ред от таблицата на прехода на автомата Milie, съответстващ на състояние ap (от 1.10.).

3) Функцията на изходите на автомата на Мур се дефинира по следния начин: B (bik) \u003d? A (ai, xk). За начално състояние b0 стойността на изходния сигнал може да бъде избрана произволно, но генерирана от първоначалното състояние a0 (като се вземе предвид понятието за еквивалентност на състоянията). Резултатната таблица на преходите и изходите на автомата Moore, еквивалентна на автоматиката Mealy, посочена в таблица 1.10, е представена в таблица 1.12.

4) Намерете еквивалентните състояния в таблица 1.12 и ги изтрийте (заменете с представител на класа на еквивалентност).

Ако изходният сигнал близо до b0 е допълнен с y1, тогава се оказва, че в тази таблица на прехода има 3 еквивалентни състояния (b0, b11, b02). Замествайки класа на еквивалентност с един представител (b0), получаваме финалната таблица на прехода (Таблица 1.13).

Таблица 1.12

Описаните по-горе методи за взаимното преобразуване на автоматите на Майлс и Мур показват, че при преминаване от автомата на Мур към автомата на Майлс броят на състоянията на автомата не се променя, докато при обратния преход броят на състоянията в автомата на Мур като правило се увеличава.

По този начин, еквивалентни помежду си автомати могат да имат различен брой състояния и следователно възниква проблемът с намирането на минималния (с минимален брой състояния) автомат в класа на еквивалентни един на друг автомати. Съществуването на всеки абстрактен автомат на еквивалентен абстрактен автомат с минимален брой вътрешни състояния за първи път е доказано от Мур.

1.6 Минимизиране на броя на вътрешните състояния на автоматика

Алгоритъм на Aufenkampa-Hon.

Методът за минимизиране на състоянията на автомат се основава на идеята за разделяне на всички състояния на оригиналния, абстрактен автомат на взаимно разединяващи се класове на еквивалентни състояния и замяна на всеки клас на еквивалентност с едно състояние (представител на този клас). Минималният автомат, образуван в резултат на тези трансформации, има същия брой състояния, както и началните състояния, разделени на колко класа еквивалентност.

Две състояния на автоматика am и както се наричат \u200b\u200bеквивалентни (am \u003d as), ако? (am, X) \u003d? (като, X) за всички възможни входни думи с дължина X.

Ако съм и не са еквивалентни, те се различават. По-слабата еквивалентност е K-еквивалентност. Състоянията съм и както са K-еквивалентни, ако? (am, Xk) \u003d? (като, Хк) за всички възможни входни думи с дължина K. Когато свеждате до минимум броя на вътрешните състояния на автоматите Mealy, S \u003d (X, Y, A,? , ?, a0) използва алгоритъма Aufenkamp-Hon:

1. Намерете последователни дялове на? 1,? 2, ...,? K,? K + 1, поставя A в класове от едно-, две -,., K-, (K + 1) - еквивалентни състояния до някои (K + 1) стъпка не се оказва? k \u003d? k + 1. В този случай K-еквивалентните състояния са еквивалентни. Броят на стъпките K, при които? K \u003d? K + 1, не надвишава N-1, където N е броят на вътрешните състояния на автоматика.

2. Във всеки клас на еквивалентност? изберете един елемент (представител на класа), който формира множествата A от "състояния на минималния автоматичен S".

3. Преходна функция? "И изходи?" автоматикът S "е определен на множеството A" xX.

За да направите това, зачеркнете колоните, съответстващи на състоянията, които не са включени в множеството A в таблицата на прехода и изхода, а в останалите колони на таблицата на прехода всички състояния се заменят с еквивалентни състояния от множеството A (от представители).

4. Като "0 се избира едно от състоянията, което е еквивалентно на състоянието a0. По-специално е удобно да се приеме самото състояние a0.

За да се сведе до минимум автоматът на Мур, се въвежда концепцията за 0-еквивалентност на състояния и разделяне на множеството състояния на 0-класове: 0-еквивалентни са всякакви състояния на автомата на Мур, които са еднакво маркирани с изходни сигнали. Като пример, помислете за минимизиране на автомата на Мур, даден от таблицата за прехода и изхода (Таблица 1.14).

Таблица 1.14

Направете дяла? 0:

? 0 \u003d (В1, В2, В3);

B1 \u003d (a1, a2, a8), B2 \u003d (a6, a9, a10, a11, a12), B3 \u003d (a3, a4, a5, a7).

Създайте таблица на дяловете? 0:

Направете дяла? 1:

1 \u003d (С1, С2, С3, С4);

С1 \u003d (a1, a2, a8), C2 \u003d (a6, a9, a11), C3 \u003d (a10, a12), C4 \u003d (a3, a4, a5, a7).

Изградете таблица на дяловете? 1:

Направете дяла? 2 .

1 \u003d (D1, D2, D3, D4);

D1 \u003d (a1, a2, a8), D2 \u003d (a6, a9, a11), D3 \u003d (a10, a12), D4 \u003d (a3, a4, a5, a7).

Дял № 2 повтаря дяла? 1 - процедурата за дял е завършена.

Избираме произволно от всеки клас на еквивалентност D1, D2, D3, D4 по един представител - в този случай минималният брой: A "\u003d (a1, a3, a6 ,   А10).

Премахвайки "допълнителните" състояния от първоначалната таблица на прехода, определяме минималния автомат на Мур (Таблица 1.15.)

Таблица 1.15.

заключение

В процеса на изпълнение на тестовата работа се запознахме с основните понятия на абстрактни цифрови автомати; видове абстрактни автомати; начини за определяне на абстрактни автомати; връзката между моделите на Майлс и Мур; еквивалентни автомати и еквивалентни трансформации на автомати; чрез минимизиране на броя на вътрешните състояния на автоматика и алгоритъма Aufenkamp-Hon бяха дадени примери.

Позоваването

1. Самофалов К.Г., Романкевич А.М. и др. Приложна теория на цифровите автомати. - Киев. „Вишко училище“ 1987г.

2. Соловиев Г.Н. Аритметични компютърни устройства. - М. „Енергия“. 1978.

3. Савелиев А.Я. Приложна теория на цифровите автомати - М. „Висше училище“. 1,987.

4. Каган Б.М. Електронни компютри и системи. - М. Енергоатомиздат. 1985 година.

5. Лисиков Б.Г. Аритметични и логически основи на цифровите машини. - Минск. „Висше училище.“ 1980 година.

На изхода, той произвежда знаци (в общия случай) от друга азбука.

Абстрактен автомат

Формално абстрактният автомат се определя като пет

Ограничаването на броя на параметрите на абстрактен автомат дефинира такова понятие като машина с ограничено състояние.

Функционирането на автомата се състои в генерирането на две последователности: последователност от последващи състояния на автомата и последователност от изходни символи, които се разгръщат за последователност от символи в отделни моменти t \u003d 1, 2, 3, ... Моментите на дискретно време се наричат \u200b\u200bкърлежи.

Функционирането на автоматика в отделни моменти от време t може да се опише чрез система от рекурентни отношения:

За да се изяснят свойствата на абстрактните автомати, се въвежда класификация.

Абстрактните автомати формират основен клас от дискретни модели като независим модел и като основен компонент на машини на Тюринг, машини за списания в паметта, държавни машини и други преобразуватели на информация.


Фондация Уикимедия. 2010.

  • Диаграма на състоянието (теория на автоматите)
  • Нагорни Карабах

Вижте какво е "Абстрактна автоматика" в други речници:

    абстрактен автомат   - abstraktusis automatas statusas T sritis automatika atitikmenys: angl. абстрактна автоматика vok. abstrakter Automat, m. абстрактен автомат, м шанс. автоматизирано резюме, м ... Automatikos termų žodynas

    Автоматична машина   - В Уикиречник има статия „автоматично“ Автоматично: Автоматичното устройство е устройство, което независимо извършва някои действия ... Уикипедия

    Държавна машина   - Държавна машина е абстрактна машина без изходящ поток, чийто брой възможни състояния е ограничен. Резултатът от работата на машината се определя от крайното й състояние. Има различни опции за определяне на машина с ограничено състояние. Например, ... ... Уикипедия

    ТУРИНГ МАШИНА   - Абстрактен автомат (тоест компютър или друг прецизен, определен механизъм), теоретично характеризиран от британския математик Алън М. Тюринг през 30-те години. По принцип машина на Тюринг се състои от лента и четена глава. Лентата ... ... Обяснителен речник на психологията

    Теория на автоматите

    Теория на автоматите   - Раздел от теоретична кибернетика, който изучава математическите модели (наричани тук машини или машини) на реални или възможни устройства, които обработват дискретна информация с дискретни цикли на часовника. Основните ... ... Икономически и математически речник

    теория на автоматите   - Секция от теоретична кибернетика, която изучава математическите модели (наричани тук автомати или машини) на реални или възможни устройства, които обработват дискретна информация с дискретни цикли на часовника. Основните понятия на тази теория ... ... Справка за технически преводач

    Теория на автоматите   - Теорията на автоматите е клон на дискретна математика, който изучава абстрактни компютри на автомати, представени под формата на математически модели и задачи, които могат да решат. Теорията за автоматите е най-тясно свързана с ... ... Уикипедия

    компютър   - Схема на персонален компютър: 1. Монитор 2. Дънна платка 3 ... Уикипедия

    Официални методи - Пример за официална спецификация, използваща нотация Z. В компютърните науки и софтуерното инженерство формалните методи се наричат \u200b\u200bгрупа техники, базирани на математически апарат за ... Wikipedia

По метода на формиране на функцията на изходите се разграничават три типа абстрактни автомати: автоматът Mealy, автомат Moore и C-автомати. Машината на Майлс се характеризира със система от уравнения:

y (t) \u003d (a (t), x (t));

a (t + 1) \u003d δ (a (t), x (t)). (1-1)

Муров автомат - система от уравнения:

a (t + 1) \u003d δ (a (t), x (t)). (1-2)

C-машина - система от уравнения:

y 1 (t) \u003d (a (t), x (t));

Y2 (t) \u003d 2 (a (t));

a (t + 1) \u003d δ (a (t), x (t)).

Произволен абстрактен автомат Mily или Moore (фиг. 1.1.) Има един вход и един изходен канал. Един произволен абстрактен С-автомат има един вход и два изходни канала (фиг. 1.2.).

Фигура 1.1 - Абстрактна автоматика

Фигура 1.2 Абстрактна машина с C състояние

Ако входът на абстрактния автомат Mili или Moore е настроен на първоначално състояние a, подайте буква по буква последователност от букви от входната азбука x (0), x (1),. е входната дума, тогава буквите на изходната азбука y (0), y (1) ще се появяват последователно на изхода на машината. - изходната дума. В случая на С-автомати, на изходите му ще се появят две последователности: y 1 (0), y 1 (1),. и y 2 (0), y 2 (1),. В абстрактна машина C - състояние, изходният сигнал y 2 (t) \u003d (a (t)) се издава през цялото време, докато машината на състоянието е в състояние a (t). Изходният сигнал y 1 (t) \u003d λ 1 (a (t), x (t)) се издава по време на действието на входния сигнал x (t), когато C-състоятелната машина е в състояние a (t).

По този начин, на нивото на абстрактната теория, функционирането на цифров автомат се разбира като преобразуване на входните думи в изходните думи.

Разпределете напълно дефинирани и частични автомати.

Напълно дефиниран се нарича абстрактен цифров автомат, чиято функция на преход или изходна функция, или и двете от тях са дефинирани за всички двойки преходи (x i, a j).

Частичен е абстрактен цифров автомат, чиято функция на преход или изходна функция или и двете от тези функции не са дефинирани за всички двойки на прехода (x i, a j).

Абстрактен цифров автомат се нарича първоначален, ако първоначалното състояние а е разграничено от множеството на неговите състояния А.

1.3 Начини за определяне на абстрактни автомати

За да се дефинира машина с ограничено състояние S, е необходимо да се опишат всички елементи от множеството: S \u003d (X, A, Y ,,, a o). Има няколко начина да се определи работата на машината, но най-често използваната таблица (матрица), графична, аналитична.

По табличен начин автоматът се дефинира от две таблици: преходна таблица и изходна таблица или матрица за свързване. Таблицата на прехода на произволен напълно дефиниран автомат се изгражда по следния начин: редовете на таблицата са маркирани с буквите на входната азбука на автоматика, а колоните на таблицата са маркирани с буквите на азбуката на състоянията на автомата; В клетката на преходната таблица, разположена на в пресечната точка на реда, маркиран с входния сигнал x i и колоната, обозначена със състоянието a j, се задава състоянието a k, което е резултат от прехода на автомата от състояние a j под влияние на входния сигнал x i, който се определя от израза a k \u003d (a j, x j).

Таблица 1.1 машина за преходи на таблица

състояния

входни сигнали

   (a k, x j)

Пример за попълване на таблицата на прехода на някои абстрактни напълно дефинирани автомати с входната азбука X \u003d (x 1, x 2) - и азбуката на състоянието A \u003d (a 1, 2 и 3) е представен в таблица 1.2.

Таблица 1.2

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

Попълването на останалите клетки е подобно на случая с напълно определен автомат. Изгледът на таблицата за преход не зависи от типа на посочения автомат (автоматичен Miley, Moore, C-automatic). Изходните таблици на машините Mily, Moore, C-automaton имат разлики.

Изходната таблица на напълно дефиниран автомат Miles е конструирана по следния начин: идентифицирането на колони и редове, както и форматът на таблицата съответстват на таблицата на прехода на напълно определен автомат. В клетката на изходната таблица, разположена в пресечната точка на реда, маркиран с входния сигнал X j, и колоната, маркирана със състоянието a k, се поставя изходният сигнал U m, който машината генерира, докато е в състояние a k в присъствието на входния сигнал Xj, който се определя чрез израза Ym \u003d (a k, x j).

Таблица 1.3 Таблица на изхода на абстрактната машина на Miles.

състояния

Входни сигнали

Пример за попълване на изходната таблица на някакъв абстрактно напълно дефиниран автомат с входна азбука X \u003d (x 1, x 2), азбука на състояния A \u003d (a 1, a 2, 3) и азбука на изхода Y \u003d (y 1, y 2, y 3 ) е представена в таблица 1.4.

Таблица 1.4

Очевидно абстрактният напълно дефиниран С-автомат се дефинира от две изходни таблици, първата от които е изходната таблица на автомата на Майлс, а втората е Мур. Ако автоматът е частичен, тогава в някои клетки от таблицата му може да има тире, което означава, че няма изходен сигнал.

На практика таблиците за преход и изход често се комбинират в една таблица, наречена маркирана таблица на прехода на автоматика. Примери за маркирани преходни таблици са представени в таблица 1.6. - 1.8 (Общият изглед на маркираната таблица на прехода е таблица 1.6., Маркираната таблица на прехода на автомата Milie е таблица 1.7., Маркираната таблица на прехода на автомата Moore е таблица 1.8.).

В допълнение към таблиците за преход и изход, обсъдени по-горе, произволен абстрактен автомат може да бъде определен чрез матрица от съединения.

Матрицата на връзката е квадратна и съдържа толкова колони (редове), колкото много различни състояния съдържа азбуката на състоянията на даден автомат. Всяка колона (ред) на матрицата за връзка е маркирана със буквата на състоянието на машината. В клетката, разположена в пресечната точка на колоната, означена с буквата a j, и реда, обозначен с буквата a s на автоматика, се поставя входен сигнал (или дисункция на входните сигнали), под въздействието на който се извършва този преход.

За абстрактен автомат Mily, в клетката до състоянието, се поставя и изходен сигнал, който автоматът дава в резултат на този преход (Таблица 1.9.) За автомати на Мур изходният сигнал се поставя в ред до състоянието (тези състояния съответстват на началните състояния на автоматика).

Таблица 1.6

състояния

Входни сигнали

 (a 2, x j)

 (a k, x j)

 (a 2, x j)

 (a k, x j)

Таблица 1.7

Таблица 1.9.

В графичния метод за определяне на абстрактни автомати са представени от ориентирани графики. Графика на автоматика е ориентирана свързана графика, чиито върхове съответстват на състоянията на автоматика, а дъгите между тях съответстват на преходи между състояния. Две върхове a k и s са свързани с дъга, ако автоматът има преход от състояние a k към състояние a s. За автомата Mili входните и изходните сигнали са начертани върху дъгата, съответстваща на дадения преход (фиг. 1.3.), За автомата Moore входният сигнал е начертан върху дъгата, а изходният сигнал е близо до върха, съответстващ на състоянието (фиг. 1.4.).

Тук разглеждаме само детерминизирани автомати, за които е изпълнено условието за недвусмисленост на преходите: автомат в определено състояние не може да премине в повече от едно състояние под влияние на който и да е входен сигнал. Както се прилага към графичния метод за определяне на автомат, това означава, че в графиката на автомат две или повече дъги, маркирани с един и същи входен сигнал, не могат да излязат от всяка върха.

Фигура 1.3-Графика на машината Miles Фигура 1.4-Графика на машината Mura

В аналитичния метод за определяне на абстрактни автомати се дефинират от четири обекта:

S \u003d (X, A, Y, F), където F дефинира за всяко състояние a j на автоматика карта (XxA) - >   (AxY). С други думи, с аналитичния метод за определяне, за всяко състояние на автомата a j, е показана картата F ai, която е множеството от всички тройки a p, x m, y k и такава, че под въздействието на входния сигнал x m автоматикът превключва от състоянието и к   в   посочете a p, произвеждайки изходен сигнал y k.

Както е приложено към общото определение на абстрактен автомат, последният е еквивалентен на описание на функциите δ и λ в съответствие с израза: a p \u003d δ (a i, x m), y k \u003d λ (a i, x m).

Съпоставянето на F ai се записва така:

F ai (a p (X m / y k), a i (X f / y z) ...).

За абстрактния автомат Mily (таблица 1.7.) Аналитичната задача има следната форма:

S \u003d (X, A, Y, F), X \u003d (x 1, x 2), A \u003d (a 1, 2 и 3), Y \u003d (y 1, y 2, y 3),

F a1 \u003d (a 2 (x 1 / y 2), a 1 (x 2 / y 3)),

F a 2 \u003d (a 3 (x 1 / y 3), a 1 (x 2 / y 1)),

F a 3 \u003d (a 1 (x 1 / y 3) и 2 (x 2 / y 2)).

Трябва да се отбележи, че функцията F ai винаги се записва за начално състояние.

Определете синхронни и асинхронни автомати. Състоянието a s на автоматиката S се нарича стабилно състояние, ако за всеки входен сигнал x j X, такъв че s \u003d δ (a i X m), s \u003d δ (a s, x m).

Автомат S се нарича асинхронен, ако всяко негово състояние a s A е стабилно. Автомат S се нарича синхронен, ако не е асинхронен.

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