Ақырлы детерминистік автоматты формалды түрде сипатта.Осы автоматтың жадысы бар ма?

Осы автоматтың жадысы жок.Себебі PDA-бұл стек деп аталатын құрылғы мен стектің төбесіне оқып жазатын стектің басымен жабдықталған NFA.Яғни біздеDFA-da NFA-da мұндай қасиетке ие бола алмайды.Олар ешқашан жадыға сақтай алмайды.Ақырлы детерминистік автоматты формалды түрде сипатталуы: Формалды q орындалады.Сонда және тек сонда ғана ,егер –ге дейін w бойынша бір жол бар болса.M=<k, > -- автоматты белгіленуі; k=барлық күйлер жиыны; S k-бастапқы күй; F ішкі жиыны К-ақырлы күйлер; :kx K;

Мыс:k={ }; ={a,b}; S= ; F={ }

A b a

L={ }

19.Детерминистік емес автоматтар мен стегі бар автоматтардың арасындағы айырмашылығын сипатта. Стектің артықшылығы неде?

Жалпы M = (Q, ∑, δ , q₀, F) детерминистік емес ақырлы автоматтың (NFA) детерминистік ақырлы автоматтан айырмашылығы – мұнда күйлердің көп ретті өзгеруі мен ε-өтулерге рұқсат етілген.

Күйлердің көп ретті өзгеруі деген не? Бұл әрбір қозғалыс кезінде бірден көп күй болуы мүмкін дегенді білдіреді. Яғни, кез келген q күйі мен a кіріс символы үшін Q-дың ішкі жиыны δ(q,a) = {p₁, p₂, …, p_k} көшуі келесі q күйі a-ны оқығаннан кейін p₁, p₂, …, p_k –ның кез келгені бола алатынын білдіреді.

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

Стегі бар автомат (PDA) стек деп аталатын құрылғымен және стектің төбесіне оқып-жазатын стектің басымен жабдықталған детерминистік емес ақырлы автомат болып табылады. Стек – анықталған мөлшері жоқ, бірінші кірген соңғы шығатын, мәліметтерді сақтайтын құрылғы. Стектің басы әрқашан стектің төбесін қарастырады. Ол екі операцияны орындайды: push және pop.

Екеуінің негізгі айырмашылығы да осы: стегі бар автоматтың жадыда сақтау қабілеті бар. Яғни, PDA-да сөз алфавитке кіруі үшін қосымша тағы да стектің бос болуы шарт. Осыдан кейбір есептерді шешуде стегі бар автоматтың осы артықшылығын пайдалануға болады. Кішкене ғана мысал келтірейік:

ω сөзінде a-лар саны b-лардан 3 есе көп болсын және b-дан кейін a-лар кездеспейді. Яғни стектің артықшылығын пайдалансақ болады: сөз тілге кіруі үшін лента, стек босап, сөз ақырлы күйге жетсе болды.

Мұнда байқайтынымыз, лентада a кездескен сайын стекке A жазылады, b кездескен сайын стектен 3 A өшіріледі. Яғни, стек босауы үшін b міндетті түрде a-дан 3 есе аз болуы тиіс!

Андай жағдайда берілген сөзді детерминистік емес ақырлы автомат қабылдайды? Қандай жағдайда берілген сөзді стегі бар автомат қабылдайды?

Детерминистік емес ақырлы автомат, яғни NFA қандай жағдайда сөзді қабылдайды? Егер де сөзді қабылдайтын автоматтың, яғни DFA-ның бір есептеуі бар болса. Жалпы, детерминистік емес ақырлы автомат дегеніміз – күйлердің көп ретті өзгеруі мен ε-өтулер рұқсат етілген автомат болып табылады. Мұнда берілген есептің шартына сәйкес дұрыс бір жолы болса жеткілікті, яғни кез келген тілдің сөзін детерминистік емес ақырлы автомат арқылы бейнелеуге болады, мұндағы басты шарт – жоғарыда атап өткеніміздей, автоматтың бір есептеуі бар болып, сөз ақырлы күйге жетсе болды.

Стегі бар автомат, яғни PDA қандай жағдайда сөзді қабылдайды? Егер де сөзді қабылдайтын автоматтың бір есептеуі болып, стек босаса. Жалпы стегі бар автомат – бұл стек деп аталатын құрылғысы бар детерминистік емес ақырлы автомат болып табылады. Яғни, детерминистік емес ақырлы автомат қабылдайтын сөздердің ішінен есептің шартын қанағаттандыратын, стек пен лента босайтын кездегі сөздерді қабылдайды.