25 Билет емес бул 12 билеттин 3 есеби
13 – билет
1. Берілген регуляр тілдің оны қабылдайтын автоматты құру алгоритмі.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) өмірде детерминистік автоматтардың мысалдарын келтіріңіз, мағынасын түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
3.
Берілген регуляр тілдің оны қабылдайтын автоматты құру алгоритмі
14 – билет
1. Стегі бар детерминистік емес автоматтар. Конфигурация. Стекті автоматпен қабылданатын тіл.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) регуляр тілдерге стегі бар автоматты құрастыруға болады түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
, мұндағы w сөзі a,b алфавитінен құрылған,
ал
- кері сөз.
3.
Стекті детерминистік емес автоматтар. Конфигурация. Стекті автоматпен қабылданатын тіл.
Стегі бар автомат (PDA) – бұл детерминистік емес ақырлы автомат пен жадысы бар лента арқылы құрылған автоматты айтамыз.
Стектің қасиеті:
сыйымдылығы шексіз.
оқитын тетігі бас жағында орналасады.
бос стек λ М= (K, Ʃ, Г, δ,F,S,) мұнда: -K — автомат күйінің ақырлы жиыны; -Σ — алфавитпен есептелінетін мүмкін кіруші алфавиті,мұнда жолдан тілдер формалданады; -S — жад алфавиті;
δ: Q × (Ʃ
δ(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.
15 – билет
1. Ақырлы детерминистік автоматты формалды түрде сиппата. Не себепті автомат ақырлы деп аталады?
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) Ақырлы детерминистік автоматта жадысы бар ма? Түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
,
мұндағы w сөзі a,b алфавитінен құрылған,
ал
- кері сөз.
3.
Ақырлы детерминистік автоматты формалды түрде сипатта.Осы автоматтың жадысы бар ма?
Осы
автоматтың жадысы жок.Себебі 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={
}
16 – билет
1. Майхилл-Нероуд теоремасының салдары. (регуляр емес тілдер мен эквивалент кластар арасындағы байланысы туралы)
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в)
Index(
)
өрнегінің мәні тілдердің регуляр және
регуляр еместігіе байланысты қалай
өзгереді, түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
3.
Майхилл-Нероуд теоремасының салдары(регуляр емес тілдер туралы)
L
тілі регуляр болады сонда және тек сонда
ғана егер
тілі бойынша анықталған эквивалент
класстар саны ақырлы болса.Дәлелдеу:
Егер L тілі регуляр болса, онда L
кейбір ақырлы автоматтар үшін және
-де
эквиваленттік класстардан аз емес күй
сақтайды. Демек в
эквивалентті класстардың ақырлы саны.
Бұл салдар арқылы тілдің регуляр емес
екендігін де дәлелдеуге болады. Мысалы:
L={
}
Ешқандай
екі сөз
i
бола тұры
қатысты эквивалентті емес, себебі
кейін жазылса да L тілінің сөзін береді,
бірақ
L тіліне жатпайтын сөзді береді. Осыдан
шексіз көп эквивалентті классқа ие.
Осының салдарынан L тілі регуляр емес
болып шығады.
17 – билет
1. Ақырлы детерминистік автоматты формалды түрде сипатта.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) осы автоматтың жадысы (сақтау қабілеті) бар ма? Түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
, мұндағы w сөзі a,b алфавитінен құрылған,
ал
- кері сөз.
3.
Ақырлы детерминистік автоматты формалды түрде сипатта.Осы автоматтың жадысы бар ма?
Осы
автоматтың жадысы жок.Себебі 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={
}
18 – билет
1. Детерминистік емес автоматтар мен стегі бар автоматтардың арасындағы айырмашылығын сипатта.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) стектің артықшылығы неде? Түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
abwcwRa, мұндағы
w сөзі
a,b алфавитінен
құрылған,
ал
-кері
сөз.
3.
Детерминистік емес автоматтар мен стегі бар автоматтардың арасындағы айырмашылығын сипатта. Стектің артықшылығы неде?
Жалпы 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 есе аз болуы тиіс!
19 – билет
1. Ақырлы детерминистік автомат пен детерминистік емес автоматтын арасындағы айырмашылыктарын сипатта.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) берілген регуляр тілге эквивалент болатын DFA және NFA автоматтарын құруға болама, түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
,мұндағы
w сөзі
a,b алфавитінен
құрылған,
ал
-кері
сөз.
3.
Ақырлы детерминистік автомат пен детерминистік емес автоматтын арасындағы айырмашылықтарын сипатта.
Аықырлы автомат (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).Кез келген 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 автоматтары эквивалент деп аталады.
Ақырлы
детерминистік емес автомат бұл-
дегеніміз
ақырлы күйдін жиыны.
алфавит
бастапқы күй
ақырлы
күйдін жиыны
көшу қатынасы,ішкіжиыны
Орналасқан
a және жетекші
М күй диаграммасында. Егер М
күйінде орналасса, онда а келесі оқылатын
символ болып табылады, сонымен М ары
қарай
күйлеріне түріне немесе
: егер
оқытын болса онда символ оқылмайды.
Формалды түрде есептелінетін ақырлы детерминистік емес автомат, детерминистік автоматка өте ұқсас.
Детерминистік емес ақырлы автоматтардан бірнеше күй шығаруға болады.
20 – билет
1. Жиындарға қолданылатын амалдар. Функциилар және қатынастар. Саналымды және санаусыз жиындар.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) қатынасты қай кезде эквивалентті қатынастар деп атаймыз, түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
3.
Жиындарға қолданылатын амалдар. Функциялар және қатынастар
Саналымды және санаусыз жиындар.
Жиын
ретiнде оның қандай да бiр белгiлерiн
ескеріп, әртүрлi объектiлердiң алдын -
ала берiлген ерекшелiктерi бойынша
топтастырылуын айтамыз Жиындарды үлкен
латын әрiптерi арқылы белгiлеймiз: A,
B, X, P, T және
т.б. Жиынды құрайтын нысандар осы жиынның
элементтерi
деп
аталады. Жиын элементтерi кiшi латын
әрiптерiмен белгiленедi: a,
b, c, x, u, v және
т. б. Қажет болған жағдайда, тӛменгi
немесе жоғарғы индекстер еркiн қолданылады.
Жиындарды олардың элементтерiнiң тiзiмiн
немесе олардың элементерiне ортақ
қасиеттердi кӛрсету
жолымен беруге болады Ақырсыз жиындар
негізінен екінші тәртiппен анықталады.
Бiздiң келешек баяндауларымыз үшiн
тӛмендегi
сандық жиындар кеңiнен қолданылады.
натурал сандар жиыны, бүтiн сандар жиыны
рационал сандар жиыны,R
нақты
сандар жиыны. Бұл жиын рационал және
иррационал сандардың бірігуінен тұрады.
Жиындар арасындағы байланыстар –
жиындарға қолданылатын тӛмендегi
амалдарды анықтайды.
Егер А жиынының барлық элементтерi B жиынына тиiстi болса, онда А жиынын
B жиынының iшкi жиыны деп атаймыз. Ал B жиыны А жиынын қамтушы жиын
деп аталады.Ешбiр элементi болмайтын жиынды бос жиын деп атаймыз. – бос жиын
белгiсi. Анықтауымыз бойынша бос жиын кез келген жиынның ішкі жиыны болады.
Кез келген A,B,C жиындары үшін：⑴ A=B ⇔ A⊆B және B⊆A. ⑵ егер A⊆B ,онда |A|≤|B|. егер A⊂B,онда |A|≤|B| ⑶ Егер A ақырлы жиын болса әрі A⊂B онда |B|>|A|⑸ Егер A⊆B , онда∀x∈A үшін x∈B. ⑹ ЕгерA⊂B, онда ∀x∈A үшін x∈B және ∃x∈B бірақ x∉A. ⑺ Егер A⊆B және B⊆C онда A⊆C. ⑻ Егер A⊂B және B⊂C сонымен бірге не A⊆Bәрі B⊂C не A⊂Bәрі B⊆C бірі орындалса онда A⊂C. ⑼ егер A=B болса, онда |A|=|B|.
Егер Т⊆W және табылады x∈W болса, бірақ х∉Т орындалса, T жиынын W жиынының меншiктi iшкi жиыны деп атаймыз.
1. А және В жиындарына ортақ элементтерден ғана тұратын жиынды А және В жиындарының қиылысуы деп атап, ол жиынды А∩В арқылы белгiлеймiз. Егер А∩В = ᴓболса, онда А және В жиындарын қиылыспайтын жиындар деп атаймыз. ⑴ A∩B= B∩A.⑵ (A∩B)∩C=A∩(B∩C). ⑶ A∩A=A ⑷ A∩B=A ⇔ A⊇B. ⑸ Φ∩A=Φ. ⑹ |A∩B|≤min{|A|，|B|}. ⑺ A∩(B∪C)=(A∩B)∪(A∩C). ⑻ A∪(B∩C)=(A∪B)∩(A∪C). ⑼ A∩(A∪B)=A.
⑽ A∪(A∩B)=A.
2. А және В жиындарының ең болмағанда бiреуiне тиiстi элементтерден тұратын
жиынды – А және В жиындарының бiрiгуi деп атаймыз. Оны АỤВ таңбасы арқылы белгiлеймiз.
A1∪A2∪…∪An={a|∃i1≤i≤n,a∈Ai}
3. А жиынына тиiстi, ал В жиынына тиiстi емес элементтерден тұратын жиын А
жиыны мен В жиынының айырмасы (А минус В) деп аталып, А\В арқылы
белгiленедi. ⑴ A-A=Φ
⑵ A-Φ=A ⑶ A-B ≠ B-A ⑷ A-B=A iff A∩B=Φ\
⑸ A∩(B-C)=(A∩B)-(A∩C) ⑹ |A-B|≤|A|
4.
Симметриялық
айырма
(symmetric difference):A
∪(B\A)
Ал
А
жиынына
тиiстi емес және А
жиынын
қамтушы қандай да бiр жиынның элементтерiнен
тұратын жиынды А
жиынының
аталған қамтушы жиындағы толықтаушы
жиыны деп
атаймыз. Белгiлеуi:
Бұл
суреттегi боялған бӛлiк,
А
жиынының
толықтаушы жиыны – A жиынын бiлдiредi.
- конволюция заңы.
Элементтерiнiң саны белгiлi бiр натурал санға тең болатын жиынды ақырлы
жиын деп атаймыз. Ақырлы жиынның элементтер санын оның қуаты деп атайды.
Сонымен бірге, ақырлы жиын деп, ӛзiнiң кез келген меншiктi iшкi жиынымен ӛзара әрмәндi сәйкестiкте болмайтын жиынды айтуға болатыны төменде кӛрсетіледі. Ал мұндай сәйкестiктер табылатын жиынды ақырсыз жиын деймiз.
Анықтама.
Бос
емес А1, А2 ,...,Аn
жиындары
берiлсiн. Онда реттелген элементтер
жиыны
жиыны А1, А2 ,...,Аn жиындарының декарттық көбейтiндiсi деп аталады.
Олардың элементтерiн n-дiктер деп атаймыз.
Анықтама. Бос емес А жиыны берiлсiн. Мұндеғы n – оң бүтiн сан, онда n
жиынының кез келген iшкi жиынын А жиынында анықталған n-орынды қатынас
деп атаймыз.1-орынды қатынастар унарлық, 2-орынды қатынастар бинарлық, 3-орынды
қатынастар тернарлық қатынастар деп аталады
1. Егер кез келген x€ A элементi үшiн (x,x) €R болса, онда R қатынасы рефлексивтi қатынас деп аталады.
2. Егер кез келген x,y €A элементтерi үшiн (x, y)€ R (y, x) €R шарты орындалса, онда R қатынасы симметриялы деп аталады.
3. Егер кез келген x, y, z€ A элементтерi үшiн (x, y) €R және (y, z) €R => (x, z) €R шарты орындалса, онда R қатынасы транзитивтi деп аталады.
4. Кез келген x€A үшiн (x, x)тиісті емесR болса, онда R қатынасы иррефлексивтi деп
аталады.
5. Кез келген x,y €A үшiн (x, y)€R және (y, x) €R болғандығынан x = y теңдiгi
орындалса, онда R қатынасы антисимметриялы деп аталады.
A жиынында анықталған рефлексивтi, симметриялы және
транзитивтi
қатынас эквиваленттiлiк
қатынас деп
аталады.
Функциялар Егер төмендегі шарттар
орындалса, онда f
қатынасынфункция
деп
атайды
dom f=A
Im f ⊆B
(x,
)
Dom f - функцияның анықталу аймағы, ал Im f - функцияның мәндер аймағы. Сонымен, функция бинарлық қатынас болады.
f:A
B
функциясын
инъекция
деп
атайды,
егер
кез
келген
үшін
x1!=x2 теңсіздігінен
f(x1)!= f(x2) теңсіздігі
шықса.
f:A
B
функциясын сюръекция деп атайды, егер Im f=B теңдігі орындалса.
Егер
f:A
B
функциясы инъекция және сюръекция болса, онда оны биекция деп атайды.
f:R
R,
инъекция
да, сюръекция да емес
f:R
сюръекция, бірақ инъекция емес
f:Z
инъекция, бірақ сюръекция емес
f:R
,биекция.
21 – билет
1. Детерминистік емес автоматтар мен детерминистік автоматтардың эквиваленттілігі.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) детерминистік ақырлы автоматтарды қолдану мағынасын түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
,
мұндағы w сөзі a,b алфавитінен құрылған,
ал
- кері сөз.
3.
Детерминистік емес автоматтар мен детерминистік автоматтардың
эквиваленттілігі.
L(
)=L(
)
NFA=DFA?
{NFA
қабылдайтын
тіл}
= {DFA қабылдайтын
тіл}
Дәлелдейміз:
NFA және
DFA да
бірдей
есептеу
күші
бар
1 КАДАМ:
{NFA
қабылдайтын
тіл}
{DFAқабылдайтын
тіл}
Дәлел: әрбір DFA-NFA болады , DFA қабылдайтын тілді NFA қабылдайды.
2 ҚАДАМ: {NFA қабылдайтын тіл} ⊆ {DFA қабылдайтын тіл}
Дәлел: кез келген NFA-ны сәйкес пара-пар DFA-ға аударуға болады. NFA қабылдаған тілді DFA қабылдайды.
NFA-дан DFA-ға
22 – билет
1. Детерминистік ақырлы автоматтар, олармен қабылданатын тілдер. Конфигурация. Детерминистік автоматпен қабылданатын тіл.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) детерминистік ақырлы автоматтарды қолдану мақсаты, түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
3.
Детерменистік
ақырлы автоматтар, олармен қабылданатын
тілдер. Конфигурация.Детерминистік
автоматпен қабылданатын тіл.
Ақырлы
автомат (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,
) =
23 – билет
1. Регуляр өрнектер мен регуляр тілдер.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) регуляр тілдердің қолдану мағынасын түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
3.
Регуляр өрнектер мен регуляр тілдер.
Σ
-алфабиті бойынша регуляр өрнек келесідей
рекурсивті жолмен анықталады: 0-регуляр
өрнек болып табылады; 1- регуляр өрнек
болып табылады; егер
болса, онда
-регуляр
өрнек болады; егер
регуляр өрнек болса, онда (
), (
) және
өрнектері де регуляр өрнектер болады.
Жақшаларды
азайту мақсатында,
операциясының приоритеті көбейту
операциясынан жоғары, ал көбейту
амалының приоритеті қосу операциясына
қарағанда жоғары деп аламыз. Көбінесе
-тің орнына
деп жазады.
Мысалы:
.Онда
–регуляр
өрнек болады.
Әрбір
е регуляр
өрнегі
алфабиті
бойынша қандай да бір тіл құрады, ол
келесідей рекурсивті жболмен анықталады:
L(a)⇔{a}, егер
болса,L(0)⇔ø,
L(1)⇔{e},
L(e*f)⇔
,
АН: L-регуляр тіл деп аталады, егер ол қандай да бір регуляр өрнекпен анықталса.
Ан: е-регуляр өрнек болсын. Онда
1)
2)
3) e+0=e 4)
5)
6)
8)
9)
10)
11)
Лемма:
Кез-келген
регуляр
өрнектері үшін келесі тепе-теңдіктер
орындалады:
1)
2)
3)
4)
Лемма:
Кез-келген
L
тілі
регулярлы
тіл
деп аталады, егерде М автоматы табылып:
орындалса.
Ақырлы автоматпен қабылданатынбарлық
тіл регулярлы.
24 – билет
1. Ақырлы детерминистік автомат пен детерминистік емес автоматтын арасындағы айырмашылыктарын сипатта.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) берілген регуляр тілге эквивалент болатын DFA және NFA автоматтарын құруға болама, түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
,мұндағы
w сөзі
a,b алфавитінен
құрылған,
ал
-кері
сөз.
3.
Ақырлы детерминистік автомат пен детерминистік емес автоматтын арасындағы айырмашылықтарын сипатта.
Аықырлы автомат (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).Кез келген 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 автоматтары эквивалент деп аталады.
Ақырлы
детерминистік емес автомат бұл-
дегеніміз
ақырлы күйдін жиыны.
алфавит
бастапқы күй
ақырлы
күйдін жиыны
көшу қатынасы,ішкіжиыны
Орналасқан
a және жетекші
М күй диаграммасында. Егер М
күйінде орналасса, онда а келесі оқылатын
символ болып табылады, сонымен М ары
қарай
күйлеріне түріне немесе
: егер
оқытын болса онда символ оқылмайды.
Формалды түрде есептелінетін ақырлы детерминистік емес автомат, детерминистік автоматка өте ұқсас.
Детерминистік емес ақырлы автоматтардан бірнеше күй шығаруға болады.
25 – билет
1. Детерминистік автоматпен қабылданатын тілдің регуляр өрнегін табу алгоритмі.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) тілдің регуляр өрнегін қолдану мағынасын түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
,мұндағы
w сөзі
a,b алфавитінен
құрылған,
ал
-кері
сөз.
3.
Детерминистік автоматпен қабылданатын тілдің регуляр өрнегін табу алгоритмі.
L={
}
L={a,ab,ba,aaa,abb,bab,bba,aaab,aaba,abaa,baaa,abbb,babb,bbab,bbba,..}
DFA
k={
}
s=
F={
}
b
b a 
b
a 
a
|
|
|
|
|
|
a |
|
|
|
|
b |
|
|
|
L=
регуляр
өрнек.
26 – билет
1. Берілген регуляр тілдің оны қабылдайтын автоматты құру алгоритмі.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) өмірде детерминистік автоматтардың мысалдарын келтіріңіз, мағынасын түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
,мұндағы
w сөзі
a,b алфавитінен
құрылған,
ал
-кері
сөз.
3.
Берілген регуляр тілдің оны қабылдайтын автоматты құру алгоритмі
27 – билет
1. Регуляр тілдердің тұйықтық қасиеттері. Ақырлы автоматтардың тура көбейтіндісі.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) тілдің регуляр өрнегін құрастыруға қолданылатын амалдар туралы түсіндіріп беріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
3.
Регуляр тілдердің тұйықтау қасиеттері. Ақырлы автоматтың тұйықтық қасиеттері.
Регуляр тілдердің тұйықтық қасиеттері мына идеяны іске асырады: егер бір немесе біренеше тілдер регуляр болса, онда ол тілдермен байланысқан тілдер де регуляр болады.
Регуляр тілдердің тұйықтық қасиеттері келесі операциларда сәйкесінше орындалады:
Бірігу, қиылысу, толықтау,итерация, конкатенация, гомоморфизм, кері гомоморфизм.
Алдымен бульдік операцияларында: бірігу, қиылысу, толықтау кезіндегі тұйықталу қасиетін қарастырайық. 1) Егер L,M тілдері ∑ алфавитіне тиісті болса , онда LUM тілінде L,M тілдерінің кем дегенде біреуінде бар барлық тізбектер (цепочка) бар; 2) Егер L,M тілдері ∑ алфавитіне тиісті болса, L∩M тілінде Lжәне M тілдерінің барлық тізбектері (цепочка) бар; 3) Егер қандай да бір L тілі ∑ алфавитіне тиісті болса, онда ¯L тілі, L-дің толықтауы – L тіліне жатпайтын ∑* алфавитінің тізбектерінің жиыны.
ТЕОРЕМА. Егер L,M тілдері ∑ алфавитіне тиісті болса және регуляр тіл болса, онда LUM тілі де регуляр тіл. ДӘЛЕЛДЕУІ. L,M тілдері регуляр тіл болғандықтан, оларға кейбір регуляр сөйлемдер сай келеді, L=L(R) M=L(S) болсын, онда регуляр сөйлемдер үшін операцияның анықтамасы бойынша LUM=L(R+S) # Бұл теореманың дәлелдеу идеясы конкатенация мен итерацияға да сай келеді: 1)(конкатенация) Егер L,M тілдері ∑ алфавитіне тиісті болса және регуляр тіл болса, онда LM тілі де регуляр тіл.
2)(итерация) Егер L ∑ алфавитіне тиісті болса және регуляр тіл болса, онда L* тілі де регуляр тіл.
ТЕОРЕМА.
Егер
L тілі ∑ алфавитіне тиісті болса және
регуляр тіл болса, онда ¯L
*
болғандықтан L регуляр тіл.
ДӘЛЕЛДЕУІ.
Қандай да бір L=L(A) болысн . A = DFA (Q, Σ, δ,
q0, F). Онда L = L(B), Мұндағы B- DFA болысн (Q, Σ,
δ, q0, Q – F), яғни Ажәне В бірдей автоматтар
тек А-дағы күйлер В-да орындалмайды,
және сәйкесінше В-дағы күйлер А-да
орындалмайды. Онда w L(B)-да жатса, сонда
және сонда ғана δ (q0, w)
Q
– F- те жатады , яғни w L(A)-ға жатпайды.
Мұндағы δ (q0, w) – қандай да бір күй. Аөда
барлық жолдар анықталған, егер қандай
да бір жолдар анықталмаған болса (жоқ
болса) онда L(A)-да L(B)-да жоқ болар еді,
бірақ қуанышқа орай DFA-да әрбір күйде
алфавитінің
әрбір күйіне жол бар болғандықтан, әрбір
тізбек (цепочка) F немесе Q-F күйіне
апарады. #
ТЕОРЕМА
.
Егер L,M тілдері ∑ алфавитіне тиісті
болса және регуляр тіл болса, онда L
M
тілі де регуляр тіл. L және M — автомат
тілдері AL
= (QL,
Σ, δL,
qL,
FL)
және AM
=(QM,
Σ, δM,
qM,
FM)
автомат алфавиттері бірдей болып
саналады, яғни егер L және M. Оңай болу
үшін AL
= (QL,
Σ, δL,
qL,
FL)
және AM
= (QM,
Σ, δM,
qM,
FM)
DFA болсын. L,M үшін AL
және AM
бір уақытта автомат күйлерін моделідейтін
А автоматын құрастырайық. А қос куй
болсын, біріншісі AL
куйі
ал екіншісі AM
куйі болсын. А автоматының өту жолдарын
құру үшін, А (p, q) куйінде тұр деп ұйғарайық.
Мұндағы р-автомат куйі, ал q- AM
куйі. AL
Автоматы қандай әрекет орындайтынын білеміз, кірісінде а символын алады. Ол s куйіне өтсін, ал - AM а кіріс символы арқылы t куйіне өтеді. Онда А автоматының куйі (s, t) болады, сөйтіп А автоматы AL және AM автоматтарының жұмысын моделдейді. A былай анықталады A = (QL × QM, Σ, δ, (qL, qM), (FL × FM),где δ((p, q), a) = (δL(p, a), δM(q, a)).#
ТЕОРЕМА
.
Егер L,M тілдері ∑ алфавитіне тиісті
болса және регуляр тіл болса, онда L
M
тілі де регуляр тіл.L – M = L
M.
Теорема бойынша М және L
M
регуляр тілдер => L – M тілдері де
регуляр#
28 – билет
1. Тіл ұғымы, тілдерге қолданылатын амалдар.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) тілдерге қолданылатын қандай амалдарды жиындар теориясында қолдағанжоқпыз, түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
3.
Тіл ұғымы, тілдерге қолданылатын автоматтар.
Алфавит
дегеніміз бос емес ақырлы жиын, оны
арқылы белгілейміз. Оның элементтерін
символ (symbol) деп атаймыз.
алфавитіндегі сөз (string) дегеніміз осы
алфавиттегіэлементтердің ақырлы
тізбегі. Мысалы:
={a,b,c} алфавит, ал abbba, aa,bbaa- алфавиттегі
сөздер.Анықтама:
Ешқандай
сөзден тұрмайтын сөзді бос сөз деп
атаймыз да оны ℮ арқылы белгілейміз.
алфавитіндегі барлық сөздердің жиынын
арқылы таңбалаймыз.Анықтама:
ύ
сөзі
сөзінің
ішкі сөзі
деп
аталады, егерде ω
ύy
теңдігі орындалатындай x,y сөздері
табылатын болса, x,y екуі де бос сөз болуы
мүмкін. Сондықтан әрбір сөз өзінің ішкі
сөзі болады.
Subw(L)-арқылы
сәйкес L тілінің барлық сөздерінің ішкі
сөздерінен құрылған жиынды белгілейміз.
Анықтама:
Егер L
Σ*
болатын болса, онда L-ді Σ
алфавитіндегі
тіл деп
атайды. Әрбір тілді жиын ретінде
қарастыруға болады, сондықтанда жиындарға
қолданылатын барлық амалдарды осы
тілдерге де қолдануға болады. L
Σ*
болсын, онда Σ*-
L осы тілдің алфавитіне байланысты
толықтауышы деп аталады. Анықтама:
Егер
x,y сөздері Σ*
алфавитінің сөздері болатын болса,
онда xy(x сөзінің соңына y сөзінің басы
тіркеп жазылады) оcы екі сөздің
конкатенациясы
деп аталады6 кейде оны x*y деп белгілейді.
Конкатенация амалы ассосативті, яғни
(xy)z=x(yz).Мысалы: Σ*={a,b}
алфавитінде x=aabb, y=abab сөздерінің
конкатенациясы xy=aabbabab болады. Анықтама:
L1,
L2
Σ*
болсын, онда L1*L2={xy, x
}
L1*L2 тілі L1 мен L2 тілдерінің конкатенацияланған
тілі деп атады. Мысалы: L1={a,abb},
L2={bbc,c}болса, онда L1*L2={ac,abbc,abbbbc}
Анықтама:
L
Σ*
болсын, онда
Анықтама:
сөзінің
кері сөзі деп
сөзіне
кіретін символдарды кері ретпен алғандағы
сөзді айтамыз. Оны
арқылы таңбалаймыз. Мысалы:
=abcdac
болса
.Клини
жұлдызшасы L*= L0∪L∪L2∪L3∪L4∪…
29 – билет
1. Кез келген ақырлы автомат үшін оған пара-пар, күйлер саны минимал болатын детерминистік автоматты құру тәсілі.
a) негізгі анықтамаларын жазып беріңіз;
б) минималдау туралы теореманы дәлелдеңіз;
в) мысалдар келтіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
, ,
мұндағы w сөзі a,b алфавитінен құрылған,
ал
- кері сөз.
3.
Кез келген ақырлы автомат үшін оған пара-пар, күйлер саны минимал болатын детерменистік автоматты құру тәсілі.
Бізде берілген тіл NFА автоматы арқылы сипатталған болса, онда DFA-ға көшу алгоритмі арқылы тілдің DFA автоматын салып аламыз. Осы DFA автоматында бастапқы күйден бара алмайтын барлық күйлер мен жолдарын алып тастаймыз.
МЫСАЛЫ:
тілінің DFA автоматы берілген болсын
Бастапқы DFA автоматы Артық күйлері алынып тасталған DFA автоматы
Бастапқы
күйден жете алмайтын күйлерді алып
тастағанның өзінде автомат
минимизацияланбаған болуы мүмкін.
Мысалда
және
күйлері эквивалентті күйлер болады,
сондықтан оларды бір күйге біріктіруге
болады.
АН:
-тіл,
болсын.
тілі бойынша эквивалентті
болады, егер барлық
үшін келесі тұжырым дұрыс:
болады, сонда және тек сонда ғана, егер
дұрыс.
-
эквиваленттілікті білдіреді.
дегеніміз x және y екі сөзі де L-ге тиісті
немесе тиісті емес болады.
АН:
M=⟨K,
,
⟩-
детерменистік
ақырлы автомат болсын.
сөздері
осы М автоматы бойынша эквивалентті(x
)
деп аталады, егер осы екі сөз де М
автоматында s
күйден
бірдей ақырлы немесе ақырлы емес күйге
көшсе. Формалды түрде:
Біз M автоматына сәйкес q күйінің
эквиваленттілік класын
арқылы белгілейміз.
Th:
Кез келген детерменистік ақырлы автомат
үшін M=⟨K,
,
⟩-
және кез келген
үшін, егер бұл сөздер Ь автоматы бойынша
эквивалентті болса (x
,
онда бұл сөздер берілген тіл бойынша
эквивалентті болады(x
.
Егер
х-сөз, ал L-тілі автомат бойынша анықталған
болса, онда [x] арқылы х сөзі жататын L
–тілінің эквиваленттілік кластарын
белгілейміз. Мысалдағы
тіліне қатысты
-төрт
эквиваленттілік кластарға бөлінеді:
1)[e]=L
2) [a]=La
3) [b]=Lb
4)
[aa]=L(aa
bb)
М автоматы бойынша эквиваленттілік кластары:
1)
2)
3)
4)
5)
6)
кластары
[e]
класына кіреді. Бұдан барлық эквивалентті
кластар саны төртеу болды. Яғни, соңғы
құратын автоматымыз төрт күйден
тұрады(кұйлер саны эквивалентті кластар
санына тең болады).
Минимизацияланған DFA автоматы
30 – билет
1. Автоматтардың "үрлеу" туралы теоремасы.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) эквивалент класстар ұғымы қолданып тілдің регуляр емес екенін калай көрсетуге болатынын түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
,
мұндағыw
сөзі a,b
алфавитінен құрылған, ал
- кері сөз.
3.
Автоматтардың pumping туралы теоремасы.
Тілдің
регулярлы болуы оның қандай да бір
ақырлы детерменистік автомат
қабылданылуымен пара пар. Мұнда М-нің
күйлерінің саны ақырлы. Мысалға n дана.
Рumping
туралы теоремасы. L-регулярлы
жиын болсын, онда
саны бар болып, егер
-кез келген сөз үшін
,
оны
түрінде жазуға болады. мұндағы
әрі кез келген
үшін
.
Рumping туралы теоремадан: егер бір регулярлы жиында жеткілікті ұзындықта
сөзі
бар болса, онда осы жиын
сөзін де қамтитын шексіз жиын дегенді
түсінуге болады.
Рumping туралы теорема қолданылуы. Ойын ретінде қарастырсақ: сіз ж/е тағы бір адам бар, негізгі мақсат сіздің оны жеңуіңіз.
Сіз регулярлы емес деп ойлаған бір L тілін таңдап алыңыз.
Қарсы жақ n санын таңдап алу керек, яғни Рumping туралы теоремадағы тұрақты сан n. Енді кез келген таңдап алынған n санына дайын болу керек, бірақ бір жақсы жері қарсы жағың бір рет n санын таңдап алғаннан кейін ол оны өзгерте алмайды. Дегенмен қарсы жақты өте осал деп санамау керек.
Енді сіз осы L тіліне тиісті бір сөздер тізбегі
-ны
алыңыз. Сіздің таңдап алған
қарсы жағың таңдап алған n санымен іштей
байланыста.Қарсы жағың Сіз берген
сөзін
=xyz
түрінде жіктеп жазылуы керек, яғни
x,y,z-ішкі сөзін белгілеу керек. Әрі олар
шартын қанағаттандыруы шарт.Сіз енді Рumping туралы теореманың тұжырымына қайшы қорытындыға келтіруіңіз керек, ол үшін кез келген анықталған x,y,z ішкі сөздер үшін қандай да бір
бар болып
шартын қанағаттандыратын t санын табу
керек.
31 – билет
1. Майхилл-Нероуд теоремасы. (Pumping lemma)
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) берілген тілге эквивалент кластардың құрастыру жолдары, түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
3.
Майхилл-Нероуд теоремасы.
Майхилла-Нероудтың теоремасының формалды тiлдерiнiң теорияларында қажеттi және тiлдiң жүйелiлiгiнiң жеткiлiктi шарттарын анықтайды. Сонымен бiрге осы теорема осы тiлді жүйелi дәлелдеуге мүмкiндiк бередi.
Теорема
(Майхилл-Нероуд):
егер
- регуляр тіл болса, онда DFA- L тілін
анықтайтын автомат табылып, автоматтың
күйлер саны L тілі бойынша эквивалент
кластар санына тең.
V алфавитінде L тілі берілсін, ≡L қатынасы алфавиттегі бүкіл сөздер жиынына берілген.
X ≡L y болады сонда ж/е тек сонда ғана,егер барлық берілген алфавитке тиісті z үшін, xz ж/е yz сөздері L тілдеріне тиісті немесе бір уақытта тиісті емес болса. ≡L-Vалфавитіндегі сөздер жиынының эквивалентті қатынасы екенін дәлелдей аламыз. Майхилл Нероуд теоремасы б/ша минималды DFA-та, L-тіл бар, ≡L қатынасынасы б/ша эквивалентті класс санына тең. Берілген қатынас сонымен қатар бинарлы қатынастардағы индексі деп аталады, ind≡L деп белгіленеді.
Майхил-Нероуд теоремасынан эквивалентті кластар саны ақырлы болған кезде ғана тіл регулярлы болатындығы шығады. Егер қатынас шексіз эквивалентті кластар санында тілді бұзса тіл регулярлы болмайды. Бұл тұжырым регуляр емес тілдерді анықтағанда жиі қолданылады.
32 – билет
1. Тіл ұғымы, тілдерге қолданылатын амалдар.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) тілдерге қолданылатын қандай амалдарды жиындар теориясында қолдағанжоқпыз, түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
3.
Тіл ұғымы, тілдерге қолданылатын автоматтар.
Алфавит
дегеніміз бос емес ақырлы жиын, оны
арқылы белгілейміз. Оның элементтерін
символ (symbol) деп атаймыз.
алфавитіндегі сөз (string) дегеніміз осы
алфавиттегіэлементтердің ақырлы
тізбегі. Мысалы:
={a,b,c} алфавит, ал abbba, aa,bbaa- алфавиттегі
сөздер.Анықтама:
Ешқандай
сөзден тұрмайтын сөзді бос сөз деп
атаймыз да оны ℮ арқылы белгілейміз.
алфавитіндегі барлық сөздердің жиынын
арқылы таңбалаймыз.Анықтама:
ύ
сөзі
сөзінің
ішкі сөзі
деп
аталады, егерде ω
ύy
теңдігі орындалатындай x,y сөздері
табылатын болса, x,y екуі де бос сөз болуы
мүмкін. Сондықтан әрбір сөз өзінің ішкі
сөзі болады.
Subw(L)-арқылы
сәйкес L тілінің барлық сөздерінің ішкі
сөздерінен құрылған жиынды белгілейміз.
Анықтама:
Егер L
Σ*
болатын болса, онда L-ді Σ
алфавитіндегі
тіл деп
атайды. Әрбір тілді жиын ретінде
қарастыруға болады, сондықтанда жиындарға
қолданылатын барлық амалдарды осы
тілдерге де қолдануға болады. L
Σ*
болсын, онда Σ*-
L осы тілдің алфавитіне байланысты
толықтауышы деп аталады. Анықтама:
Егер
x,y сөздері Σ*
алфавитінің сөздері болатын болса,
онда xy(x сөзінің соңына y сөзінің басы
тіркеп жазылады) оcы екі сөздің
конкатенациясы
деп аталады6 кейде оны x*y деп белгілейді.
Конкатенация амалы ассосативті, яғни
(xy)z=x(yz).Мысалы: Σ*={a,b}
алфавитінде x=aabb, y=abab сөздерінің
конкатенациясы xy=aabbabab болады. Анықтама:
L1,
L2
Σ*
болсын, онда L1*L2={xy, x
}
L1*L2 тілі L1 мен L2 тілдерінің конкатенацияланған
тілі деп атады. Мысалы: L1={a,abb},
L2={bbc,c}болса, онда L1*L2={ac,abbc,abbbbc}
Анықтама:
L
Σ*
болсын, онда
Анықтама:
сөзінің
кері сөзі деп
сөзіне
кіретін символдарды кері ретпен алғандағы
сөзді айтамыз. Оны
арқылы таңбалаймыз. Мысалы:
=abcdac
болса
.Клини
жұлдызшасы L*= L0∪L∪L2∪L3∪L4∪…
33 – билет
1. Бинар қатынастардың негізгі түрлері. Рефлексив және транзитив тұйықтау.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) қатынасты қай кезде функция деп атаймыз, түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
3.
Бинар қатынастардың негізгі түрлері. Рефлексив және транзитив тұйықтау.
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)}
34 – билет
1. Кез келген ақырлы автомат үшін оған пара-пар, күйлер саны минимал болатын детерминистік автоматты құру тәсілі.
a) негізгі анықтамаларын жазып беріңіз;
б) минималдау туралы теореманы дәлелдеңіз;
в) мысалдар келтіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
, мұндағы w сөзі a,b алфавитінен құрылған,
ал
- кері сөз.
3.
Кез келген ақырлы автомат үшін оған пара-пар, күйлер саны минимал болатын детерменистік автоматты құру тәсілі.
Бізде берілген тіл NFА автоматы арқылы сипатталған болса, онда DFA-ға көшу алгоритмі арқылы тілдің DFA автоматын салып аламыз. Осы DFA автоматында бастапқы күйден бара алмайтын барлық күйлер мен жолдарын алып тастаймыз.
МЫСАЛЫ:
тілінің DFA автоматы берілген болсын
Бастапқы DFA автоматы Артық күйлері алынып тасталған DFA автоматы
Бастапқы
күйден жете алмайтын күйлерді алып
тастағанның өзінде автомат
минимизацияланбаған болуы мүмкін.
Мысалда
және
күйлері эквивалентті күйлер болады,
сондықтан оларды бір күйге біріктіруге
болады.
АН:
-тіл,
болсын.
тілі бойынша эквивалентті
болады, егер барлық
үшін келесі тұжырым дұрыс:
болады, сонда және тек сонда ғана, егер
дұрыс.
-
эквиваленттілікті білдіреді.
дегеніміз x және y екі сөзі де L-ге тиісті
немесе тиісті емес болады.
АН:
M=⟨K,
,
⟩-
детерменистік
ақырлы автомат болсын.
сөздері
осы М автоматы бойынша эквивалентті(x
)
деп аталады, егер осы екі сөз де М
автоматында s
күйден
бірдей ақырлы немесе ақырлы емес күйге
көшсе. Формалды түрде:
Біз M автоматына сәйкес q күйінің
эквиваленттілік класын
арқылы белгілейміз.
Th:
Кез келген детерменистік ақырлы автомат
үшін M=⟨K,
,
⟩-
және кез келген
үшін, егер бұл сөздер Ь автоматы бойынша
эквивалентті болса (x
,
онда бұл сөздер берілген тіл бойынша
эквивалентті болады(x
.
Егер
х-сөз, ал L-тілі автомат бойынша анықталған
болса, онда [x] арқылы х сөзі жататын L
–тілінің эквиваленттілік кластарын
белгілейміз. Мысалдағы
тіліне қатысты
-төрт
эквиваленттілік кластарға бөлінеді:
1)[e]=L
2) [a]=La
3) [b]=Lb
4)
[aa]=L(aa
bb)
М автоматы бойынша эквиваленттілік кластары:
1)
2)
3)
4)
5)
6)
кластары
[e]
класына кіреді. Бұдан барлық эквивалентті
кластар саны төртеу болды. Яғни, соңғы
құратын автоматымыз төрт күйден
тұрады(кұйлер саны эквивалентті кластар
санына тең болады).
Минимизацияланған DFA автоматы
35 – билет
1. Автоматтардың "үрлеу" туралы теоремасы.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) эквивалент класстар ұғымы қолданып тілдің регуляр емес екенін калай көрсетуге болатынын түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
,
мұндағы w сөзі a,b алфавитінен құрылған,
ал
- кері сөз.
3.
Автоматтардың pumping туралы теоремасы.
Тілдің
регулярлы болуы оның қандай да бір
ақырлы детерменистік автомат
қабылданылуымен пара пар. Мұнда М-нің
күйлерінің саны ақырлы. Мысалға n дана.
Рumping
туралы теоремасы. L-регулярлы
жиын болсын, онда
саны бар болып, егер
-кез келген сөз үшін
,
оны
түрінде жазуға болады. мұндағы
әрі кез келген
үшін
.
Рumping туралы теоремадан: егер бір регулярлы жиында жеткілікті ұзындықта
сөзі
бар болса, онда осы жиын
сөзін де қамтитын шексіз жиын дегенді
түсінуге болады.
Рumping туралы теорема қолданылуы. Ойын ретінде қарастырсақ: сіз ж/е тағы бір адам бар, негізгі мақсат сіздің оны жеңуіңіз.
Сіз регулярлы емес деп ойлаған бір L тілін таңдап алыңыз.
Қарсы жақ n санын таңдап алу керек, яғни Рumping туралы теоремадағы тұрақты сан n. Енді кез келген таңдап алынған n санына дайын болу керек, бірақ бір жақсы жері қарсы жағың бір рет n санын таңдап алғаннан кейін ол оны өзгерте алмайды. Дегенмен қарсы жақты өте осал деп санамау керек.
Енді сіз осы L тіліне тиісті бір сөздер тізбегі
-ны
алыңыз. Сіздің таңдап алған
қарсы жағың таңдап алған n санымен іштей
байланыста.Қарсы жағың Сіз берген
сөзін
=xyz
түрінде жіктеп жазылуы керек, яғни
x,y,z-ішкі сөзін белгілеу керек. Әрі олар
шартын қанағаттандыруы шарт.Сіз енді Рumping туралы теореманың тұжырымына қайшы қорытындыға келтіруіңіз керек, ол үшін кез келген анықталған x,y,z ішкі сөздер үшін қандай да бір
бар болып
шартын қанағаттандыратын t санын табу
керек.
