Стекті детерминистік емес автоматтар. Конфигурация. Стекті автоматпен абылданатын тіл.

Стегі бар автомат (PDA) – бл детерминистік емес аырлы автомат пен жадысы бар лента арылы рылан автоматты айтамыз.

Стекті асиеті:

1) сыйымдылыы шексіз.

2) оитын тетігі бас жаында орналасады.

3) бос стек М= (K, , Г, ,F,S,) мнда: -K — автомат кйіні аырлы жиыны; - — алфавитпен есептелінетін ммкін кіруші алфавиті,мнда жолдан тілдер формалданады; -S — жад алфавиті;

: Q × ( {e}) × ( Г {})

(q, a, u) = (P, )

NFA: (q, a) = P

(P, ) (q, a, u) – нені білдіреді?

PDA: М-автоматы q кйінде лентадан а рнек кріп жне стектен u Г символын кріп, стектен u символын шіріп, орнына символын жазады жне лентаны тетігі оа бір адама кшіп Р кйіне кшеді.

Жадайлар:

1) = , (Р, ) (q, a, u) – стектен шіру бйрыы: q а, \

2) u = , (Р, ) (q, a, u) – стекке элемент жазу : : q а, \ Р

3) u = , = , (Р, ) (q, a, ) – стекке ешнрсе істемей NFA-мен жмыс істеу: q а, \ Р

Жады стек трізді жмыс атарады,яни соы жазылан элемент маызды. Бдан, ту функциясы бейнесі болып табылады: : K× × S K × S .

Символды оиды.Онда негізгі екі амал бар:

Push:Стекке жаа символ осу.

Pop: Бас символды оу жне алып тастау

Стек символдарыны алфавиті:

Екі ерекше кй бар:бас кй s жне соы кйлер жиыны F. Е уелі,PDA бас кй s-те болады жне лента басы е сол жаында болады, лентада енгізілген сз бар біра, стек бос болады.Лента е соы яшыа келгенде, PDA тотайды. Енгізілген сз x осы PDA-мен абылданады, егерде PDA соы кйге тотаса жне стек бос болса. Баса жадайда сз абылданбайды.

PDA-ны тмендегідей сипаттауа болады: M = (Q, , , , s, F)

– ену алфавиті, -стектегі символдар алфавиті.

M- PDA арылы абылданан барлы сздерді жиыны L(M).Кейде L(M) тілі M машинасымен абылданады деп те атаймыз.

PDA шін транзиттік диаграмма осы PDA-ны сипаттайтын е тиімді рал.

M = (Q, , , , s, F) шін,транзиттік диаграмма G=(V, E )тріндегі тмендегі шартты лайы диграф:

V = Q(s =, f =, f Fшін )

E ={q p | (p,u) (q, a, v) }a.

16.Аырлы детерминистік автоматты формалды трде сипатта. Не себепті автомат аырлы деп аталады? Аырлы детерминистік автоматта жадысы бар ма?Аырлы детерминистік автомат деп(DFA)- M=<KS, F> , бестігін айтамыз. Мндаы: К – кйлер жиыны (аырлы), – алфавит, SК – бастапы кй, FК – аырлы кйлер, – кшу функциясы. функциясы К×К. Кез келген qQ, a шін (q,a)-натылы аныталан мні бар болса, онда ондай автоматты Детерминистік аырлы автомат деп атаймыз. Ереже бойынша, М автоматыны келесі кйі ту функциясында кодталан. Бдан, егер М qК кйінде болып, лентадан a символы оылса, онда автоматты тетін жалыз аныталатын кйі, ол (q,a) К. Детерминистік аырлы автомат кіріс сзіні оылан блігіне басын айтадан арта брай алмайды, сол жа блігіндегі сз саналатын басындаы машинаны ары арай функциялануына сер ете алмайды. Детерминистік автоматты конфигурациясы <KS, F> - бл К× кез-келген элемент. Аырлы автомат детерминистік деп аталады егер: 1)множество I дл 1 ана элементтен трса, 2)рбір <p, x, q> туі шін |x| = 1 тедігі орындалса. 3)кез-келген a символы жне p Q кйі шін, < p, a, q> рылымды бір q Q кйі болады. M- абылданатын тіл: x* шін, егер (q,w)F болса, онда x-ті M-абылдайды дейміз, ал (q,w) F болса, онда M-автоматы x-ті абылдамайды деп атаймыз. L(M)={x| x* рі (q,w)F } M-автоматымен абылданатын тіл: L(M1)= L(M2)={02n|n1} Егер L(M1)=L(M2), онда M1мен M2 автоматтары эквивалент деп аталады. Мысал: M=<KS, F>, К={q₀, q₁}, ={a,b}, S=q₀, F={q₀}

– функциясы келесі кестемен рнектеледі:

17)Аырлы детерминистік автомат пен детерминистік емес автоматтын арасындаы айырмашылытарын сипатта.

Аыырлы автомат (finite automaton,FA) M=(Qq0F) Q——кйлерді бос емес

аырлы жиыны . qQq-ді M-ны бір кйі деп атаймыз. (state). —— алфавит (Input alphabet).

Енгізілген сздер тізбегі тек даы cимволдардан алынады. q0——q0Q, M-автоматыны бастапы кйі (initial state).——кй ауыстыру функциясы (transition function). Q×Q, (qa)Q×шін (qa)=p арылы M-автоматыны q кйінле трып a символын оып, кйін p-а ауыстыруды сонымен бірге оа арай бір адам жылжыуды білдіреді. F——FQ, M-ны аятау кйлеріні жиынын білдіреді (final state). qF, q-ді M-ны тотау кйі деп атаймыз немесе абылдау кйі (accept state).Кез келген qQ, a шін (q,a)-наытылы анытаан мні бар болса, онда ондай автоматтыДетерминистік аырлы автомат деп атаймыз.

M- абылдайтін тіл: x*шін,егер (q,w)F болса, онда x-ті M-абылдайды дейміз, ал (q,w) F болса, онда M-автоматы x-ті абылдамайды деп атаймыз. L(M)={x| x*рі (q,w)F }

M-автоматымен абылданатын тіл. -L(M1)= L(M2)={02n|n1} Егер L(M1)=L(M2), онда M1мен M2 автоматтары эквивалент деп аталады.

Аырлы детерминистік емес автомат бл- дегеніміз аырлы кйдін жиыны. алфавит бастапы кй

аырлы кйдін жиыны кшу атынасы,ішкіжиыны

Орналасан a жне жетекші М кй диаграммасында. Егер М кйінде орналасса, онда а келесі оылатын символ болып табылады, сонымен М ары арай кйлеріне тріне немесе : егер оытын болса онда символ оылмайды.

Формалды трде есептелінетін аырлы детерминистік емес автомат, детерминистік автоматка те сас.

Детерминистік емес аырлы автоматтардан бірнеше кй шыаруа болады.