1.Жиындарға қолданылатын амалдар. Функциялар және қатынастар
Саналымды және санаусыз жиындар.
Жиын
рет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
,биекция.
5– билет
1. Детерминистік автоматпен қабылданатын тілдің регуляр өрнегін табу алгоритмі.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) тілдің регуляр өрнегін қолдану мағынасын түсіндіріңіз.
2.
Берілген
тілді
қабылдайтын
Стегі
бар
автоматты
құр:
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=
регуляр
өрнек.
6– билет
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.
7– билет
1. Майхилл-Нероуд теоремасының салдары. (регуляр емес тілдер мен эквивалент кластар арасындағы байланысы туралы)
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) Index(RL) өрнегінің мәні тілдердің регуляр және регуляр еместігіе байланысты қалай өзгереді, түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
3.
Майхилл-Нероуд теоремасының салдары(регуляр емес тілдер туралы)
L
тілі регуляр болады сонда және тек сонда
ғана егер
тілі бойынша анықталған эквивалент
класстар саны ақырлы болса.Дәлелдеу:
Егер L тілі регуляр болса, онда L
кейбір ақырлы автоматтар үшін және
-де
эквиваленттік класстардан аз емес күй
сақтайды. Демек в
эквивалентті класстардың ақырлы саны.
Бұл салдар арқылы тілдің регуляр емес
екендігін де дәлелдеуге болады. Мысалы:
L={
}
Ешқандай
екі сөз
i
бола тұры
қатысты эквивалентті емес, себебі
кейін жазылса да L тілінің сөзін береді,
бірақ
L тіліне жатпайтын сөзді береді. Осыдан
шексіз көп эквивалентті классқа ие.
Осының салдарынан L тілі регуляр емес
болып шығады.
8– билет
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
тілі
регулярлы
тіл
деп аталады, егерде М автоматы табылып:
орындалса.
Ақырлы автоматпен қабылданатынбарлық
тіл регулярлы.
9– билет
1. Ақырлы детерминистік автоматты формалды түрде сипатта.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) осы автоматтың жадысы (сақтау қабілеті) бар ма? Түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
, мұндағы w сөзі a,b алфавитінен құрылған,
ал
- кері сөз.
3.
Ақырлы
детерминистік автоматты формалды түрде
сипатта. Не себепті автомат ақырлы деп
аталады? Ақырлы детерминистік автоматта
жадысы бар ма?
Ақырлы
детерминистік автомат деп(DFA)- M=<K，Σ，δ，S,
F> , бестігін айтамыз. Мұндағы:
К
– күйлер жиыны (ақырлы), Σ
– алфавит, S∈К
– бастапқы күй, F⊆К
– ақырлы күйлер, δ
– көшу функциясы. δ
функциясы К×Ʃ→К.
Кез
келген q∈Q,
a∈Σ
үшін δ(q,a)-нақтылы
анықталған мәні бар болса, онда ондай
автоматты
Детерминистік
ақырлы автомат деп атаймыз. Ереже
бойынша, М автоматының келесі күйі өту
функциясында кодталған. Бұдан, егер М
q∈К
күйінде болып, лентадан a∈Σ
символы оқылса, онда автоматтың өтетін
жалғыз анықталатын күйі, ол δ(q,a)
∈К.
Детерминистік ақырлы автомат кіріс
сөзінің оқылған бөлігіне басын қайтадан
артқа бұрай алмайды, сол жақ бөлігіндегі
сөз саналатын басындағы машинаның ары
қарай функциялануына әсер ете алмайды.
Детерминистік автоматтың конфигурациясы
<K，Σ，δ，S,
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|n≥1} Егер
L(M1)=L(M2), онда M1мен M2 автоматтары эквивалент
деп аталады.
Мысал:
M=<K，Σ，δ，S,
F>, К={q0,
q1},
Ʃ={a,b}, S=q0,
F={q0}
δ
– функциясы
келесі кестемен өрнектеледі:
10 – билет
1. Детерминистік емес автоматтар мен детерминистік автоматтардың эквиваленттілігі.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) детерминистік ақырлы автоматтарды қолдану мағынасын түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
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-ға
11 – билет
1. Детерминистік емес ақырлы автомат ұғымы. Детерминистік емес автоматпен қабылданатын тіл.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) детерминистік ақырлы автоматтардың детерминистік емес ақырлы автоматтармен айырмашылығы, түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
3.
Ақырлы
детерминистік емес автомат ұғымы.
Детерминистік емес автоматпен қабылданатын
тіл.
Детерминистік
емес ақырлы автомат - бұл мына бестіктен
тұрады:
М=(K,
Σ,
∆, s, F)
K- ақырлы күйлердің
жиыны
Σ-
алфавит
s∈K-
бастапқы күй
F
-
ақырлы күйлер жиыны
∆-
көшу күйі, K×( Σ
K
Анықтама: Конфигурация немесе тез
бейнелеу( instantaneous description) ақырлы автоматы
(Q, Σ,
∆, I, F) деп кез-келген реттелген жұпты
(q,
) айтамыз, мұндаq∈Q
және
∈
.Ламбда
тасымалы
Орындалады сонда және тек қана сонда егер qi-ден qj -ге дейін w бойынша бір жол
бар болса болады
Әр
үштік (q,
u,
p)
∈∆
М ге
көшу деп аталады; Бұл бағыттың
формализациясы. Анықталынған
детерменистік ақырлы автоматтармен
детерменистік емес ақырлы автоматты
есептеудiң анықтамасы өте ұқсас.
Конфигурация М бұл K×
.
Конфигурацияның арасындағы жағдай
былай
анықталады: (q, w)
(
)
сонда және тек сонда ғана, u∈
{e}
болған жағдайда, w=u
және (q, u,
)∈∆.
Байқасақ
– міндетті түрде функция емес: кейбір
конфигурацияларға (q, w) бірнеше жұп болуы
мүмкін (
)
немесе ешқандай жұп болмауы мүмкін -
(q, w)
(
).
12 – билет
1. Детерминистік емес ақырлы автомат ұғымы. Детерминистік емес автоматпен қабылданатын тіл.
a) негізгі анықтамаларын жазып беріңіз;
б) мысалдар келтіріңіз;
в) детерминистік ақырлы автоматтардың детерминистік емес ақырлы автоматтармен айырмашылығы, түсіндіріңіз.
2.
Берілген тілді қабылдайтын Стегі бар
автоматты құр:
3.
Ақырлы
детерминистік емес автомат ұғымы.
Детерминистік емес автоматпен қабылданатын
тіл.
Детерминистік
емес ақырлы автомат - бұл мына бестіктен
тұрады:
М=(K,
Σ,
∆, s, F)
K- ақырлы күйлердің
жиыны
Σ-
алфавит
s∈K-
бастапқы күй
F
-
ақырлы күйлер жиыны
∆-
көшу күйі, K×( Σ
K
Анықтама: Конфигурация немесе тез
бейнелеу( instantaneous description) ақырлы автоматы
(Q, Σ,
∆, I, F) деп кез-келген реттелген жұпты
(q,
) айтамыз, мұндаq∈Q
және
∈
.Ламбда
тасымалы
Орындалады сонда және тек қана сонда егер qi-ден qj -ге дейін w бойынша бір жол
бар болса болады
Әр
үштік (q,
u,
p)
∈∆
М ге
көшу деп аталады; Бұл бағыттың
формализациясы. Анықталынған
детерменистік ақырлы автоматтармен
детерменистік емес ақырлы автоматты
есептеудiң анықтамасы өте ұқсас.
Конфигурация М бұл K×
.
Конфигурацияның арасындағы жағдай
былай
анықталады: (q, w)
(
)
сонда және тек сонда ғана, u∈
{e}
болған жағдайда, w=u
және (q, u,
)∈∆.
Байқасақ
– міндетті түрде функция емес: кейбір
конфигурацияларға (q, w) бірнеше жұп болуы
мүмкін (
)
немесе ешқандай жұп болмауы мүмкін -
(q, w)
(
).
