Шанышқының автоматты үлгісі

Кіріспе

Қазіргі кезде ақырлы автоматтарды бағдарламалауда қолдану қайтадан қарқын алып келеді. Бұл үрдіс, әсіресе, логикалық басқару жүйелерінде және объектіге бағытталған бағдарламалауда байқалады. Мур және Мили автоматтарының үлгілерін жалпы бағдарламалауда қолдану да жиі ұсынылады.

Ақырлы автоматтарды қолданудың маңызды бағыттарының бірі — әртүрлі трансляторлардағы алгоритмдік тілдердің синтаксистік талдауы. Классикалық қолдануларда автоматтың кіріс ақпаратын өңдеу үдерісі оны іске асыратын автоматтың, бағыныңқы бағдарламалардың және мысалдардың шегінде қарастырылады.

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

Автоматтар теориясы: негізгі ұғымдар

Автоматтар теориясының негізі екі іргелі ұғымнан тұрады: абстрактілі автомат және автоматтар композициясы.

Абстрактілі автомат

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

Автоматтар композициясы

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

Қазіргі автоматтар теориясы — көптеген мәселелерді қамтитын, кең қолданылатын дербес ғылым саласы.

Автомат түсінігі

Автомат — қандай да бір жиынды анықтайтын алгоритм; қажет жағдайда ол бір жиынды басқа жиынға түрлендіре алады.

Формальды емес сипаттама

Автомат кіріс лентасынан, күй нөмірін сақтайтын ақырлы жадысы бар басқару құрылғысынан тұрады. Сонымен қатар жұмыс (көмекші) және шығыс ленталары болуы мүмкін.

Автоматтардың негізгі типтері

Танығыштар — шығыссыз автоматтар; берілген кіріс тізбегінің L жиынына тиістілігін анықтайды.
Түрлендіргіштер — шығысы бар автоматтар; x ∈ L болғанда кіріс тізбегін x-тен y-ке түрлендіреді.

Кіріс лентасы

Ұяшықтардың сызықтық тізбегі ретінде қарастырылады: әр ұяшық кіріс алфавитінің бір символын сақтай алады. Лента шексіз деп алынады, бірақ кез келген уақытта бос емес ұяшықтардың саны ақырлы болады.

Шекара ұяшықтарында арнайы соңғы маркерлер болуы мүмкін (кейде бір жақта ғана немесе мүлде болмауы да ықтимал).

Бастиек (оқу механизмі)

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

Жұмыс лентасы және басқару құрылғысы

Жұмыс лентасы — ақпаратты сақтайтын көмекші қойма: деректер оқылады және жазылады.

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

Бір такт кезіндегі әрекеттер

1 Кіріс бастиегі оңға жылжиды немесе орнында қалады.
2 Жұмыс лентасына ақпарат жазылады (қажет болса).
3 Басқару құрылғысының күйі өзгереді.
4 Шығыс лентасына символ жазылады (егер шығыс лентасы болса).

Конфигурация ұғымы

Автоматтың жұмыс істеу күйін сипаттау үшін конфигурация термині қолданылады. Ол мыналарды қамтиды:

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

Детерминделмеген басқару

Әр конфигурация үшін келесі такттің бірнеше мүмкін нұсқасы болуы мүмкін.

Детерминделген басқару

Әр конфигурация үшін келесі такт бір ғана нұсқамен анықталады.

Автоматтардың түрлері және күрделілік

Автоматтар жұмыс жадысының ұйымдасуына және мүмкіндіктеріне қарай келесі типтерге бөлінеді:

Тип	Ерекшелігі
Тьюринг машинасы (ТМ)	Екі жаққа да шексіз ленталармен жұмыс істей алады.
Сызықты-шектелген автомат (США)	Жұмыс лентасының ұзындығы кіріс тізбегінің ұзындығына сызықтық тәуелді.
Магазиндік жадысы бар автомат (МЖ-автомат)	Жұмыс жадысы LIFO принципімен (стек) ұйымдасады.
Ақырлы автомат (АА)	Жұмыс лентасы болмайды; күй саны ақырлы.

Автоматтың формальды анықтамасы

Инициалданбаған автомат

Инициалданбаған автомат мына бестікпен беріледі: A = (K, X, Y, δ, γ), мұнда:

K — күйлер жиыны (күйлер алфавиті);
X — кіріс алфавиті;
Y — шығыс алфавиті;
δ — өту функциясы: δ: K × X → K;
γ — шығу функциясы: γ: K × X → Y.

Командалар арқылы сипаттау

Автоматтың әрекеті командалар жиыны ретінде берілуі мүмкін: qx → py, мұнда q, p ∈ K, x ∈ X, y ∈ Y.

Егер qx → py командасы бар болса, онда ағымдағы тактте шығысқа y жазылады, ал келесі тактте күй p-ке өтеді. Команда болмаса, автомат бұғатталып, әрі қарай символдарды қабылдамайды.

Инициалданған автомат

Егер бастапқы күй алдын ала бекітілсе (q(0) = q0), онда автомат инициалданған деп аталады және мына алтылықпен беріледі: A = (K, X, Y, δ, γ, q0).

Глава 1. Автоматтардың эквиваленттілігі

Автоматтардың эквиваленттілігі кіріс символдары тізбегіне реакциясының бірдейлігімен анықталады, яғни бірдей кіріске бірдей шығыс тізбегі құрылуы тиіс.

Эквиваленттіліктің түйіні

Екі автомат бірдей кіріс тізбектеріне бірдей шығыс тізбектерін генерацияласа, олар эквивалентті.
Салыстыруда, әдетте, кіріс (X), күй (Q) және шығыс (Y) жиындарын байланыстыратын бейнелеулер қарастырылады.

Изоморфты бейнелеу туралы

Егер екі бағытта да гомоморфты бейнелеулер анықталып, олардың композициясы сәйкестік бейнелеуге тең болса, онда бейнелеу изоморфты деп аталады. Изоморфты бейнелеу рефлексивті, симметриялы және транзитивті қасиеттерге ие.

Тәжірибеде, әсіресе f = 1 жағдайы маңызды: кіріс алфавиті бірдей болғанда, эквивалентті күйлерді табу есепті айқын жеңілдетеді.

Ажыратылмас (шығыс бойынша айнымайтын) жұптар

Егер екі автоматтың (q1; q2) күйлер жұбы үшін кіріс алфавитінің әрбір символында шығу функцияларының мәндері тең болса, онда бұл күйлер жұбы ажыратылмас (шығыс бойынша айнымайтын) деп аталады.

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

Минималды автомат ұғымы

Егер эквивалентті автоматтардың ішінде бір автомат күйлер саны жағынан ең аз болып, оны одан да аз күйі бар автомат «жаба» алмаса, онда ол автомат минималды деп аталады.

Мысал: M1 және M2 автоматтарының эквиваленттілігі

Екі автомат берілсін: M1 (күйлері {q11, q12, q13}) және M2 (күйлері {q21, q22}). Кіріс және шығыс алфавиттері бірдей: {0, 1}.

Шығыс бойынша ажыратылмас жұптар ретінде (q11; q21), (q12; q22) және (q13; q21) анықталады. Осыдан ажыратылмас кластар құрылады: {(q11; q21), (q13; q21)} және {(q12; q22)}.

Кіріс сөзі 01010101 үшін екі автомат та бірдей шығыс тізбегін береді: 01111111. Демек, M1 және M2 эквивалентті. Күйлері аз болғандықтан, M2 автоматын M1-ді «жабады» деуге болады.

Эквивалентті автомат құру: «Бес философ» есебі

Бір қайырымды меценат ашқан пансионда атақты бес философ тұрады. Олар кезекпен асханаға келіп, түстенеді. Үстелде спагетти және әр философтың сол жағында бір шанышқы бар. Спагеттиді жеу үшін екі шанышқы қажет болғандықтан, философ түстенуге отырғанда көршісінің шанышқысын (егер бос болса) алуға мәжбүр.

Талдаудағы қауіп: блоктау

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

Құрылымдық үлгі

Тапсырманы құрылымдық деңгейде бес параллель блок ретінде көрсетуге болады. Әр блокта философ пен оның сол жағындағы шанышқыны біріктіру ыңғайлы. Блоктар көршілер арасында ресурс (шанышқы) беру арқылы өзара әрекеттеседі.

«Философ–шанышқы» блогының арналары

Кіріс сигналдары (3 арна)

«Шанышқы керек» — сол жақ көршіден сұраныс.
«Шанышқылар бос» — сол жақ көрші босатты.
«Шанышқыны алуға болады» — оң жақ көрші шанышқыны сұрайды.

Шығыс сигналдары (3 арна)

«Шанышқыны алуға болады» — сол жақ көршіге рұқсат.
«Шанышқы керек» — оң жақ көршіден шанышқыны сұрау/қайтаруды талап ету.
«Шанышқылар бос» — философ тамақтанды және шанышқылар бос.

Құрылымдық деңгейдің қысқа жазылуы: (1,2,3)-ФN-(4,5,6).

Иерархия: ішкі блоктарға жіктеу

Келесі деңгейде «философ–шанышқы» блогын үш құрамдас блокқа бөлуге болады: «шанышқы», «қызметші» және «философ». Төменде «шанышқы» мен «қызметші» блоктарының арналық сипаттамалары беріледі.

«Шанышқы» блогы

Сол және оң жақтағы қызметшілерден «шанышқы керек» және «шанышқы босады» сигналдарын қабылдап, сәйкес жаққа «алуға болады» сигналын береді.

Қысқа жазылуы: B: (1,2,3,4)-B-(5,6).

«Қызметші» блогы

Екі шанышқының бос/бос еместігі туралы ақпаратты және философтың «түстенгім келеді» өтінішін қабылдайды. Шанышқыға сұраныс жібереді, босауын жариялайды және философқа түстенуге рұқсат береді.

Қысқа жазылуы: C: (1,2,3)-C-(4,5,6).

Шанышқының автоматты үлгісі

Блоктардың жұмыс алгоритмін функционалдық деңгейде сипаттау үшін ақырлы автомат үлгісі қолданылады: жеке блок үшін де, параллель жұмыс істейтін автоматтар желісі үшін де.

Автомат сипаттамасының фрагменті

Шанышқының әрекетін сипаттайтын автомат үшін келесі жазылым келтіріледі:

P: ps = {pl(x1-), pr(^x1x3-)},
pl = {ps(x2-)},
pr = {ps(x4-)}.

Мұнда автомат арналары мен құрылымдық контактылар арасындағы сәйкестік енгізіледі. Берілген мәтінде осы сәйкестіктің әрі қарайғы тізімі үзінді түрінде аяқталмай қалған.