Асинхронды автоматтар

Асинхронды автоматтардың немесе дәлірек айтқанда автоматтың асинхрондық моделінің ерекшелігі кіріс сигналдарының қасиеттерімен анықталады. Бұндай автоматтың кіріс сигналдары импульстік түрдегі (6.1а суреті) сигналдарға ұқсас. Бұл кезде келесі шектеуліктер алынған болатын:

Сурет 6.1 - Импульсивті және потенциалды түріндегі сигналдар

- сигналдар автомат кірісіне үнемі периодты СИ реттілігі беретін нақты бір уақытта ғана түсе алады;

- кіріс сигналдарының ұзақтығы аз ;

- автомат кірісіндегі тактілейтін сигналдардың аралығындағы уақытта сигнал болмайды. Бұндай сигналдарға тұрғызылған автомат модельдері элементтерінде гальвандық байланысы жоқ импульстік типтегі сигналдармен жұмыс істейтін кестелерге сәйкес келеді.

Асинхронды автоматтың кіріс сигналдары потенциалды түрдегі сигналдарға (6.1б суреті) ұқсас. Бұндай сигналдарға келесі қасиеттер тән болу керек: - сигнал автомат кірісінде кез келген уақытта болады;

- кіріс сигналының ұзақтығына шектеулік қойылмайды және ол кейбір минималды мөлшерінен асады; кіріс сигналдары кез келген уақытта өзгеруі мүмкін.

Аталып өткен қасиеттер асинхрондық автомат үзіліссіз жұмыс істейді деп айтуға мүмкіндік береді.

Синхрондық автоматқа сияқты екілік кіріс сигналдарын қарастырумен шектелеміз. Және бұл жағдайда асинхрондық автомат моделі потенциал түріндегі элементтерден құрылған кестелерді мазмұндау үшін қолданылуы мүмкін. Айтарлық кіріс сигналының іс-әрекетінен синхронды автомат күйіне ауысады. Потенциалды түрдегі сигналдардың келтірілген қасиеттеріне сәйкес автомат кірісінде болады және аяқталуы алдын ала белгілі болмайтын ауысым орындалған соң ғана. Осыған сәйкес бұндай ауысым орындалған соң автомат келесі кірісте сигнал өзгерісі болғанға дейін күйінде қалу керек. Мазмұндалған жайды келесі анықтама түрінде қорытуға болады. Егер автомат күйінен іс-әрекет астында күйіне ауысым жасаса, яғни , және іс-әрекеті астында күйінде қалса, онда бұндай күй тұрақты деп аталады.

Асинхрондық автомат жұмысы да синхронды түрдегі автомат сияқты ауысым кестесі мен шығыс немесе граф көмегімен мазмұндалынады. Бірақ нөлдік емес ұзақтығы бар сигналдарға ауысу бұндай мазмұндауды қиындата түседі. Алдымен асинхрондық автоматты графты құру тәсілін берілген синхрондық автоматты графы бойынша құруға тоқталайық.

(6.2а) суретінде графы келтірілген синхронды автомат берілген делік. Бұл графты құру кезінде кіріс сигналдарының ұзақтығы есептелген жоқ. Егер де шығысқа берілетін импульстік сигналдар соңғы ұзақтыққа ие болады деп санасақ, онда әр сигналдың іс-әрекеті кезінде автомат қандай күйде болу керектігін анықтай қажет.

Бұны (6.2б) суретінде көрсетілгендей әр ауысымға берілген граф асинхронды автоматты анықтайды, себебі автоматың барлық жай-күйі ұрақты болып келеді.

Сурет 6.2 - Синхронды және оған сәйкес келетін асинхронды автоматының диаграммасы

Асинхронды автоматта барлық ауысымдар таблицаларын құру кзінде қосымша қиындықтар туғызатын тұрақты жай-күйлер арасында іске асырылады. Егер күйі тұрақты болып келсе, онда жолмен анықталатын, күйімен, бағанамен, кіріс сигналымен күйінің символы ауысым таблицасының торында жазылуы керек, себебі .

Осыдан асинхронды автомат ауысым таблицасының тұрақты күйі үшін кіріс сигналы өзгергенде автомат қандай күйге өзгеру керектігін көрсететін қосымша құралдар қажет. Бұл қиындық келесі тәсілмен шешіледі. Автомат күйінің өзгеру үрдісі екі кезеңге бөлінеді.

Алдымен кіріс сигналдары өзгереді де, автомат күйі өзгермейді, ал содан кейін кіріс сигналдарының жаңа мәндеріне сәйкес жай-күй де өзгереді. Бұл үрдістің бірінші кезеңіне ескі күймен белгіленген ауысым таблицасының жолында ауысу сәйкес келеді.

Сонымен, бірінші кезең сөзсіз автоматтың ауыспалы күйіне сәйкес келетін таблицаның жаңа торын анықтайды. Бұндай күйлерді транзитивті деп атайды. Бұл торда автомат көшетін күйдің символын жазып қоямыз.

Екінші кезеңдегі күйдің өзгеруіне жаңа кіріс сигналдарымен анықталған бағана бойынша ауысудың автомат көшу қажет күйімен белгіленген жолға көшу сәйкес келеді. Екінші кезеңде қолданылатын ауысым көрсеткіштері бар тұрақты күйге сәйкес келетін символдарды дөңгелек жақшаларға алатынымызды уәделесіп алайық.

Асинхронды автоматтың ауысым мен шығыс таблицасына мысал ретінде 6.1-кестені келтіруге болады. Бұл кесте (6.2б) суретінде келтірілген граф бойынша құрылған.

Кесте 6.1 - Граф бойынша құрылған

		-
			-
		-
			-
		-
		-
			-

6.1-кестеде ауысым қалай орындалатынын мысал негізінде қарастырайық. Айтарлық автомат 00 кіріс сигналдарының іс-әрекетінің астында 3 күйінде делік. Ауысым таблицасына сәйкес бұл күй тұрақты болып келеді. Егер енді кіріс сигналдарының 10-ға өзгерсе, онда автомат қандай күйге өзгеретінін табу үшін 10 сигналдарымен белгіленген үшінші жол бойынша бағанаға көшуді орындау қажет.

Бұл тәсілмен анықталған таблица торында автомат көшетін күйдің нөмірі бұл күйі-орналасқан. Тігінен 10 бағанасында жолына дейін жүре отырып бұл күйдің тұрақты екеніне көз жеткіземіз. Яғни бұл ауысым аяқталды деген сөз.

Қарастырылған мысалда бір тұрақты күйден екіншіге ауысқанда автомат бір транзиттік күйден құтқарылады. Жалпы жағдайда автомат күйінің өзгеруі бірнеше транзиттік күйлерден өтіп ауысуы мүмкін, бірақ олар ауысым таблицасының бір бағанасында орналасуы керек.

Дебиеттер

1 Дмитриев, В.И. Прикладная теория информации. – М.: Высшая школа, 1989. – 319 с.

2 Игнатов, В.А. Теория информации и передачи сигналов. – М.: Радио и связь, 1991. – 279 с.

3 Первозванский, А.А. Курс теории автоматического управления: учеб. пособие. – М.: Наука, 1986. – 300 с.

4 Перегудов, Ф.И., Ф.П. Тарасенко. Основы системного анализа – Томск: изд-во НТЛ, 1997. – 396 с.

5 Рейуорд-Смит, В.Дж. Теория формальных языков. Вводный курс. – М.: Радио и связь, 1988. – 129 с.

Мазмұны

Кіріспе………………………………………………………….........3

1 Формалдық тілдер мен грамматикалар…………………………....4

1.1 Формалдық грамматика мен тілдер анықтамасы……………........4

1.2 Формалдық грамматика типтері.......................................................7

1.3 Шығару ағашы. Сол жақты және оң жақты шығарулар…….........9

1.4 Көпмағыналы грамматикалар…………………………………......10

1.5 Грамматика кестелерін беру тәсілдері………………………........11

1.6 Грамматикаларды құру әдістері………………………………......13

1.7 Бағдарламалау тілінің жай конструкцияларын

мазмұндайтын грамматикалар……………………………………..17

2 Мәнмәтінді бос грамматикалар мен дүкендік автоматтар……….21

2.1 Тудырмайтын, жетпейтін және пайдасыз символдарды

анықтау.................................................................................................21

2.2 Оң жақты және шынжырлы ережелердің шығарылуы..................23

2.3 Қысқартылмайтын грамматикалар өзгеруі.....................................25

2.4 Дүкендік автоматтар.........................................................................26

2.5 Дүкендік автоматтар жұмысы..........................................................27

3 Азамайлы (бәсендейтін) және өрмелі

(жоғары көтерілуші) танушылар.......................................................28

3.1 Азаймалы танушылар және -грамматикалар.........................28

3.2 Детерминалданған азаймалы танушылардың тұрғызылуы.............29

3.3 Нашар бөлінген грамматикалар. -грамматикалар....................30

3.4 Дүкендік автоматтың тұрғызылуы....................................................33

3.5 Өрмелі танушылар..............................................................................35

3.6 Жою ережелері бар грамматикаларға арналған

өрмелі танушылар..............................................................................36

4 Ауысуды мазмұндау тәсілдері мен түрлендірушілер……………..39

4.1 Ауысуды мазмұндау тәсілдері мен түрлендірушілер......................39

4.2 Ауысу немесе трансляцияны мазмұндау.........................................42

4.3 Жақшасыз формулалар......................................................................43

4.4 Дүкендік жаңғыртушылар..................................................................44

5 Атрибуттық трансляциялау грамматикалары мен

Түрлендірушілер……………………………………………………..46

5.1 Атрибуттық трансляциялау грамматикалары

мен түрлендірушілер...........................................................................46

5.2 -грамматикаларын қолданумен жасалған

синтаксистік талдау.............................................................................48

5.3 -атрибуттық трансляциялау грамматикалары.

Атрибуттық түрлендірушілер ....................................................49

5.4 -грамматика ережелерін дүкенде көрсету.................................55

5.5 жұмысын мазмұндау....................................................................57

5.6 Өрмелі атрибуттық түрлендірушілерді тұрғызу..............................60

6 Автоматтардың құрылымдық синтезі.................................................62

6.1 Автоматтардың құрылымдық синтезі...............................................62

6.2 Асинхронды автоматтар.....................................................................65

Әдебиеттер……………………………………………………………69