Кіріспе
Қазіргі кезде ақырлы автоматтарды бағдарламалауда қолдану қайтадан өрби түсуде, мысалы логикалық басқару аймағы мен объектілі – бағыттлаған бағдарламалауда. Мур және Мили ақырлы автоматтарын тағайындалуы жалпы бағдарламалауда қолдану ұсынылады. Сонымен қатар ақырлы автоматтарды қолданудың бір сұрағы болып әртүрлі трансляторлардағы алгоритмдік тілдердің синтаксикалық анализі болып табылады. Атақты қолдануларда автоматтардың кіру ақпаратын есептеу үрдісі сәйкес, іске асыратын автоматтың, бағыныңқы бағдарламалар мен мысалдардың шегіне шығарылды.
Автоматтар теориясы — теориялық кибернетиканың дискретті ақпараттың түрлендіргіштерін зерттейтін саласы. Ол есептеуіш машиналарды жобалауға және биология, экономика тағы басқа күнделікті өмір талабы аса қажет еткен ғылым салаларындағы ақпараттарды қайта өңдеу процестерінің математикалық модельдерін жасауға байланысты пайда болды.Автоматтар теориясы Автоматтар теориясының негізі абстракт автомат пен автоматтар композициясы ұғымдарынан тұрады. Абстрактілі автомат ұғымы қарастырылатын қондырғыны, яғни өзі жүзеге асыратын ақпараттарды қайта өңдеу алгоритмі тұрғысынан сипаттайды. Автоматтар композициясы қондырғыны оның құрылысы тұрғысынан қарастырады. Қазіргі автоматтар теориясы — сан алуан мәселелері бар және жан-жақты қолданылатын дербес ғылым саласы.
1 Автомат түсінігі
Автомат – бұл қандай да бір жиынды анықтайтын алгоритм, мүмкін болған жағдайда ол жиынды басқа жиынға түрлендіруі мүмкін. Автоматтардың формальсыз сипатталынуы келесі түрде болады: автомат кіру лентасынан, күйдің нөмірін сақтайтын ақырлы жадысы бар басқару құрылғысынан тұрады, сонымен қатар көмекші және шығыстық лентасы болуы мүмкін. Автоматтардың екі типі бар:
1) танығыштар – шығыссыз автоматтар, олар кіру тізбегі берілген L жиынына тиісті ме соны таниды;
2) түрлендіргіштер – шығысы бар автоматтар, олар x ∈ L шарты орындалғанда кіру тізбегі х –ті у тізбегіне түрлендіреді.
Кіру лентасын ұяшықтардың сызықтық тізбегі ретінде қарастыруға болады, әрбір ұяшық ақырлы кіру алфавитінің бір символын сақтай алады.
Автоматтың лентасы шексіз, бірақ әрбір уақыт моментінде ұяшықтардың тек ақырлы саны ғана бос емес болады. Бос емес аймақтың шекаралы оң және сол жақтағы ұяшықтары арнайы соңғы маркерлерді алуы мүмкін. Маркер лентаның тек бір жақ соңында ғана тұруы немесе мүлдем болмауы мүмкін.
Кіру бас тиегі әрбір уақыт моментінде кіру лентасының бір ұяшығын оқиды. Автоматтың бір жұмысының тактісінде енгізу бастиегі бір ұяшық оңға жылжуы немесе бір орында тұруы мүмкін, мұндайда ол тек қана оқуды орындайды, яғни автоматтың жұмыс істеу барысында кіру лентасының ұяшықтарындағы символдар өзгермейді.
Жұмыс лентасы - ақпаратты сақтаудың көмекші қоймасы. Ондағы берілгендер автоматтың көмегімен оқылады және оған жазылуы да мүмкін.
Басқару құрылғысы – автоматтың тәртібін басқаратын бағдарлама. Ол кіру бастиегімен оқылатын ағымды кіру символына сәйкес күйдің және жұмыс лентасынан алынып тасталған ағымды ақпараттың қалай өзгеретінін сипаттайтын, бейнелеуі бар күйлердің ақырлы жиынын береді Басқару құрылғысы жұмыс бастиегінің жылжу бағытын және жұмыс лентасына қандай ақпарат жазу керектігін анықтайды. Автомат жұмыс тактілерінің қандай да бір тізбегін орындай отыра жұмыс істейді. Тактінің ең басында кіру символы оқылады және жұмыс лентасындағы ақпарат зерттеледі. Одан кейін оқылған ақпарат пен ағымды жағдайға байланысты, автоматтың іс - әрекеті анықталады:
1) кіру бастиегі оңға жылжиды немесе бір орында тұрады;
2) жұмыс лентасына қандай да бір ақпарат жазылады;
3) басқару құрылғысының жағдайы өзгереді;
4) шығу лентасына (егер ол бар болса) символ жазылады.
Автоматтың жұмыс істеу тәртібін автоматтың конфигурациясы терминімен сипаттаған ыңғайлы, ол келесіден тұрады:
а) басқару құрылғысының жағдайы;
б) кіру лентасындағы берілгендер кіру бастиегінің жағдайымен бірге;
в) жұмыс лентасындағы берлігендер кіру бастиегінің жағдайымен бірге;
г) шығу лентасындағы берілгендер, егер ол бар болса.
Басқару құрылғысы детерминделмеген болуы мүмкін. Мұндай жағдайда әрбір конфигурация үшін тактілердің ақырлы жиыны бар болуы мүмкін, оның әрқайсысын автомат осы конфигурациядан шыға отыра жасайды. Басқару құрылғысы детерминделген болады, егер әрбір конфигурация үшін тек бір ғана келесі такт мүмкін болса.
Автоматтардың келесі типтері болады: 1) Тьюринг машинасы (ТМ); 2) сызықты – шектелген автомат (США); 3) магазиндік жадысы бар автомат (МЖ- автомат); 4) ақырлы автомат (АА).
Ақырлы автоматтың күрделігін автоматтың күрделілігі анықтайды. Мысалы:
1) Тьюринг машинасы екі жаққа да шексіз ленталардан тұрады;
2) сызықты – шектелген автоматтарда жұмыс лентасының ұзындығы кіру тізбекшесінің ұзындығының сызықтық функциясын береді;
3) МЖ-автоматта жұмыс лентасы LIFO магазинінің принципімен жұмыс істейді;
4) ақырлы автоматтарда жұмыс лентасы болмайды.
Автоматтың формальды анықтамасы
Инициалданбаған автомат – бұл А = (К, X, Y, δ, γ) түрдегі бестік, мұндағы К – күйлердің жиыны (күйлердің алфавиті); Х – кіру алфавиті; Y – шығу алфавиті; δ – К: Х→К бейнелеуді беретін өту функциясы; γ – К: Х→У бейнелеуді беретін шығу функциясы.
Автоматтың функцияларын келесі түрдегі командалардың жиыны ретінде беруге болады: qx → py, мұндағы q және p ∈ K, x ∈ X, y ∈ Y.
ti қайсыбір тактісінде басқару құрылғысы q жағдайда болсын, ал кіру лентасынан x символы оқылсын делік. Егер командалардың жиынында qx → py командасы бар болса, онда ti тактісінде шығу летасына у символы жазылады, ал келесі ti +1 тактісінде басқару құрылғысы р жағдайына өтеді, яғни:
y(t) = γ(q(t), x(t)), q(t-1) =δ(q(t), x(t)).
Егер qx → py командасы болмаса, онда автомат бұғатталады және ti моментінде қабылданған символға ешқандай әсер білдірмейді, сонымен қатар уақыттың келесі моментіндегі символдарды да қабылдамайды.
Инициалданбаған автоматтың анықтамасына сәйкес, жағдайдың алғашқы сәтінде автомат ерікті болуы мүмкін.
Егер қандай да бір алғашқы жағдай алдын – ала бекітілген болса, онда мұндай автоматты инициалданған автомат деп атайды, яғни q(0) = q0.
Инициалданған автомат – бұл А = (К, X, Y, δ, γ, q0) түріндегі алтылық, мұндағы К – жағдайлардың жиыны (жағдайлардың алфавиті); Х – кіру алфавиті; Y – шығу алфавиті; δ - өту функциясы (К: Х → К бейнелеуі); γ – шығу функциясы (К: Х → У бейнелеуі); q0 – алғашқы жағдай.
Глава 1. Автоматтардың эквивалентілігі
Автоматтардың эквиваленттілігін кіру символдарының тізбегіне реакциясының бірдейлігімен анықтайды, демек шығу символдарының тізбегі бірдей болып құрылады.
Автоматтың үлгісі үш негізгі алгебраны көрсететіндіктен, сондықтан екі автоматты салыстыруда X, Q және Y көпшелерін бейнелейтін үш операторды табу қажет, олар бір автоматтың үлгісін құраушылары келесі бір автоматтың үлгісін құраушыларына сәйкес келуі керек. Содан кейін осы операторларды әрбір автоматтың өту функциялары және шығу символдарына қандай әсер тигізетінін тексеру қажет. Егер автоматтар бірдей тізбектелген кіру символарына бірдей тізбектелген шығу символдарын генерацияласа, онда автоматтар эквивалентті болып табылады.
Екі абстрактілі автоматтың үлгісін қарастырамыз:
(1)
Мына операторлар берілсін:
(2)
Егер өту және шығу функцияларын орындалуы барысында шарт орындалса:
(3)
онда (f;g;h) операторларының жиынтығы М1 автоматының үлгісі М2 автоматының үлгісіне гомоморфты бейнелеуді құрады, ал x1k X1 y1j Y и q1i Q1 әрбір мәні бойынша x2k X2 y2j Y2 q2i Q1 жалғыз түрде сәйкестенеді.
Мына операторлар берілсін:
(4)
Егер өту және шығу функцияларын орындалуы барысында шарт орындалса:
(5)
онда -1 f-1;g-1;h-1 операторларының жиынтығы М2 автоматының үлгісі М1 автоматының үлгісіне гомоморфты бейнелеуді құрады, ал x2k X2 y2j Y и q2i Q2 әрбір мәні бойынша x1k X1 y1j Y1 q1i Q1 жалғыз түрде сәйкестенеді.
Егер ( -1) операторларының жиынтығы табылса, ол үшін
-1= -1 =1, (6)
онда өзара әрекетті бейнелеу изоморфты деп аталады.
Изоморфты бейнелеу рефлексивті, симметриялы және транзитивті болып келеді. Автоматтардың эквивалентілігін тексеру үшін әсіресе f=1 болғандағы жағдай қызықты болып табылады. Шарт (3) және (5) бойынша xk X үшін мынадай болады:
(7)
Егер 1(q1i;xk) және 2(q2i;xk) шығу функцияларының мәні барлығына xk X сәйкес келетін q1i және q2i бар болса, онда
1(q1i;xk)= 2(q2i;xk), (8)
онда g=g-1=1, h(q1i)=q2i, h-1(q2i)=q1i. Сонымен қатар Y1=Y2=Y тең болады. Мұндай q1i және q2i жағдайларды автоматтар шығуы бойынша айнымайтындар деп атайды.
Айнымайтын жұп (q1i;q2i) (Q1 Q2) жағдайларды қарап шығу нәтижесінде бірнеше ішкікөпшелерді табуға болады, олар (Q1 Q2) көпшелерін шығу жағдайы бойынша айнымайтындар класына бөледі.
Егер айнымайтын жағдайдағы (q1i;q2i) жұптар үшін өту функциясының мәні барлық символдар үшін xk X құрайды және ( (q1i[ ];xk[ ]); (q2i[ ];xk[ ])) айнымайтын жағдай жұптары да q1i және q2i сәйкестенген жағдайлар деп аталады. Осындай қарап шығудың нәтижесінде барлық айнымайтын жағдайдағы бір кластың жұптары сәйкес жағдайлы кластарға бөлінуін құрайды.
q1i және q2i жағдайлары эквивалентті болады, егер барлық кіру тізбегіне =(x1x2...xn) шарты орындалады:
М1(q1i; )=М2(q2i; ), (9)
Сондықтан әрбір кіру =(x1x2...xn) символының тізбегі үшін ( (q1i[ ];xk[ ]); (q2i[ ];xk[ ])) өту функцияларының мәнінің өзгеруін қарап отыру керек.
Барлық (q1i;q2i) жұптарының көпшесі шартын орындайтын болса, онда эквивалентті жағдайлар класын құрайды.
Егер екі автоматтың да кіру және шығу алфавиттері сәйкес келсе, онда M2 автомат M1 автоматын жабады, егер 2(h(q1i); )= 1(q1i; ) барлығы үшін Xn, онда M1 автомат M2 автоматты жабады, егер осы екі автоматтың кіру және шығу алфавиттері ортақ және 1(h-1(q2i); )= 2(q2i; ) барлығы үшін Xn.
Изоморфизм шарты бойынша M1 және M2 автоматтары эквивалентті, егер M1 автоматы M2 автоматын жабады және M2 автоматы M1 автоматын жабады. Эквивалентті автоматтардың q1i және q2i эквивалентті жағдайлары бар болады.
Егер М1 және М2 эквивалентті автоматтар үшін Q1 Q2 болады, онда m1 = Q1 жағдай саны кем болатын М1 автоматы m2 = Q2 жағдай саны көп болатын М2 автоматын жабады. Аз жағдай саны бар автоматпен жаба алмайтын автоматты минималды деп аталады.
q1i және q2i эквивалентті жағдайларды іздестіру үшін екі автоматтың өту кестелерінің жұбын қолданған ыңғайлы. Әрбір жұптың сол элемент М1 автоматының жағдайы, ал оң элемент М2 автоматының жағдайы. Осындай кестенің сол бағаны ажыратылмас жұптардың жағдайларын көрсетуге арналған, олар шығу кестелері бойынша келесі ережемен құрылады:
"егер Q1 және Q2 екі автоматының көп жағдайларының ішінен (q1;q2) жұбы табылады, олардың шығу функцияларының мәні әрбір символдың кіру алфавиті xk X, т.е. 1(q1i;xk)= 2(q2i;xk) мәніне тең, демек q1 және q2 жағдайлары ажыратылмас;"
Кестелердің орындары ретінде екі автоматтың жұп жағдайы саналады, олар xk кіру символының автоматына жіберу кезіндегі ажыратылмас жағдайлардың жұбына сәйкес жіберіледі. Кезекті жағдайлардың мәні М1 және М2 автоматтардың өту кестелері бойынша символа xk X, т.е. (q1= (q1i;xk); q2 = (q2i;xk)) сәйкес символы үшін іздеп табылуы мүмкін.
Екі автоматтың жұп өту жағдайларының кестесі 1 кестесінде көрсетілген. Мұндағы жұптар ажыратылмас жағдайлар кестенің сол бағанында келтірілген (q1i;q2j), (q1j;q2p), (q1p;q2s), (qs;q2i).
Кесте 1
ажыратылмас жағдайлардың ағымдағы (q1;q2)
xi X алфавитінің кіру символдары
x1
x2
...
xn
...
...
...
...
...
(q1i;q2j)
(q1i;q2j)
(q1j;q2p)
...
(q1s;q2i)
(q1j;q2p)
(q1i;q2j)
(q1p;q2p)
...
(q1s;q2i)
(q1p;q2s)
(q1j;q2p)
(q1j;q2p)
...
(q1j;q2p)
(q1s;q2i)
(q1s;q2p)
(q1p;q2j)
...
(q1j;q2i)
...
...
...
...
...
Кестенің талдауы көрсетеді:
1) q1i және q2j жағдайлары сәйкестенген, себебі кіру алфавитінің әрбір символын қабылдау кезінде М1 және М2 автоматтарының жағдайы ажыратылмас жағдайлы жұптардың қатарына өтеді;
2) q1p және q2s жағдайлары сәйкестенген, себебі кіру алфавитінің әрбір символын қабылдау кезінде М1 және М2 автоматтарының ажыратылмас жағдайы бір ажыратылмас жағдай жұбында қалады;
3) q1j және q2p жағдайлары сәйкестенбеген, себебі x2 символын қабылдауда М1 және М2 автоматтарының ажыратылмас жағдайлары ажыратылмас жағдайлардың әр түрлі жұптарына өтеді;
4) q1s және q2i жағдайы сәйкестенбеген, себебі кіру алфавитінің әрбір символын қабылдауда М1 және М2 автоматтарының ажыратылмас жағдайлары әр түрлі ажыратылмас жағдайларының жұбына өтеді.
Сонымен М1 және М2 автоматтары жағдайлары сәйкес келсе де, өзара эквивалентті болып табылады.
Мысал. M1= X1;Y1;Q1; 1 1 автоматы берілсін, мұндағы X1 {0;1}, Y1 {0;1}, Q1={q11;q12;q13}, 1 және 1 (1.20 кестесін қараңыз) және M2= X2;Y2;Q2; 2 2 автоматы, мұндағы X2 {0;1}, Y2 {0;1}, Q2={q21;q22}, 2 және 2 (1.21 кестесін қараңыз).
М1 автоматының графы суретте көрсетілген, М2 автоматы суретінде көрсетілген. М1 және М2 автоматының эквивалентілігін табу керек.
Кесте 2
Кесте 2
ағымды жағдай q Q1
x X1 кіру алфавитінің символдары
ағымды жағдай q Q2
x X2 кіру алфавитінің символдары
0
1
0
1
q11
q13;0
q12;1
q21
q21;0
q22;1
q12
q11;1
q13;0
q22
q21;1
q21;0
q13
q11;0
q12;1
1-сурет. М1 автоматының графы
2-сурет. М2 автоматының графы
М1 және М2 автоматтары үшін шығу бойынша (q11;q21), (q12;q22) және (q13;q21) жағдайлар жұбы ажыратылмас болып табылады. Сонымен бірге ажыратылмас жағдайлардың екі класы құрылады {(q11;q21);(q13;q21)} және {(q12;q22)}.
Егер (q11;q21) ажыратылмас жұбы үшін кіру символы "0" болса, онда М1 және М2 автоматтары (q13;q21) ажыратылмас жағдайлар жұбына өтеді, ал кіру символы "1" болса, онда (q12;q22) ажыратылмас жұбына, онда М1 автоматының q11 жағдайы және М2 автоматының q21 жағдайы сәйкестенген болып саналады.
Егер (q12;q22) ажыратылмас жұбы үшін кіру символы "0" болса, онда М1 және М2 автоматтары (q11;q21) ажыратылмас жағдайлар жұбына өтеді, ал ал кіру символы "1" болса, онда (q13;q21) ажыратылмас жұбына, онда онда М1 автоматының q12 жағдайы және М2 автоматының q22 жағдайы сәйкестенген болып саналады.
Ең соңғысы, егер (q13;q21) жыратылмас жұбы үшін кіру символы "0" болса, онда М1 және М2 автоматтары (q11;q21) ажыратылмас жағдайлар жұбына өтеді, ал ал кіру символы "1" болса, онда (q12;q22) ажыратылмас жұбына, онда онда М1 автоматының q13 жағдайы және М2 автоматының q21 жағдайы сәйкестенген болып саналады.
Егер М1 автоматының q13 жағдайы М2 автоматының q21 жағдайымен сәйкестенген, ал М2 автоматының q21 жағдайы М1 автоматының q11 жағдайымен сәйкестенген, онда транзитивті қасиеті бойынша М1 автоматының q11 жағдайы М1 автоматының q13 жағдайымен сәйкестенген.
Автоматтардың эквиваленттілігін тексеруді бірдей тізбектлеген символдарды әрбір автоматпен және шығудағы тізбектелген символдарды талдау арықыл орындау мүмкіндігі бар.
М1 автоматы үшін q11=q0 және = (01010101) бар болсын. Сонда кіру сөзін өңдеу процесі келесі тізбектерді құрады:
кіру: 0[1] 1[2] 0[3] 1[4] 0[5] 1[6] 0[7] 1[8];
q: q11[1] q13[2] q12[3] q11[4] q12[5] q11[6] q12[7] q13[8] q12[9];
шығу: 0[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8],
онда 1 (01111111).
М2 автоматы үшін q21=q0 және =(01010101) бар болсын. Сонда кіру сөзін өңдеу процесі келесі тізбектерден құралады:
кіру: 0[1] 1[2] 0[3] 1[4] 0[5] 1[6] 0[7] 1[8];
q: q21[1] q21[2] q22[3] q21[4] q22[5] q21[6] q22[7] q21[8] q22[9];
шығу: 0[1] 1[2] 1[3] 1[4] 1[5] 1[6] 1[7] 1[8],
онда 2 (01111111).
Сонымен М1 және М2 автоматтары эквивалентті. Себебі М2 автомат ішкі жағдайлардың аз санын болса, онда ол М1 автоматын жабады.
3 Эквивалентті автомат құру
Бір филиантроп ашқан пансионда атақты бес философ жиналады. Жұмыс барысында олар бір-бірінен тәуелсіз асханаға түстену үшін кіріп шығады. Асханада үстел тұрады және оның айналасында орындықтар қойылған. Әр философтың өз орындығы бар. Философтың сол жағында шанышқы жатыр, ал үстелдің ортасында үлкен табақта спагетти тұр. Спагеттиді тек екі шанышқының көмегімен ғана жеуге болады, сондықтан философ түстенуге отырғанда көршісінің жатқан шанышқысын алуына(егер ол бос болса ғана) тура келеді.
Осы жүйенің үлгісін жасау мәселесінен басқа, оны талдаудың мәселесі де бар. Өйткені, мынадай ықтималдық бар, қайсы бір философ тамаққа тиісе алмауы да мүмкін, себебі шанышқы біреуі немесе екеуі де тұрақты түрде бірдей бос болмаса (көршілер келісімі деп аталатын жағдай). Ал егер олар үстелге барлығы бір уақытта отырса, барлық философтар өзара блоктауға түсіп қалу нұсқасы бар.
Құрылымдық үлгі
Тапсырманың құрылымдық ұлгісін бес параллельді блоктар ретінде қарастыруға болады. Сонымен қатар бір блок ішіне философ пен сол жағында жатқан шанышқыны біріктіру ыңғайлы болады. Блоктар өзара әрекеті көршілер түстену кезінде бір-біріне ресурс - шанышқыларын беріп отырғанда іске асады. 1-суретте философшанышқы блогы көрсетілген.
3-сурет. Философтың құрылымдық сұлбасы
Ол үш кіру және үш шығу арналы болып келеді. Кіру арналары бойынша келесі сигналдар келеді:
"шанышқы керек" 1 – сол жақтағы көршісінің шанышқы сұрауы;
"шанышқылар бос" 2 – сол жақтағы көршісі шанышқыны босатты деген ақпарат;
"шанышқыны алуға болады" 3 – оң жақтағы көршісі оның шанышқысын сұрауы.
Ал шығу арналары бойынша ақпараттар:
"шанышқыны алуға болады" 4 – сол жақтағы көрші шанышқыны алуына болады;
"шанышқы керек" 5 – оң жақтағы көршісінен шанышқыны қайтаруды сұрайды;
"шанышқылар бос" 6 – философ тамақтанды және шанышқылар бос (оң жақтағы көршісінен алынғаны да).
Текстік түрде құрылым деңгейі мынадай болады:
(1,2,3)-ФN-(4,5,6)
4-суретте блоктар деңгейінде философтарды байланыстыратын құрылымдық сұлба келтірілген.
4-сурет. Философтарды байланыстыру сұлбасы
Текстік түрде бұл сұлба мынадай болады:
(Ф5(5),Ф5(6),Ф2(4))-Ф1-(Ф5(3),Ф2(1),Ф2(2)),
(Ф1(5),Ф1(6),Ф3(4))-Ф2-(Ф1(3),Ф3(1),Ф3(2)),
(Ф2(5),Ф2(6),Ф2(4))-Ф3-(Ф2(3),Ф4(1),Ф4(2)),
(Ф3(5),Ф3(6),Ф3(4))-Ф4-(Ф3(3),Ф5(1),Ф5(2)),
(Ф4(5),Ф4(6),Ф4(4))-Ф5-(Ф4(3),Ф1(1),Ф1(2)).
Иерархиялы құрылымның тағы бір деңгейін енгіземіз. Мұнда "философшанышқы" блогы "шынышқы", "қызметші" және "философ" блоктарынан құралады. Шанышқының құрылымдық үлгісі 5-суретте келтірілген. 1,2 арналары бойынша "оған" сол жақтан "қызметшіден" шанышқы керек және шанышқы босады деген ақпараттар келіп түседі. 3,4 арналары бойынша тура сол секілді оң жақтағы "қызметшіден" ақпарат келеді. 5 шығу арнасына сол жақтағы қызметшіге "шанышқы" алуға болады деген ақпарат, ал 6 арнадан – оң жақтан.
5-сурет. Шанышқының құрылымдық үлгісі
Текстік түрде "шанышқы" құрылымдық үлгісі:
B: (1,2,3,4)-B-(5,6);
"Қызметші" құрылымдық үлгісі 6-суретте көрсетілген. Оған 1,2 арналары арқылы шанышқылар бос деген ақпараттар келіп түседі (сәйкесінше сол және оң жақтағы шанышқы), ал үшінші арқылы – философтың түстік туралы өтініші. Төртінші шығу арнасы бойынша қызметші шанышқыға сұраныс жасайды, ал бесіншісі шанышқылардың босады деген ақпарат береді, алтыншысы философқа түстенуге мүмкіндік береді.
6-сурет. Қызметшінің құрылымдық үлгісі
Текстік түрде:
C: (1,2,3)-C-(4,5,6),
5-суретте жалпы "философшанышқы" блогының құрылымдық сұлбасы графикалық түрде бейнеленген (сұлба құрамында "фил" блогы да көрсетілген, философқа сәйкес, бірақ оны қарапайым болғандықтан қарастырмаймыз).
7-сурет. Философ блогының құрылымдық сұлбасы
Ішкі және сыртқы байланыстарды есептеумен "философшанышқы" блогының құрылымдық сұлбасының текстік түрі былай болады:
ФN:
(C(4),C(5),3[1],4[2])-B-(C(1),6[4]),
(B(5),2[3],3)-C-(б(1)[5],B(2)[6],6).
Тік жақшадағы цифрлар жоғарғы деңгейдегі байланыстарконтакттардың "есімдерін" құрайды. Берілген жағдайда ФN блогының контакті нөмірлерін. Өйткені сұлбадан "фил" блогы алынып тасталынған, әрі қарай "қызметші" 3 блоктың кіру контактісіне философтан қызметшіге "түстенгім келеді" сигналы түседі, ал алтыншы контактіден "түстік берілді" деген қызметшіден философқа сигнал беріледі.
Шанышқының автоматты үлгісі
Енді блоктардың жұмыс алгоритмі деңгейінде функционалды сипаттауына кірісеміз. Бұл үшін ақырғы автомат үлгісін аламыз – бөлек блок үшін және параллельді деңгейде жұмыс істейтін автоматтар желісін. Шанышқының іс-әрекетін үлгілейтін автомат арналары арсындағы сәйкестік және шанышқының құрылымдық арналар үлгісі 6-суретте көрсетілген (шығу арнасындағы шеңбер автоматтың ішкі жағдайға "қосылып" тұрғанын білдіреді).
8-сурет. Шанышқы блогы
9-сурет. Шанышқы автомат графы
Оның сипатталуы талдау формасы келесідей түрде болады:
P: ps = {pl(x1-), pr(^x1x3-)}, pl = {ps(x2-)}, pr = {ps(x4-)}.
Мұндағы (Р) автоматты үлгінің арналарының көрінуі (В) оның құрылымдық контактілер келесідей болады: (6-суретті қараңыз):
P-б: x1-1, x2-2, x3-3, x4-4, pl-5, pr-6.
Жоғарыда жазылған автоматтарды сипаттауды талдаудың түрі бульдік функцияларға сәйкестенеді. Бульдік функция секілді ол арқылы дұрыс автомат толығымен анықталғанша толықтыруы анықталады. Берілген жағдайда Р автоматының толықтыруымен P' толығымен анықталған автоматқа дейінгісі келесідей болады:
^P: ps = {ps(^x1^x3-)}, pl = {pl(^x2-)}, pr = {pr(^x4-)}.
Сонымен P' толығымен анықталған автомат, жұмыс істеу алгоритмі деңгейінде блоктың құрылымдың үлгісі мына өрнекпен анықталады:
P' = P ^P
Бұдан, толық анықталған автоматқа дейінгі ^P толықтырушысы мына өрнекпен анықталады:
^P = P' - P
Бұдан осыған ұқсас автоматтық толықтырушылар шығу жиынтықтары жоқ көптеген автоматтық графтардың түйінін көруге болады.
Автоматтың шанышқы үлгісінде pl жағдайында сол жақтағы көршіге шанышқыны алуына, ал pr жағдайында оң жағындағы көршісіне шанышқыны алуына рұқсат беріледі (9-сурет). Шанышқыны белгілеу стратегиясының ерекшелігі сол жақтағы философқа шанышқы әрдайым беріледі, ал оң жақтағы философқа шанышқы тек "өзінің" философының сұранысы болмағын жағдайда ғана тиесілі болады (басымдылықты өзгертуге болады сөзсіз, бірақ ол басқа автомат болып шығады). "Шанышқы" автоматына сәйкес "қызметші" автоматы да құрастырылған. Оның құрылымдық деңгейі 10-суретте, ал графтың 11-суретте бейнеленген.
10-сурет. Қызметші автоматының құрылымдық сұлбасы
11-сурет. Қызметші автомат графы
Оның талданған түрі мынадай болады:
F: f1 = {f2(x5-)}, f2 = {f1(x6x7y1)}.
мұндағы F-C: x5-3, x6-2, x7-1, f2-4, f1-5, y1-6.
^F автоматының толықтырушысы F' автоматына дейін мына түрде болады:
^F: f1 = {f1(^x5-)}, f2 = {f2(^x6-), f2(^x7-)}.
Мұндағы f1 жағдайы қызметшіге (философқа) шанышқы керек емес немесе түстіктен кейін босаған кезі, ал f2 жағдайы шанышқылардың сұраныс жағдайы. Қызметші f2 жағдайына x5=1 болғанда кіреді, осы кезде философ түстікке деген өтініш білдіреді.
Сетевая автоматная модель блока "философвилка"
Компонент үлгілерінен "философшанышқы" блогының жалпы үлгісін құруға болады. Оның автоматты желі түріндегі графы 12-суретте келтірілген.
12-сурет. ФилософШанышқы автомат үлгісі
Оның талданған түрі келесідей көрсетіледі:
P: ps = {pl(f2-), pr(f1x3-)}, pl = {ps(f1-)}, pr = {ps(x4-)}. (3)
F: f1 = {f2(x5-)}, f2 = {f1(plx6y1)}. (4)
мұндағы x5 – философтың қызметшіге "түстенгім келеді" деген сигналы, ал y1 - қызметшінің философқа "түстенуге болады" деген сигналы.
ФN блогының кірушығу "контактілері" келтірілген. (ескерейік, оның функционалды үлгісі – М желілік автоматты үлгісі - P және F автоматтарды параллель байланыстыру,M = PF):
x3-1, x4-2, x6-3, pr-4, f2-5, f1-6
Желілік үлгінің автоматтық графында пунктирлі бағыттауыштармен ақпараттық және желідегі автомат компоненттерін синрондаушы байланыстар бейнеленген. Графикалық бейнелеуде синхрондау үшін Петри желісіндегідей "полочка" әйкес келетін "полочка" енгізілген. Талдау түрінде синхрондаушы ақпарат автоматтар жағдайының аттары арқылы көрінеді, олар өз кезегінде компонентті автоматтардың кіру айнымалыларына сәйкес келеді. Мысалы, х1 айнымалысы f2 жағдайына сәйкес келеді, ал ^x1 - f1 және т.с.с.
Эквивалентті автоматты құру үшін бізге желідегі компонентті автоматтардың толықтырулар керек болады, олар бұл жағдайда келесідей:
^P: ps = {ps(f1^x3-)}, pl = {pl(f2-)}, pr = {pr(^x4-)}.
^F: f1 = {f1(^x5-)}, f2 = { f2(pr-), f2(ps-), f2(^x6-)}.
Желі жалпы бір алгоритмді жүзеге асырады, ол көптеген параллельді функционалды жұмыс жасайтын автоматтарға эквивалентті автоматпен көрсетіледі. Жүйені сипаттауға желілік көрсетілім ыңғайлы, себебі эквивалентті түрінен гөрі ықшамдау болып табылады. Оны құру да жеңілірек, жүйені бір үзіммен алгоритм әрекетін анықтап салыстыру арқасында автоматтың компоненттерін құрамыз. Осымен бірге эквивалентті автомат арқылы жүйенің жұмысын бақылау қайда жеңілрек болады. Желілік автомат үлгісінің эквивалентті берілген мысалы түрінде көруге болады.
"Философшанышқы" эквивалентті автомат
Бізге P және F автоматы берілген. M автоматы екі автоматтың параллельді эквивалентті жұмысына мына өрнекпен анықталады:
M = P F = P ^F ^P F P F,
мұндағы – автоматтардың параллельді көбейтудің алгебралық операциясы. Автоматтардың жетілген түрімен және қосымшаларын қолдана отырып, формуланы құрайтын элементтерді табамыз:
P ^F:
psf1 = {prf1(x3^x5-)}, psf2 = { plf2(--)},
plf1 = {psf1(^x5-)}, plf2 = {-},
prf1 = {psf1(x4^x5-)}, prf2 = {psf2(x4-)}.
^P F:
psf1 = {prf2(x3x5-)}, psf2 = {-},
plf1 = {psf2(x5-)}, plf2 = {-},
prf1 = {psf2(x4x5-)}, prf2 = {-}.
P F:
psf1 = {prf2(x3x5-)}, psf2 = {-},
plf1 = {psf2(x5-)}, plf2 = {-},
prf1 = {psf2(x4x5-)}, prf2 = {-}.
Ақырғы:
P F = P ^F ^P F P F:
psf1 = {prf1(x3^x5-), psf2(^x3x5-), prf2(x3x5-)},
psf2 = {plf2(--)},
plf1 = {psf1(^x5-), psf2(x5-) },
plf2 = {plf1(x6y1)},
prf1 = {psf1(x4^x5-), prf2(^x4x5-), psf2(x4x5-)},
prf2 = {psf2(x4-)}.
Эквивалентті автоматтың графикалық түрі 13-суретте көрсетілген. Суретте желідегі автоматтардың компонентті символдарынан эквивалентті автоматтың жағдайларының атаулары берілген.
Философтың мінез-құлығын талдау
Эквивалентті біркомпонентті үлгісі шанышқы-қызметші-философ жүйесін бүтін түрінде толық көрсетеді. 13-суретке қарап, s2-l2-l1-s2 жағдайлаымен құрылатын циклға көңіл аудару керек. Автомат циклданады егер l2 жағдайынан l1 жағдайына өту кезінде x5 айнымалысы ("түстенгім келеді") шындық мән болады. Бұл аш философтың мысалына сәйкес, демек l2-l1 өту кезінде, осыдан қайта түстенгісі келеді.
13-сурет. философшанышқы блогына эквивалентті М автоматы
Мүмкіндігі аз, себебі философ бір автоматтық такт ішінде түстеніп үлгермейді, бірақ берілген жағдайда түстіктің "жылдамдығы" сыртқы философтың үлгісі, мысалы қарапайым мынадай түр болады:
D: d1 = {d2(-y1)}, d2 = {d1(-y2)}.
Мұнда y1 әрекеті айнымалыны сәйкес x5 сигналына нөл орнатады, ал y2 бірлікті орнатады.
Үлгі циклданған жағдайдан басқа тұйықталу ықтималдығын және көрсетеді. Бұл барлық автоматтар өзінің бастапқы жағдайынан s1 (х5=1 болғанда) бір-екі секірістен (дискретті тактілер) бір сәтте l2 жағдайына түседі, мұндағы (x6=0 болғанда) тоқтап қалады, себебі оң жақтағы көршісіне көрсетілген. Бірақ тұйықталу болмайды, егер автоматтың бірінде болсын "түстенгім келеді" сигналын алмайды. Онда s1 жағдайында r1 жағдайына көше отырып, көршісіне шанышқыны (x3=1) береді
Философ r1 жағдайында да тоқтап қалуы мүмкін, егер белгілі бір себептермен көршісі оған қайтармайды. Шынайы өмірде мынадай болады, бірақ біздің үлгіде көршісі шанышқыны алып, оны қайтармауы мүмкін емес. Біріншіден, сондықтан ол өз шанышқысын тек мына жағдайда береді, егер ол өзіне керек болмаса (pr жағдайына өту 8 суретте қарау), ал шанышқыны бергеннен соң, қайта сұрай алмайды, себебі шанышқының қайтуын күтеді. Екіншіден, егер оның шанышқысы бос болса, онда түстенгісі келсе, "шанышқы" компоненті pl жағдайына өтеді, сосын өзінің шанышқысын алып, ал қызметші f2 жағдайына өтеді, көршісінің шанышқысын сұранысына. Сонымен көрші өз шанышқысын сұрай алады, егер өзіндікісін "бекітсе". Сондықтан ол шанышқысын беріп, оның қайтарылуын күтуге құқылы, себебі көршісіне түстенуге тағам берілген, түстенген соң, шанышқыларды босатуы керек.
14-суретте "философшанышқы" блогының күрделірек үлгісі көрсетілген. Әрбір философқа тарелка берілген (Q автоматы) анық түрде енгізілген және философтың үлгісі (D автоматы). Сонымен қатар жаңа үлгілерді санау арқылы және олардың өзара әрекеттесуі мен олардың арасындағы қызметшінің үлгісі өзгертілген (F автоматы). "Шанышқы" автоматы және "философшанышқы" блогы деңгейінде сыртқы ортамен байланысының құрамы өзгертусіз қалады. Екі суретті қарағанда 13-сурет графында алты жағдай бар, ал 14-суретте 72 жағдай бейнеленген.
14-сурет. философшанышқы блогының төрткомпонентті үлгісі
f1 – шанышқы бос
f2 – шанышқы керек
f3 – шанышқы берілді
f4 - түстену
q1 – тарелка бос
q2 - тарелка толтырылған
y2 – тарелканы толтыру
d1 - философ тоқ
d2 - философ аш
d3 - түстенеді
y1 – түстіктің жартысы
Тұйықталу болмауы үшін қосымша блок енгізу керек, ол үстелге философтарды бір сәтте жібереді. Бұл жағдайда барлық сұраныстар үшін оларды сүзгілеу керек. Егер сұраныстар философтың санына байланысты сұраныс санына тең түссе, онда кез келген сұранысты кес дегенде бір автоматты тактіде ұстауы керек. Ал қалған жағдайда барлық сұраныстар тоқтатусыз жіберіледі. Шынайы өмірде бұл блок ретінде автоматты есік болуы мүмкін.