Методи за специфициране на крайни автомати. Дефиниция на крайни автомати Методи за дефиниране на крайни автомати и основни свойства

Както беше посочено по-рано, Y (x,q)определя реда на трансформация на входните символи и състоянието на машината при предишния тактов цикъл в състоянието при следващия, a Q (x,q) -трансформиране на входни символи и състоянието на машината в текущия тактов цикъл в изходен символ. Ако р 0 е първоначалното състояние на машината и аз- номер на цикъл, тогава работата му се описва от системата:

Тези съотношения се наричат системи от канонични уравнениякраен автомат. Можете да ги използвате, като започнете от q 0,последователно намиране на всички последващи състояния на машината и изходни символи.

Има два вида машини - инициалиИ неинициален. INПри първоначалните автомати първоначалното състояние е фиксирано (т.е. те винаги започват да работят от едно и също състояние q 0).В неначалните автомати всеки от набора може да бъде избран като начално състояние Q; Този избор определя по-нататъшното поведение на машината.

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

IN табличен методфункциите на автоматите се определят от две крайни таблици, наречени съответно преходна матрицаИ изходна матрица.В тези таблици редовете са обозначени с букви от входната азбука, а колоните с букви от вътрешната азбука (символи, кодиращи вътрешното състояние на машината). В матрицата на прехода в пресечната точка на ред (xk)и колона (qr)се поставят стойностите на функцията Y ( q r, x k),А в изходната матрица - стойностите на функцията Q (q r, x k).

Основни дефиниции n Краен автомат е система M =(A, B, S, y), в която n n n A = (a 1, . . . , am) е крайната входна азбука, B = (b 1, . . . . ., bk ) - крайна изходна азбука, S =(s 1, . . . , sn) - крайна азбука на състоянията, : A S S - преходна функция, y: A S B - изходна функция. n Ако в автомат M е избрано едно състояние, наречено начално (обикновено се приема, че това е s 1), тогава полученият автомат се нарича начален и се обозначава (M, s 1). n Има два начина за дефиниране на автомат: Таблица на автомата, диаграма на прехода

Автоматична таблица n 1) 2) 3) 4) Пример: задайте автомат да чете думата „001“, ако входните знаци са „0“ и „1“. Входна азбука A=(0, 1) Изходна азбука A=(Y, N) Азбука на състоянието S=(s 0 "", s 1 "0", s 2 "00" s 3 "001") Автоматична таблица по два начина . се определя от 1) Линии – състояния на машината. Колоните са входни символи. В пресечната точка на редове и колони са посочени функциите y. 2) S, A, y са определени от колони. Упражнение 25 Изградете автомат за търсене на думата KAKADU SA 0 1 S 0 "" S 1, N S 0, N S 1 " 0" S 2, N S 0, N S 2 " 00" S 2, N S 3, Y S 3 " 001 " S 1 , N S 0, N S In y S 0 0 S 1 N 1 S 0 N 0 S 2 N 1 S 3 Y 0 S 1 N 1 S 0 N S 1 S 2 S 3

Диаграма на преход n Ориентирана диаграма на преход, наречена графика, е мултиграф, преходите или графиката съответстват на състояния. Ако (Si, aj)=Sk, y(Si, aj)=bl, тогава се изчертава дъга от върха Si до върха Sk, върху която е написано (aj, bl) n Във ​​всеки връх si условията за коректност са: 0 1 S 0 "" S 1, N S 0, N S 1 « 0» n Върхове, y S 2, N S 0, N S 2 « 00» S 2, N S 3, Y S 3 « 001» S 1, N S 0, N 1, N са изпълнени 1) за всяка входна буква aj има дъга, излизаща от si, върху която е написано aj (условие за пълнота); 2) всяка буква aj се появява само на един ръб, излизащ от si (съгласуваност или условие за детерминизъм) S 0 S 1 (0, N) (1, N) (0, N) (1, N) S 2 (1, Y ) S 3

Автомати и входни думи n За даден автомат M неговите функции са M и y. M може да се дефинира не само върху множеството A от всички входни букви, но и върху множеството A* от всички входни думи. n За всяка въведена дума = aj 1 aj 2. . . ajk (si, aj 1 aj 2. . . ajk) = ((… (si, aj 1), aj 2), . . . , ajk-1), ajk). y (si, aj 1 aj 2... ajk) = y((... (si, aj 1), aj 2),... , ajk-1), ajk).

Пример: Автомати и входни думи Пример: = 0101 (S 1, 0101) = ((S 1, 0), 1) (S 1, 0101) = (((S 2, 1), 0), 1) (S 1, 0101) = ((S 3, 0), 1) (S 1, 0101) = (S 1, 1) (S 1, 0101) = S 0 0 1 S 0 "" S 1, N S 0, N S 1 " 0" S 2, N S 0, N S 2 " 00" y(S 1, 0101) = y((((S 1, 0), 1) y(S 1, 0101) = y(((S 2 , 1), 0), 1) y(S 1, 0101) = y((S 3, 0), 1) y(S 1, 0101) = y(S 1, 1) y(S 1, 0101) = N, y S 2, N S 3, Y S 3 “001” S 1, N S 0, N

Автоматично картографиране n Нека фиксираме първоначалното състояние S 0 в M ​​и всяка входна дума = a 1 a 2. . . ak съпоставяме думата в изходната азбука: = y (S 0, a 1) y(S 0, a 1 a 2). . . y(S 0, a 1... ak). (3 a) n Това съответствие, преобразуване на входни думи в изходни думи, се нарича автоматично преобразуване n Ако резултатът от прилагането на оператор към дума е изходна дума, тогава ще обозначим това съответно M() = .

Пример: Автоматично картографиране Нека свържем входната дума = 0101 с дума в изходната азбука: = y (S 0, 0) y(S 0, 01)y(S 0, 0101). y (S 0, 0)= N , y 0 S 0 "" S 1, N S 0, N S 1 " 0" S 2, N S 0, N S 2 " 00" S 2, N S 3, Y 1 S 3 " 001 » S 1, N S 0, N y(S 0, 01) = y((S 0, 0), 1) = y(S 1, 1) = N y(S 0, 010) = y(((S 0, 0), 1), 0) = y((S 1, 1), 0) = y(S 0, 0)=N y(S 0, 0101) = y((((S 0, 0) , 1) =y(((S 1, 1), 0), 1) = = y((S 0, 0), 1) = y(S 0, 1) = NNNN

Свойства на автоматичното преобразуване 1) думите и = M() имат еднаква дължина: | | = | | (свойство за запазване на дължината); 2) if = 1 2 и M(1 2) = 1 2, където | 1| = | 1|, тогава M(1) = 1; с други думи, образът на сегмент с дължина i е равен на сегмент от образа със същата дължина.

Видове автомати n Общият модел на краен автомат (S-краен), който беше обсъден по-рано, се нарича автомат на Мили. n Един автомат се нарича автономен, ако неговата входна азбука се състои от една буква: A = (a). Всички входни думи на автономния автомат са във формата aa. . . А. n Краен автомат се нарича автомат на Мур, ако неговата изходна функция зависи само от състояния, тоест за всяко s, ai, aj y(s, ai) = y(s, aj). Изходната функция на машината на Мур естествено е с един аргумент; обикновено се обозначава с буква и се нарича марка функция. В графиката на автомат на Мур изходът се записва не на ръбовете, а на върха.

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

Пример за автономен автомат SA a S 1 S 3.0 S 2 S 4.0 S 3 S 4.0 S 4 S 7.0 S 5 S 4.2 S 6 S 5.0 S 7 S 6.1 S 8 S 9, 0 S 9, 1 S S S S S A=(a) , B=(0, 1, 2), S=(S 1, S 2, S 3, S 4, S 5, S 6, S 7, S 8, S 9)

Неразличими състояния n Нека M и T са два автомата с еднакви входни и изходни азбуки. Казват, че състоянието s на автомата M и състоянието r на автомата T са неразличими, ако за всяка входна дума M(s,) = T(r,). n Автоматите M и T се наричат ​​неразличими, ако за всяко състояние s на автомата M има неразличимо състояние r на автомата T и, обратно, за всяко r от T има неразличимо s от M. n Неразличимите състояния се наричат ​​еквивалентни

Минимален автомат n Преходът от автомат M към еквивалентен автомат се нарича еквивалентна трансформация на автомат M. n Можете да поставите различни задачи за намиране на автомати, еквивалентни на даден и имащи дадени свойства. Най-изследваният сред тези проблеми е проблемът за минимизиране на броя на състоянията на автомат: сред автомати, еквивалентни на M, намерете автомат с най-малък брой състояния - минимален автомат.

Аспекти на „работата“ на автоматите Могат да се разграничат два основни аспекта на „работата“ на автоматите: 1) автоматите разпознават входни думи, т.е. те отговарят на въпроса дали думата, дадена като вход, принадлежи към даден набор (тези са разпознаващи автомати); 2) автомати преобразуват входни думи в изходни думи, т.е. прилагат автоматични съпоставки (автоматични конвертори).

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

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

Основни типове алгоритми n Теорията на алгоритмите е метатеория, която изучава различни (качествени и количествени) свойства на алгоритмите. n За изследване на качествените свойства са дефинирани 3 основни типа алгоритми: 1) Рекурсивни функции 2) Машина на Тюринг 3) Канонични системи на Пост и нормални алгоритми на Марков.

Най-простите рекурсивни функции n S 1(x) = x+1 - функцията зависи от една променлива x и е равна на x+1. n On(x 1…xn) =0 - функция, зависеща от n променливи и винаги равна на 0. n Imn(x 1…xn) = xm - функция, зависеща от n променливи и винаги равна на стойността на променливата xm

Примитивна рекурсия n Функцията f(x 1…xn+1) се получава чрез алгоритъма за примитивна рекурсия от функциите g(x 1…xn) и h(x 1…xn+2), ако f(x 1, …xn , 0) = g (x 1, …xn) (1) f(x 1, …xn, y+1) = h(z), където z=f(x 1, …xn, y) (2) Функция f се нарича примитивно рекурсивно, ако може да се получи от най-простите функции S 1, On, Imn чрез краен брой операции на суперпозиция и примитивна рекурсия.

Пример n За да докажете, че дадена функция е примитивно рекурсивна, е необходимо: ​​1) Съгласно уравнения (1) и (2), изрично дефинирайте функциите g() и h(). 2) Покажете, че g() и h() са най-простите функции S 1, On, Imn или вече доказани примитивни рекурсивни функции. Упражнение 26: Докажете, че функцията f(x, y) = x+y е примитивна рекурсивна теза на Чърч: Класът на алгоритмично изчислими числови функциисъвпада с класа на всички рекурсивни функции.

Машина на Тюринг n Машината на Тюринг съдържа: n 1) Външна памет – лента от n клетки. Всяка i-та клетка е в състояние ai. Посочена е азбуката на държавите. Лентата може да бъде безкрайна и в двете посоки. Празните състояния са пропуснати. n 2) Вътрешна памет на машината - устройството в момента е в състояние qi. Посочена е азбуката на вътрешното състояние. Начално състояние q 1, крайно състояние q 0 или qz. n 3) Показалец – сочи към текущата клетка и се движи по лентата. n 4) Контролно устройство – чете символа на клетката, към която сочи показалецът. В съответствие с програмата променя състоянието на клетката и премества показалеца.

Състояние и програма MT n Състоянието на машина на Тюринг се нарича думата n ​​n n n a 1…ak-1 qi ak…ar , образувана чрез вмъкване на символ за вътрешно състояние преди клетката, която се наблюдава. Програмата на машината на Тюринг е набор от команди, които машина qi aj qi' aj' D може да изпълни, където qi е вътрешното състояние на машината aj е състоянието на наблюдаваната клетка qi' е новото състояние на машината aj ' е новият символ, изписан в наблюдаваната клетка D = ( L, R, E) – символи, символизиращи изместване на показалеца с една клетка съответно наляво, надясно и без изместване.

Пример MT Упражнение 27: Намерете крайното състояние на машина на Тюринг Първоначална азбука: A = (0, 1) Азбука на вътрешно състояние: Q = (q 0, q 1, q 2) Програма: ( 1) q 10 q 20 R, 2)q 20 q 01 E, 3) q 11 R, 4) q 21 R ) Стартова дума:q 111

Пример MT Упражнение 28 Намерете крайното състояние на машина на Тюринг Първоначална азбука: A = (0, 1, ) Азбука на вътрешно състояние: Q = (q 0, q 1, q 2, q 3) Програма: ( 1) q 1 q 00 R, 2) q 11 q 20 R, 3) q 21 R, 4) q 2 q 31 L, 5) q 30 q 00 R, 6) q 31 L ) A) Начална дума: q 111 1 B) Начална дума: q 11 111

Тезата на Тюринг Тезата на Тюринг: за всеки алгоритъм A може да се изгради машина на Тюринг, която при същите начални данни дава същите резултати като алгоритъм A. n Ако 1 q 1 2 1 qz 2, тогава ще кажем, че машината T обработва дума 1 2 в думата 1 2 и я означете с T(1 2) = 1 2. n Нотацията T() е обозначението на машината T с оригиналните стойности.

Нормални алгоритми на Марков n Нормалните алгоритми на Марков (NAM) трансформират думи с крайна дължина една в друга чрез заместване. n Задача NAM Замени на азбука u v Окончателна замяна u v n Упражнение 29 Даден е нормалният алгоритъм на Марков: Азбука - азбуката на руския език. Схема за заместване (Y U, L U, S M, V B, RT, T R, O X, NA) n Начална дума СЛОН. n Намерете крайната дума.

Оценяване на сложността на алгоритмите n Нека приемем, че функциите f(n) и g(n) измерват ефективността на два алгоритъма, те обикновено се наричат ​​функции на времева сложност. Ще кажем, че редът на растеж на функцията f(n) не е по-голям от този на g(n), ако има положителна константа C, такава че | f(n) |

Ефективност на алгоритмите A B C D E n 3 n 2 2 n 2+4 n 3 2 n 1 ms 3 ms 6 ms 2 ms 10 10 ms 300 ms 240 ms 1024 s 100 ms 30 s 20,4 ms 0,28 h 4*1017 века 0. 56 часа 11.6 дни 10176 века 1000 ms 0,83 часа 1 ms

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

Класове P и NP n Клас на сложност P: има алгоритъм A, решаване на проблемив полиномиално време. n Клас на сложност NP - има алгоритъм А, който проверява предложеното решение за полиномиално време. n Проблемът с Хамилтоновия цикъл се състои в откриване дали дадена графика G има Хамилтонов цикъл и принадлежи към класа NP.

Примери за NP проблеми n Проблемът с изпълнимостта на булеви функции: като използвате дадена булева формула, открийте дали има набор от променливи, включени в нея, които я превръщат в 1. n Проблем с кликване: като използвате дадена графика, открийте дали тя съдържа клики (пълни подграфи) с даден размер. n Проблемът за съществуването на Хамилтонов цикъл в граф. n Съществуване на целочислено решение на система от линейни неравенства.

Възможност за решаване на NP проблеми чрез груба сила n Първоначално решението не е известно. Следователно се оказва важно, че всеки проблем, принадлежащ към класа NP, може да бъде решен за експоненциално време чрез търсене във всички възможни комбинации n Което се случва в алгоритъма за намиране на цикъл на Хамилтон

Връзка между P и NP n Всяка задача от P принадлежи на NP. n По този начин класът NP включва клас P. Към момента не е известно дали класовете P и NP са еднакви, но повечето експерти смятат, че не са.

Връзка между P и NP n Ако се окаже, че P = NP 1) Проблемите с NP ще бъдат разрешими за разумно време. 2) Има редица проблеми, които съзнателно използват проблеми с експоненциална сложност (т.е. приемайки, че проблемът не може да бъде решен). Например в криптографията има раздел за криптиране с публичен ключ, който е практически невъзможен за дешифриране. Ако внезапно P = NP, тогава много тайни ще престанат да бъдат такива.

NP–пълни проблеми n Най-сериозната причина да вярваме, че P ≠ NP е съществуването на NP пълни проблеми. n Неформално!!!, проблемът Q се свежда до проблем Q′, ако проблемът Q може да бъде решен за полиномиално време за всеки вход, като се приеме, че решението на проблем Q′ за някакъв друг вход е известно. Например проблемът с решаването линейно уравнениесе свежда до проблема за решаване на квадратно уравнение.

NP-пълни задачи n NP-пълна задача е задача от клас NP, към която може да се сведе всяка друга задача от класа NP. n NP-пълните проблеми образуват подмножество от „най-трудните“ проблеми в класа NP. Ако се намери алгоритъм за полиномиално решение за всеки NP-пълен проблем, тогава всеки друг проблем от класа NP може да бъде решен за полиномиално време. n Всички изброени NP-проблеми са NP-пълни. Включително проблема за цикъла на Хамилтън.

Представянето на краен автомат всъщност се свежда до описанието на функциите на автомата, които го дефинират.

Има три начина за дефиниране на крайни машини:

· Табличен (матрици на преходи и изходи);

· Графичен (с използване на графики);

· Аналитичен (с помощта на формули).

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

Табличен метод.Съставя се таблица на състоянието на машината за преходната функция – δ и изходната функция. В този случай:

· колоните на таблицата съответстват на елементи от въведената азбука X,

· редовете на таблицата съответстват на състояния (елементи от краен набор Q).

Пресечната точка на i-iред и j-та колона съответстват на клетка (i, j), която е аргумент на функции 8 и λ на автомата в момента, в който той е в състояние цина входа му е дума xj,и в най-подходящата клетка записваме стойностите на функциите 8 и λ. Така цялата маса отговаря на комплекта Q X X.

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

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

В матрицата на прехода, в пресечната точка на ред x k и колона q r, стойността на функцията на прехода δ(q i, X)и изходни функции λ(q, X). В някои случаи и двете таблици се комбинират в една таблица.

Графичен метод.

Автоматът се специфицира с помощта на графика, диаграма, графика и т.н. Специфицирането с помощта на насочен граф е по-удобна и компактна форма за описание на автомата.

Автоматна графикасъдържа

· върхове,отговарящи на състоянието циÎQ,

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

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

Разработване на скала за “уред за измерване на капацитет”

Фиг.2.5. Мащабна графика на устройство за измерване на капацитет

Заключение

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

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

В практическата част беше разгледана темата за енкодери, декодери, тяхното предназначение и бяха проектирани електрически функционални и електрически схеми на енкодери и декодери. Беше разкрита темата за картите на Карно. Разработен е и сегментът „b” на седемсегментния индикатор. Разработен е краен автомат за мащаба на устройство за измерване на капацитет, както и графика за него.

Баранов Виктор Павлович. Дискретна математика. Раздел 6. Крайни автоматии официални езици.

Лекция 31. Дефиниция и методи за специфициране на краен автомат. Задача за синтез. Елементарно автоИ ти

Лекция 30. ДЕФИНИЦИЯ И МЕТОДИ ЗА СПЕЦИФИКАЦИЯ НА КРАЙНА МАШИНА.

ПРОБЛЕМ ЗА СИНТЕЗ. ЕЛЕМЕНТАРНИ МАШИНИ

Конспект на лекцията:

1. Дефиниция на краен автомат.

2. Методи за специфициране на краен автомат.

1. Проблем със синтеза на автомати.
2. Елементарни автомати.
3. Проблемът за пълнотата на автоматната основа.
4. Каноничен метод за синтезиране на автомат.

1. Дефиниция на държавна машина

SFE не отчитат факта, че реалните устройства работят във времето. В сравнение със SFE, автоматът с краен резултат е по-точен модел на дискретен трансформатор b разработчик на информация. В същото време концепцията за краен автомат, като всеки модел, еаз въведени с редица опростяващи допускания.

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

Второ, предполага се, че времето се променя дискретно. Входните и изходните състояния съответстват на дискретна времева последователност Poscol b Тъй като моментът във времето се определя еднозначно от неговия индекс, тогава с цел опростяване ще приемем, че времето приема стойностите 1, 2, ..., ... Интервалът от време се наричатакт.

Работата на машината е представена по следния начин.

На входа на машината постъпват сигнали от входната азбука, което води до поява на сигнали на изхода от входната азбука. ЗА Зависимостта на изходната последователност от входа зависи от вътрешната структура на машината. Имайте предвид, че за разлика от SFE, които нямат памет, автоматът d е устройство с памет, т.е. изходът на машината се определя не само b към входа, но и към фона. Историята беше взета под вниманиеаз се определя от зависимостта на изходния сигнал не само от входния, но и от текущото състояние, което обозначаваме.

Нека дадем формална дефиниция на автомат.

Държавна машинаназовете пет обекта

, (1)

Къде

азбука за въвеждане; едно от възможните входни състояния;

крайно множество, наризходна азбука; елемент n Вие от този набор определяте възможните изходни състояния;

крайно множество, наразбука на вътрешните състоянияаз съм ;

– преходна функциямашина: ; тази функция присвоява състояние на всяка двойка "вход-състояние";

изходна функция машина: ; тази функция присвоява изходна стойност на всяка двойка вход-състояние.

Законът на действие на автомата: автоматът променя своите състояния споредТ функция и генерира изходни сигнали в съответствие с функциятада ция:

1. Методи за специфициране на краен автомат

1  . Табличен метод на присвояване. Тъй като функциите и домейнът са дефиниранид ции и стойности принадлежат към краен набор, те са посочени с помощта на таблици.

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

Таблица 1. Таблица на прехода Таблица 2. Таблица на изхода

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

2  . Графичен метод на задание.Използвани диаграма преход-изход.Това е ориентиран мултиграф, в който всекиТ Текущото състояние на автомата съответства на върха. Преходите на машината от състояние в състояние са изобразени със стрелки, на всяка от които е изписан входният символ, в s извикване на този преход и изходния символ, произведен от машината.

| | |

Фиг.1 Диаграма преход-изход

Пример 2. Необходимо е да се изгради автомат, който да работи по следния начин:А И така: при всеки тактов цикъл следващите двоични цифри на термините се получават на входа на машината и V доматът произвежда съответната двоична цифра от тяхната сума. За двамач условия на ред имаме: , .

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

00|0 11|1 01|0

01|1 10|0

10|1 00|1 11|1

ориз. 2

1. Проблем със синтеза на автомати

По аналогия с проблема за синтеза на SFE, можем да поставим проблема за синтеза за автоматиченА Другарю Има неограничен набор от основни машини. Необходимо е да се сглоби автоматична машина с предварително зададено функциониране. В същото време задачата за синтез е изправенаТ с определени проблеми.

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

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

Нека е краен набор от елементи и нека е множествод брой двоични думи с дължина, където. Ще наричаме произволно инжективно преобразуванекодиране на набор в двоични думи.

Нека кодираме азбуки за произволен автомат:

Нека обозначим съответно кодирания вход, изход и състояние на машината в даден момент. Тогава действащият закон ще бъде представен във формата

(2)

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

… …

ориз. 3

Преходът към структурен автомат осигурява две важни предимства за синтеза. e stva.

1 . Съвместимост на входове и изходи, тъй като двоичен ип образуване. Няма да дадем обща дефинициявериги от структурни автомати той е подобен на SFE.

2  . Нека запишем отношения (2) в „координати“:

(3)

От (3) следва, чезаконът за функциониране на структурния автомат е уточнен сИ Булева функционална система.

1. Елементарни автомати

Нека да идентифицираме най-простите структурни автомати и да им дадем имена.

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

Да преминем към автомати с две състояния. Нека машината има един двоичен вход и един двоичен изход, съвпадащи с вътрешното състояние:

ориз. 4.

За да укажете машината, показана на фиг. 4, достатъчно е да настроите само таблицата nд се движи:

Таблица 3

Вместо звездички трябва да поставите 0 и 1. Това може да стане по 16 начина, но не всички от тях са приемливи. Да предположим, например, че в първата колона на таблица 3 и двата елементап вие сте нули. Такъв автомат, веднъж в състояние 0, вече няма да излезе от него, тоест ще работи като функционален елемент. Анализът на подобни ситуации показва, че за да се получи автомат, който не се свежда до автомат без памет, е необходимоО Важно е всяка колона от таблица 3 да съдържа както нула, така и единица. Всички такива маси e g h e гума.

Таблица 4 Таблица 5

Таблица 6 Таблица 7

Имаме само два най-прости автомата, тъй като 7 се получава от 4, а 6 от 5 чрез обръщане на вътрешни състояния.

Извиква се автоматът, посочен в таблица 4забавяне или задействане:

това означава, че тази машина забавя сигнала с един такт.

Извиква се автоматът, посочен в таблица 5тригер с вход за броенеили -тригер . Състоянието на машината се обръща, ако на входа се получи 1, и остава непроменено, ако на входа се получи 0:

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

При физическо внедряване на тригери се използват два изхода:директен и обратен (фиг. 5). Ако ги разменим, тогава от- trigger ще доведе до автомат, определен от Таблица 7, и от- тригерен автомат, определен от таблица 6.

ориз. 5.

1. Проблемът за пълнотата на автоматната основа

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

Усилията на математиците да получат аналог на теоремата на Пост за автоматите не са се увеличили.п бяха успешни. През 1964 г. M.I. Накратко доказано несъществуването на алгоритъм за определянед на пълнотата на системата. В този случай представляват интерес варианти на теоремата за пълнота с допълнителни допускания за системата. Нека да разгледаме най-популярните от тях.

Теорема. система за автоматизация,съдържащ пълен комплект PV и -тригер (или -тригер) е завършен.

Доказателство. Помислете за произволен автомат, даден релациятад nyami (2) и описват веригата му от посочените автомати, наречениканонична структура(фиг. 6) .

Схемата се състои от две части.

…

…

…

ориз. 6.

Лявата половина се нарича складова част. Състои се от тригери, чийто набор от състояния формира състоянието на машината: ако в момента

, …,

тогава това означава, че машината е в състояние.

Дясна половинасе нарича комбинирана част и представлява SFE. Входове на тази верига:

1. двоичен входен сигнал на машината;
2. двоична дума текущо вътрешно състояние на машината.

Изходи:

1. двоична дума изходен сигнал на машината, която се реализираТ съгласно формули (3);
2. двоична дума, която отива на входовете на тригерите в паметтаА основна част и управлява паметта на машината.

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

Във всеки момент от време сигналите за управление на паметта трябва да преобразуват a V домати от щат до щат. За да направите това, трябва да промените състоянието на всеки тригер

, .

-тригерите или -тригерите, използвани в каноничната схема, имат следните свойства:д следното свойство: за всяка двойка състояния има входен сигналд шофиране на машина от щат в щат. Нека обозначим този сигнал с. За -тригер, тъй като състоянието, в което е зададен -тригерът, е равно на входния сигнал. За -тригер: на входа имате нужда от nО дайте 0, така че състоянието да не се променя; на 1, така че спусъкът да се „обърне“.

И така, или във векторна форма

Нека го изразим от закона за действие на автомата (2). Тогава

Теоремата е доказана.

1. Каноничен метод за синтезиране на автомат

Нека да разгледаме този метод с конкретен пример.

Пример. На конвейер, по който се движат два вида части и, V лен автомат, чиято задача е да сортира частите така, че след преминаване презд Докато минаваха покрай машината, те образуваха групи. Неподходяща машинна частл кима от поточната линия. Необходимо е да се изгради схема на такъв автомат с помощта на тригер и елементите "И", "ИЛИ", "НЕ".

Синтезът на автомата се разделя на следните етапи.

1 . Конструиране на абстрактен автомат.

Въвеждане на азбука. Изходна азбука , където C сблъсък на част, P пропускът й. Вътрешните състояния на автомата отразяват неговата памет за това коя част от групата вече е формирал: . Докато групата се формира, машината се движи циклично през тези състояния, без да променя състоянието, когато пристигне неподходяща част. Диаграмата преход-изход е показана на фиг. 7.

| | |

ориз. 7.

2  . Кодиращи азбуки.

Един от възможни вариантикодирането е дадено по-долуд следните таблици.

Състояние на входа и изхода

3  . Построяване на каноничната структура на автомата.

Каноничната структура на разработения автомат е показана на фиг. 8.

ориз. 8.

Нека намерим зависимостта на изходите на SFE от променливите, първо в таблична форма (Таблица 8), споредО с които по-нататък ще конструираме формули

, .

Таблица 8

Тези функции се наричатчастично дефиниран, тъй като те не са дефинирани в. За да се представят тези функции чрез формули, те се дефинират допълнително по такъв начин, че да се получи по-проста форма на формули.

4  . Представяне на машинни изходни функции и функции за управление на паметта r мулета.

Използвайки методи за минимизиране на булеви функции, ние конструираме, ако е възможно, eq.О Номинално представяне на функции, формули в основата:

5  . Изпълнение на SFE и крайната верига на машината (фиг. 9).

ориз. 9.

SFE

SFE

НЕ

ИЛИ