1 – билет

1. Бинар қатынастардың негізгі түрлері. Рефлексив және транзитив тұйықтау.

a) негізгі анықтамаларын жазып беріңіз;

б) мысалдар келтіріңіз;

в) қатынасты қай кезде функция деп атаймыз, түсіндіріңіз.

2. Берілген тілді қабылдайтын Стегі бар автоматты құр: , мұндағы w сөзі a,b алфавитінен құрылған, ал- кері сөз.

3.

.

1.Бинар қатынастардың негізгі түрлері. Рефлексив және транзитив тұйықтау.

R⊆A×B кез келген жиын R⊆ (предикат) жиындарында.

Түрлері:

Екі бинарлық қатынастың композициясы

Егер жәнеекі бинарлық қатынастың композициясы деп осындай өрнекті айтамыз.

Кері қатынас

Егер R⊆A×B бинарлық қатынастың кері қатынасы деп:

айтамыз.

Толықтауы

Егер бинарлық қатынастың толықтауы деп:

айтамыз.

Транзитив тұйықтау

Рефлексив тұйықтау

R={(1,1),(1,2),(2,3),(3,1)}

{(1,1),(1,2),(2,2),(2,3),(3,1),(3,3)}

2 – билет

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

a) негізгі анықтамаларын жазып беріңіз;

б) мысалдар келтіріңіз;

в) регуляр емес тілге NFA құрастыруға бола ма? Түсіндіріп беріңіз.

2. Берілген тілді қабылдайтын Стегі бар автоматты құр:

3.

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

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

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

3 – билет

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

a) негізгі анықтамаларын жазып беріңіз;

б) мысалдар келтіріңіз;

в) детерминистік ақырлы автоматтарды қолдану мақсаты, түсіндіріңіз.

2. Берілген тілді қабылдайтын Стегі бар автоматты құр:

3.

5. Детерменистік ақырлы автоматтар, олармен қабылданатын тілдер. Конфигурация.Детерминистік автоматпен қабылданатын тіл. Ақырлы автомат (finite automaton,FA) M=(Q，Σ，δ，q0，F) Q——күйлердің бос емес ақырлы жиыны . ∀q∈Q，q-ді M-ның бір күйі деп атаймыз. (state). Σ—— алфавит (Input alphabet). Енгізілген сөздер тізбегі тек Σ дағы cимволдардан алынады. q0——q0∈Q, M-автоматының бастапқы күйі (initial state). δ——күй ауыстыру функциясы (transition function). δ：Q×Σ→Q, ∀(q，a)∈Q×Σ，үшін δ(q，a)=p арқылы ：M-автоматының q күйінде тұрып a символын оқып, күйін p-ға ауыстыруды сонымен бірге оңға қарай бір қадам жылжытуды білдіреді. F——F⊆Q, M-ның аяқтау күйлерінің жиынын білдіреді (final state). ∀q∈F, q-ді M-ның тоқтау күйі деп атаймыз немесе қабылдау күйі (accept state). Анықтама: Конфигурация немесе тез бейнелеу( instantaneous description) ақырлы автоматы (Q, Σ, ∆, I, F) деп кез-келген реттелген жұпты (q, ) айтамыз, мұндаq∈Q және ∈ .

Анықтама: Барлық конфигурацияның көбіндегі ақырлы автоматын М бинарлық қатынастыкелесідей анықтаймыз. Егер (p, x, q)∈∆ және ∈ , онда (p, x)(q, w)

δ ны толықтыру: : Q×>Q. Кез-келген q∈Q ∈ ∈ үшін (1)(q, )=q (2)(q, )= δ ((q, ), a) (q, )=(q, )= δ ((q, ), a) = δ(q, ) Кез келген q∈Q, 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|n≥1} Егер L(M1)=L(M2), онда M1мен M2 автоматтары эквивалент деп аталады. Егер q ден қа дейін w арқылы жол бар болса, онда оны төмендегідей белгілейміз (q, ) =

4 – билет

1. Жиындарға қолданылатын амалдар. Функциилар және қатынастар. Саналымды және санаусыз жиындар.

a) негізгі анықтамаларын жазып беріңіз;

б) мысалдар келтіріңіз;

в) қатынасты қай кезде эквивалентті қатынастар деп атаймыз, түсіндіріңіз.

2. Берілген тілді қабылдайтын Стегі бар автоматты құр:

3.