Автомати Начини за настройка Основни дефиниции n Краен. Методи за настройка на цифрови автомати Крайни автоматични начини за настройка и основни свойства

Основни дефиниции на n Краен автомат е система M =(А, B, S, y), в която n n n А = (а 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 Създайте автомат за търсене на думата CAKADU 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) \u003d 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) ако = 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 Теорема: За всеки автомат на Мили съществува еквивалентен автомат на Мур. 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, S9)

Неразличими състояния 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, намерете автомата с най-малък брой състояния - минималния автомат.

Аспекти на „работата“ на автоматите n Могат да се разграничат два основни аспекта на „работата“ на автоматите: 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 Control 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 Посочен е нормален алгоритъм на Марков: Азбуката е азбуката на руския език. Схема на заместване (I U, L U, S M, V B, R T, T R, O X, N A) n Начална дума SLON. 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 n 3 2 n 1 1 ms 3 ms 6 ms 2 ms 10 10 ms 300 ms 240 ms 1024 s 100 ms 40 s 30 s 1 h 6 ms 10 ms 10 ms 10 ms 10 ms дни 10176 века 1000 ms 0,83 h 1 ms

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

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

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

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

Връзка между Р и 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-пълни. Включително и проблема за цикъла на Хамилтън.

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

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

Лекция 30 ОПРЕДЕЛЕНИЕ И МЕТОДИ ЗА ОПРЕДЕЛЯНЕ НА КРАЕН АВТОМАТ.

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

План на лекцията:

1. Определение на краен автомат.

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

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

1. Определение на държавна машина

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

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

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

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

Входът на автомата получава сигнали от входната азбука, което води до появата на сигнали на изхода от входната азбука. Уа Зависимостта на изходната последователност от входната последователност зависи от вътрешната структура на автомата. Имайте предвид, че за разлика от SFE, които нямат памет, автоматът preд е устройство с памет, т.е. изходът на автомата се определя не самоб към входа, но и към задната история. История счетоводствоаз се определя от зависимостта на изходния сигнал не само от входа, но и от текущото състояние, което означаваме.

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

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

, (1)

където

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

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

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

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

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

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

1. Начини за дефиниране на държавна машина

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

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

Таблица 1. Таблица за скокове Таблица 2. Изходна таблица

Вход	състояние

Вход	състояние

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

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

| | |

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

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

Автоматът е в състояние 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, достатъчно е да посочите само таблицата pд преходи:

Таблица 3

Вход	състояние

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

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

Вход	състояние
					Вход	състояние

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

Вход	състояние

Вход	състояние

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

Автоматът, даден от Таблица 4, се наричазабавяне или тригер:

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

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

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

Когато тригерите са физически реализирани, се използват два изхода:директни и обърнати (фиг. 5). Ако ги разменим, тогава- тригер, получавате автомат, определен от таблица 7, и от- тригер - автоматът, посочен в таблица 6.

Ориз. 5.

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

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

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

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

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

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

…

…

…

Ориз. 6.

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

, …,

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

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

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

Изходи:

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

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

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

, .

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

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

Нека изразим от закона за функциониране на автомата (2). Тогава

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

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

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

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

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

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

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

| | |

Ориз. 7.

2 . Азбучно кодиране.

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

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

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

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

Ориз. осем.

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

, .

Таблица 8

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

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

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

5 . Реализация на SFE и крайната схема на автомата (фиг. 9).

Ориз. девет.

SFE

SFE

НЕ

ИЛИ

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

държавна машинанаречена система Y, Q> , където X и Y са крайни входни и изходни азбуки, Q е краен набор от вътрешни състояния,Й (x, q) - преходна функция иВ (x,q) - изходна функция.

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

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

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

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

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

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

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

Лекция 30

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

План на лекцията:

1. Определение на краен автомат.

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

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

1. Определение на държавна машина

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

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

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

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

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

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

Състоянието е набор от пет обекта

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

е краен набор, наречен изходна азбука; елементите на това множество дефинират възможните изходни състояния;

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

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

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

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

1. Начини за дефиниране на държавна машина

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

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

Таблица 1. Таблица за скокове Таблица 2. Изходна таблица

	състояние

	състояние

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Отделяме най-простите структурни автомати и им даваме име.

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

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

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

Таблица 3

	състояние

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

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

	състояние
					състояние

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

	състояние

	състояние

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

Автоматът, даден от Таблица 4, се нарича забавяне или -тригер:

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

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

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

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

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

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

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

Теорема. Система от автомати, съдържаща пълен набор от FE и -тригер (или -тригер) е завършена.

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

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

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

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

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

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

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

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

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

Използваните в каноничната схема -тригери или -тригери имат следното свойство: за всяка двойка състояния има входен сигнал, който прехвърля автомата от състояние в състояние. Нека обозначим този сигнал с . За -trigger, тъй като състоянието, в което е зададен тригерът, е равно на входния сигнал. За -trigger: когато, 0 трябва да се приложи към входа, така че състоянието да не се промени; при -1 за завъртане на спусъка.

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

Нека изразим от закона за функциониране на автомата (2). Тогава

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

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

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

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

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

1. Построяване на абстрактен автомат.

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

2. Кодиране на азбуки.

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

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

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

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

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

Таблица 8

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

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

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

5. Реализация на SFE и крайната схема на автомата (фиг. 9).

ОПРЕДЕЛЕНИЕ И МЕТОДИ ЗА ОПРЕДЕЛЯНЕ НА КРАЕН АВТОМАТ. ПРОБЛЕМ ЗА СИНТЕЗ. ЕЛЕМЕНТАРНИ АВТОМАТИ

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

На входния канал по всяко време т =1, 2, ... към устройството М пристигат входни сигнали (от някакъв краен набор от сигнали). Законът за промяна на състоянието към следващия момент от време се задава в зависимост от входния сигнал и състоянието на устройството в текущия момент от време. Изходният сигнал зависи от състоянието и входния сигнал в текущото време (фиг. 1).

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

държавна машина наречена система A= (х , В , Й ,  ,  ), където х , В , Й са произволни непразни крайни множества и  и  - функции, от които:

няколко х ={а 1 , ..., а м ) е наречен входна азбука , а неговите елементи са входни сигнали , техните последователности са в крилати фрази ;

няколко В ={q 1 , ..., q н ) е наречен много държави автомат и неговите елементи - държави ;

няколко Й ={б 1 , ..., б стр ) е наречен изходна азбука , неговите елементи са изходни сигнали , техните последователности са изходни думи ;

функция  : х  В В Наречен преходна функция ;

функция  :х  В Й Наречен изходна функция .

По този начин,  (х , q )В ,  (х , q )Й за  х х , q В .

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

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

Има няколко еквивалентни начина за дефиниране на абстрактни автомати, три от които са: табличен , геометрична и функционален .

2.1 Таблица за присвояване на машината

От определението за автомат следва, че той винаги може да бъде дефиниран от таблица с два входа, съдържащи т линии и П колони, където в пресечната точка на колоната q и линии а стойностите на функциите си заслужават  (а и , q j ),  (а и , q j ).

q а	q 1		q j		q н
а 1	(а 1 , q 1),  (а 1 , q 1)		(а 1 , q j ),  (а 1 , q j )		(а 1 , q н ),  (а 1 , q н )
а и	(а и , q 1),  (а и , q 1)		(а и , q j ),  (а и , q j )		(а и , q н ),  (а и , q н )
а м	(а м , q 1),  (а м , q 1)		(а м , q j ),  (а м , q j )		(а м , q н ),  (а м , q н )

2.2. Дефиниране на автомат чрез диаграма на Мур

Друг начин за определяне на машина с крайно състояние е графичен, тоест използването на графика. Автоматът е представен като обозначена насочена графика г(В , д ) с много върхове В и много дъги д ={(q j ,  (а и , q j ))| q j В , а и х ), докато дъгата ( q j ,  (а и , q j )) е обозначен с чифт ( а и ,  (а и , q j )). Така при този метод състоянията на автомата се изобразяват с кръгове, в които се въвеждат символите на състоянията q j (j = 1, …, н ). От всеки кръг се извършва т стрелки (насочени ръбове) едно към едно, съответстващи на знаците от входната азбука х ={а 1 , ..., а м ). Стрелка, съответстваща на буквата а и х и напускане на кръга q j В , Двойката ( а и ,  (а и , q j )), и тази стрелка води до кръг, съответстващ на  (а и , q j ).

Полученият чертеж се нарича автоматна графика или, Диаграма на Мур . За не много сложни автомати този метод е по-илюстративен от табличен.