«Соңғы автоматтар және формальдік тілдер теориясы»

Мили және Мур автоматтары иннициалды автоматтар емес. S(x)=g(q0,x) бейнелеуінде q0 бастапқы нұсқасын көрсетейік,сол уақытта автомат қалыпты жағдайда болады. Осы жағдай процестің қалыптасуына ықпал етеді, және кіріспе тізбектер мен нәтиже тізбектерін анықтайды.

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

Сондықтан да ең басты екі тапсырманы шешу керек:

1. 
   Автоматтың сол уақытта қай күйде тұрғанын анықтау;
   
2. 
   Берілген уақытта автоматтың жұмысты тоқтатқанына кейінгі соңғы түрде күйі.
   

Бұл анализ тапсырмалары байқаудың түрін анықтау деген атқа ие болған.

Мили автоматы

Мили автоматы – M=(K,X,Y,f,g) түріндегі бестік жүйе, бұл бестік жүйеде:

К-автомат түрінің жиыны;

Х-ену алфавиті

У-ену алфавиті

f-ауыстырулар функциясы (K*XK түрінде бейнелеуі)

g-шығу функциясы (У*XУ түрінде бейнелеуі)

Басқа автоматтар сияқты Мили автоматында кесте және графикалық түрде бейнелеуге болады.

Мили автоматының өту доғалын ‘/’ символы түрінде бейнелейді. Өту таблицалары екі түрден тұрады: функцияның сол жағында ену мәндері жазылады, ал оң жақта өту функциялары жазылады.

Мысалы, өңдеуші автомат құрайды, ол автомат грамматикалық берілген арифметикалық белгілеулерді оқитын болсын: - Sa+S|a-S|+S|-S|a және осы белгілеулерден унарлық операцияларды жояды. Мысалы, берілуі –а+-а-+-а ол мына түрге аударады в-а-а+а. Ену тілінде а символы идентификатор түрінде берілген және идентификатор алдында унарлы +и- операциясы түрінде. Қарастыра кететін жайт ену тілі қайталанба жиын болып табылады.

M=(K,X,Y,f,g)

К={q0,q1,q2,q3,q4}

Х={a,+,-}

У=X

Өту таблицасы келесі түрде болады

Логикалық блоктың соңғы автоматты формальды көпшілікпен автоматтардың қалпымен өте тығыз байланысты. Бұл қасиеттерді алгебралық әдіспен зерттеуге болады. Біріншіден, универсалды алгебрамен соңғы автоматтардың реализациясының байланыстары Хартманиса және Стирнза монографиясында «соңғы автоматтардың құрылымдық теориясы» зерттеген.

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

Шекті автоматтардың ішкі кодтау қалпы.

Автоматтарды ішкі қалпын кодтау функционалдық логикаға ешбір зиянын келтірмейді. Кодтауда автоматтың қалпы енгізу сигналдарына шығаруды орындайды. Қалыпты кодтау құрылғыға әсер етеді, оның жылдамдығына, логикалық блоктың қарапайым блогына әсер етеді. Мысалы, докладта іздеу нәтижесі шешіледі, ол элемент жадысының минималды күшіне әсер етеді. Бұл үшін анықталған типте екі қалыпты енгізілуі Химминг кодына байланысты болады.

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

А 1= автоматты 8 қалыптан тұрсын. S= {0,….,7} және енгізу сигналдарының, а және в – дан тұрады. µ автоматының көшу функциясын келесі таблицада көрсетілген.

	а	b
0	3	4
1	4	7
2	3	0
3	2	6
4	1	5
5	1	4
6	2	3
7	4	3

Логикалық функцияны қарастырайық, олардың А1 автоматтардың көшу реализациясы А1-ің ішкі қалпының кодталуы үш түрлі жолмен өтеді. Кодталудың бірінші нұсқасы екілік кодтық қалып нөмірінен тұрады. Көшу таблицасындағы кодталу Карно картасына қолдануы минимальды ДНФ екілік функцияның құрылуымен түсіндіріледі. Триггерлердің блоктық жадысы кодталуда енгізу сигналдары x=0 үшін а және x=1 үшін в. Бұл нұсқада кодтау әрбір фнкциясы Q₁ Q₂ Q₃, екілік разрядты келесі қалыптан, үштік мағынада тұратын q₁ q₂ q₃ кодының ағымдағы қалпынан көруге болады.

Сондықтан а1 автоматы мұндай кодталудан тұрады. В схемасын құрайық, оның әрбір қадамында бірінші екі разрядты кодтық қалыпты А1 (Q₁ және Q₂) разрядымен ағымдағы қалыпты А1 (q₁ және q₂) қарастырылады. Бұл варияндты басқа көзқарастан қаратырайық, екілік кодталудың әрбір разряды S қалыпта жаңа разрядта тобынан анықталады. Таблица 3.5. В көшуінің кестесі.

	µа	µв
<0, 7>	<3, 4>	<3, 4>
<1, 2>	<3, 4>	<0, 7>
<3, 4>	<1, 2>	<5, 6>
<5, 6>	<1, 2>	<3, 4>

А1 автоматының кодталу қалпының үшінші нұсқасын қарастырайық. Ол үшінші разрядтары код мағынасымен ерекшеленеді.

Осы нұсқада кодталу кезінде әр функция Q1, Q2, Q3, екілік разрядтары кодын келесі жағдайларда яғни үш мағынасында да q1, q2, q3 автомат жағдайларынан туелді болады.

Ал енді, ADE аралас моделдеріне арналған шекті автоматтардың ішкі жағдайларының кодталуын қарастырайық, содан кейін бұл әдісті AD, AE және BF моделдеріне қарастырамыз. Кодтау жолы олардың барлық ішкі жағдайларын өзара әр түрлі болуымен аяқталады. Сонымен қатар шекті автоматттың барлық ішкі жағдайлары кодттары ортогональды болуы қажет. Шекті автоматтың енгізу-шығару жиынтықтары, жиын айнымалы мағынасымен анықталады G = {g₁,...,g_L} және Z = {z₁,...,z_N}, осы тапсырманы жиі шешеді. Одан кейінгі шешу жолы минималды сан R және де қосымша айнымалылар e₁,...,e_R Е жиыны және екілік санау жүйесімен кодталған жеке топтардың кодталуымен шешіледі. Алдыңғы жағдайдағыдай [1,2], бағандары a_m, a_ы, X(a_m,a_ы) и Y(a_m,a_ы) болатын шекті автомат кестесі берілген. ADE аралас моделді ішкі жағдайларының кодталуын үшінші ретті матрица арқылы W шешіледі. Матрица жолдары шекті автоматтың ішкі жағдайларына сәйкес келеді, ал бағандары жиын айнымалылары, яғни G және Z. Жолдардың қиылысуы кейбір a_i, a_i - болып тавбылады.
Бақылау сұрақтары:

1. Детерминантты шекті автоматтар түсінігі. Мур диаграммалары

2. Шекті автоматтардың эквиваленттілігі. Мур теоремасы.

3. Мили и Мур автоматтарының айырмашылығы неде?

4. Шекті автоматтардың алгебралық құрылымдық теоремасы. Шекті автоматтардың ішкі жағдайларын кодтау.

Дәріс №5. ТЬЮРИНГ МАШИНАСЫ

1. 
   Тюринг машинасы, фон Нейман автоматы.
   
2. 
   Бір қалыпты өрнек бойынша детерминант емес шекті автомат құру. Детерминант емес шекті автомат бойынша детерминант автомат.
   

Алан Матисон Тьюринг (1954-1954) ағылшын инженері әрі математигі. Оның ғылыми еңбектері, көбінесе, математикалық логика мен есептегіш машина жұмысының негіздемелік мәселелерін зерттеуге және уағыздауға арналған. Кибернетика ғылымы мен электронды есептегіш машиналар теориясының негізін алғаш қалаушы Норберт Виннер (1894- 1964) : «Тьюринг расында, ғалымдардың ішіндегі ойша тәжірибе жүргізу арқылы машиналардың логикалық мүмкіндігін тұңғыш зерттнген адам болды.

Тьюринг машинасы дәлді математикалық ұғым болып табылады. Оны ешұқашан кездеспейтін және ұшы қиыақырсыз жады бар механикалық құрылым деп қарастырады.

Анықтама: Тьюринг машинасы (ТМ) деп ұзындықтары бірдей шаршы ұяларға бөлінген ақырсыз таспамен және уақыттың әрбір моментінде таспаның мазмұнын есепке алатын жаңа белгілеменіжазатын және таспаны жылжытатын Д тетіктен жабдықталған А ақырсыз автоматты айтады.

Тьюринг машинасы соңғы автоматтандырудың жай моделі болып табылады.

Қарастырайық, Тьюринг машинасы мен жай модельдік автоматтың айырмашылығын.

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

Функционалдық автоматты бейнелеуді оның программасы ретінде санауға блады: онда 4 – тік санау жүйесі қолданылады < s, a, p, y> - бұл өткен қалып, а – келесі енгізілген сигнал, р – келесі қалып және у – кезекті шығару сигналы. Соңғы автомат программасы аргуметерді санайды, және функцияның нәтижесін шығарады: S*X – S*Y

A b b a c a c b

Басыныңың

Басының қозғалысы қозғалысы

Соңғы автоматтық басқару

Соңғы автоматтық бпсқару.

Y z z u

Шығару лентасы MT = ( S, X, Y,

А = (S,X, Y, O) Г = ( L, R, H)

&: S*X S*Y &: S*X S*Y*Г

Программа: Программа

1. (s, a) (p, y) 1. ( s, a) (p, y, l )

2. (q, b) (s, z) 2. (q, b ) (s, z, R )

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

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

Тьюрингтің айтуы бойынша формальдық модельдің соңғы автоматтан айырмашылығы ол – 2 аспект бойынша орындалады.

1. 
   Ол шексіз жұмыс лентасын қамтамасыз етеді, онымен ол символдарды қайда жазуды және оқуды біледі.
   
2. 
   Жазудың басы онымен ол жұмыс лентасында кез – келген жаққа қозғалуы мүмкін.
   

ұндағы: S,A,P және У – сол мағынаны береді, ол Д жұмыс лентасының басын қозғалтуды қамтамасыз етеді. Ол 3 мағынада айтылады. L – солға, R- оңға, және Н – орында қалу. Екінші сөзбен айтқанда бұл программа соңғы бестің тізбегі. Тьюринг машинасы бірінші соңғы жұмыстық Х алфавитін емденеді, онда енгізу және шығару символы ол лентада теріледі, машина келесі такт бойынша оқиды. Ыңғайына қарай Х элементі бос символдарды құрайды.

Қарастырайық: ТЬЮРИНГ машинасы қалай жұмыс істеитінін.

Тьюринг машинасының конфигурациясын оның өткен қалпы деп атайды. Программаны атқаруда тактта конфигурация өзгереді.

Тьюринг машинасының тоқтаған кезінде енгізу тізбегінде өңдеу нәтижесі шығады. Осыған орай программа автомвтты символдық тізбек болып табылады. Тьюринг машинасы көптеген тізбектерді түсіндіруіде мүмкін. Бұл программада арнаиы қалыптар беріледі немесе «!» және программа түсіндіруші ретінде берілсе енгізу лентасы бос болады.

Тьюринг машинасы тоқтаған кезде қалып өзгереді және ақпаратжұмыс лентасында енгізу ақпаратымен өңделеді.

Тьюринг машиналарының қасиеттері.

Тьюринг машиналарының бірнеше қасиеттерін қарастырайық.

Теорема. Әрбір Тьюринг машиналарына эквиваленция орындалу керек.

Дәлелдеуі: Тьюринг машинасының шығаруында эквиваленттік ережелер орындалады.

Теорема. Әрбір Тьюринг машинасына орта шексіз лента эквиваленциясы орындалады.

Дәлелдеуі: Бұл теорема конструктивтік, біз оған алгоритм берейік . Ол Тьюринг машинасы бойынша құрылады. 1-ден жұмыс летентасында ұяшықтарды нөмірлейік

Содан кейін ұяшыққа «*» символын берейік

Тьюринг машинасын қарастыру

Тьюринг машинасын қарастырудың сұрақтарын қарастырайық. Қазіргі кездегі копьютерлерде шексіз аналогтар берілген. Олар Тьюринг машинасының жұмыс лентасында орналасқан. Ол бес команда арқылы орындалады.

Команда	түсіндірмесі
Қозғалу (солға, оңға)	Басын 1 – жақ лентаға оңға немесе солға қозғалту.
Көшу, Р	Сөзсіз р нөмерімен с командасына өту
Егер s, p,	Шартты өту Р нөмерімен С командасына , егер ұяшықта S символы блоса.
Басу, S	S символының ұяшықта басылуы.
тоқтау	тоқтату

Мысалы Тьюринг машинасының программасының басы мына түрлерді ұсынады.

00: егер а , 0,2; /* егер бастапқы қалыпта а символы оқылса онда 02*/командасына

01: өту, 0,5; /* егер жоқ болса басқа символ*/

02: басу, а

03: жылжыту, солға;

04: көшу, 00; /*бастапқы қалыпқа көшу*/

05: егер, в 07; /* егер бастапқы қалыпта в символы оқылса , онда 07*/командасына

06: көшу , /* егер жоқ болса басқа символға */

07: басу, в;

08: қозғалту солға;

09:.........

Бұл мысалдан келесі нәтижені шығаруға болады. Автоматты есептеу құрылғысы кез келген алгоритмді орындай алады. Тьюринг машинасының енгізу лентасының шексіз аналогы ретінде 5 операция орындалады. Оның мағынасы универсалды есептеу машинасы болып табылады.

Егер Тьюринг машинасы шексіз лентада жұмыс атқарса, онда универсалды Тьюринг машинсы оның жұмысын көшіріп алуы мүмкін.

Универсалды Тьюринг машинасын қарастыру оқырманға жаттығулар арқылы беріледі.

2. Бір қалыпты өрнек бойынша детерминант емес шеткі автомат құру.

Детерминант емес шекті автоматтар – есептеу теориясында қолданылатын модель.

жүктеу 14,81 Mb.

Достарыңызбен бөлісу: