Аырлы детерминистік автоматты формалды трде сипатта.Осы автоматты жадысы бар ма?
Осы автоматты жадысы жок.Себебі 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, , , q0, F) детерминистік емес аырлы автоматты (NFA) детерминистік аырлы автоматтан айырмашылыы – мнда кйлерді кп ретті згеруі мен -тулерге рсат етілген.
Кйлерді кп ретті згеруі деген не? Бл рбір озалыс кезінде бірден кп кй болуы ммкін дегенді білдіреді. Яни, кез келген q кйі мен a кіріс символы шін Q-ды ішкі жиыны (q,a) = {p1, p2, …, pk} кшуі келесі q кйі a-ны оыаннан кейін p1, p2, …, pk –ны кез келгені бола алатынын білдіреді.
NFA-да кйлерді кп ретті згеруімен атар -тулер де олданылады. -ту кезінде магниттік головка ештее істемейді, жне кй згеруі ммкін. Басаша айтанда, ешандай символды оымай-а бір кйден екіншіге туге болады.
Стегі бар автомат (PDA) стек деп аталатын рылымен жне стекті тбесіне оып-жазатын стекті басымен жабдыталан детерминистік емес аырлы автомат болып табылады. Стек – аныталан млшері жо, бірінші кірген соы шыатын, мліметтерді сатайтын рылы. Стекті басы рашан стекті тбесін арастырады. Ол екі операцияны орындайды: push жне pop.
Екеуіні негізгі айырмашылыы да осы: стегі бар автоматты жадыда сатау абілеті бар. Яни, PDA-да сз алфавитке кіруі шін осымша таы да стекті бос болуы шарт. Осыдан кейбір есептерді шешуде стегі бар автоматты осы артышылыын пайдалануа болады. Кішкене ана мысал келтірейік:
сзінде a-лар саны b-лардан 3 есе кп болсын жне b-дан кейін a-лар кездеспейді. Яни стекті артышылыын пайдаланса болады: сз тілге кіруі шін лента, стек босап, сз аырлы кйге жетсе болды.
Мнда байайтынымыз, лентада a кездескен сайын стекке A жазылады, b кездескен сайын стектен 3 A шіріледі. Яни, стек босауы шін b міндетті трде a-дан 3 есе аз болуы тиіс!
Андай жадайда берілген сзді детерминистік емес аырлы автомат абылдайды? андай жадайда берілген сзді стегі бар автомат абылдайды?
Детерминистік емес аырлы автомат, яни NFA андай жадайда сзді абылдайды? Егер де сзді абылдайтын автоматты, яни DFA-ны бір есептеуі бар болса. Жалпы, детерминистік емес аырлы автомат дегеніміз – кйлерді кп ретті згеруі мен -тулер рсат етілген автомат болып табылады. Мнда берілген есепті шартына сйкес дрыс бір жолы болса жеткілікті, яни кез келген тілді сзін детерминистік емес аырлы автомат арылы бейнелеуге болады, мндаы басты шарт – жоарыда атап ткеніміздей, автоматты бір есептеуі бар болып, сз аырлы кйге жетсе болды.
Стегі бар автомат, яни PDA андай жадайда сзді абылдайды? Егер де сзді абылдайтын автоматты бір есептеуі болып, стек босаса. Жалпы стегі бар автомат – бл стек деп аталатын рылысы бар детерминистік емес аырлы автомат болып табылады. Яни, детерминистік емес аырлы автомат абылдайтын сздерді ішінен есепті шартын анааттандыратын, стек пен лента босайтын кездегі сздерді абылдайды.