JAG Flashcards
abeceda
Konecna neprazdna mnozina symbolu, znaci se velka Sigma
Slovo nad abecedou
Kazda konecna posloupnost [rvku abecedy
Prazdne slovo
Epsilon (e), je posloupnost, ktera nema zadne slovo/symbol
Delka slova
Je pocet symbolu/znaku, znaci se |w|, kardinalita znaku je pocet danych znaku ve slove
Sigma+ abeceda
Mnozina vsech slov vcetne prazdneho // uplne vsech moznych na vsemi moznymi znaky
u,v jsou slova, pak u*v je…
Retezeni v za u. Tedy vznikne uv.
Je to asociativni (muzu uzavorkovat jak chci), ale neni komutativni (nemuzu prochazet aby vysledek byl furt stejny)
Mocnina slova u^n
Je to uuu… = uuuu…u n-krat
u^0 = prazdne slovo
Podslovo w slova u
Je to vybrana posloupnost znaku slova u tak, ze:
u = xwy
Prefix/sufix
Podslovo x je prefix, p.t.k
xw = w, x je prazdne slovo
Podslovo x je sufix p.t.k
wx = w, x je prazdne slovo
Jazyk nad abecedou
Mnozina vsech slov nad zadanou abecedou Sigma.
Je to jeden vybrany jazyk, tedy je to podmnozina Sigma+
Nejvic basic schema konecneho automatu
Ma ridici jednotku a stavy. Ridici jednotka precte vstup, zmeni svuj stav a posune citac na dalsi vstup, pripadne vrati vysledek. Treba automat na kafe: vstupy - mince, stavy - kolik minci uz ma. Tedy kouka, kolik minci mu prislo, kolik uz ma a podle toho se dostane do predem definovanych stavu - vratit kafe, pripadne vratit penize
Kazdy konecny automat ma…
- Konecnou mnozinu stavu Q
- Konecnou mnozinu vstupu Sigma
- Prechodovou fci delta
- Pocatecni stav q0
- (Pro Mealyho a Mooruv automat) vystupny lambda a beta funkce
Mealyho automat, definice
Prechodova fce je zadana z mnoziny stavu a vstupuun na mnozinu stavu, tedy:
delta: QxSigma -> Q,
tedy znamena to - mam stav Q, prijde vstup Sigma a vyplivne to vystup stav Q novy
Konkretni zapis:
delta:(q,a) = p. kde q je aktualni stav, a je novy vstup, p je vysledny stav
Mooruv automat, definice
beta: Q->Y, kde Y je ano/ne, sviti/nesviti…
DFA automat, definice
Deterministic Finate Automata - deterministicky konecny automat,
ma definovane vsechny prechody (determinismus, kazdy prechod je JEDNOZNACNY), ma konecne stavu, patri do skupiny Moorova automatu
M=(Q, Sigma, delta, q0, F), kde Q je mnozina stavu, Sigma je abeceda, delta je prechodova funkce, q0 je poc. stav, F je mnozina koncovych stavu
beta: Q->Y, Y={0,1}=> F={q|beta(q)=1}, mnozina koncovych stavu
tedy rozhoduje, zda automat prijme nejaky vstup/obashuje podslovo atd… tj konci v koncvoem stavu prechodovou funkci beta ze stavu q do 1.
Prechodova funkce delta, definice obecne a rozsirena
delta(q, a) = p, kde q je aktualni stav, a je novy vstup (na ktery q reaguje), p je vysledek, kam se posle a z q.
Rozsirena prechodova funkce definovana indutkvine:
1. delta(q, epsilon) = q // nic se nezmenilo
2. delta(q, ua) = delta(delta(q,u), a) // odtrhnul jsem posledni znak
3. delta(q, uv) = delta(delta*(q,u), v) // odtrhnul jsem posledni slovo
Tedy slozity pripad, kde novy vstup muze byt az cele slovo, rekurzivne rozbijim na mensi celky tak, ze odtrhavam posledni znak az dojdu na konec, tam provedu zmenu do dalsiho stavu a vracim se o kok zpet…
Priklad:
Pokud mam zadany automat a mam rozhodnout, zda treba prijima slovo 001110, tak zacnu od prvniho znaku, pak druheho, pak rekurzivne se zanoruju az do posledniho znaku a tam na konci mi musi vyjit ano/ne…
Slovo w lezi v mnozine koncovych stavu F automatu M p.t.k.
Jinak receno: slovo lezi v L(M), nebo slovo je prijato automatem…
Rozsirena prechodova funkce aplikovana rekurzivne na w z nejakeho pocatecniho stavu skonci v jednom z koncovych stavu, tedy:
delta*(q0, w) = p, p lezi v F.
Jazyk prijimany automatem M, definice
Je to takova mnozina slov, ktera pro zadany automat skonci v nejakem z koncovych stavu, tedy
L(M) = {w | delta*(q0, w) = p, p lezi v F}
Jazyk L je regularni p.t.k
Existuje DFA automat, ktery ho prijima, tedy:
L(M) = L // jazyk prijimany automatem je muj zadany jazyk L, znaci se reg
Jak zajistim, ze automat prijima slova s poctem nul treba 3k?
Treba ma cyklus delky tri takovy, ze je pruchozi pouze tremi nulami za sebou…
Pumping Lemma
DUKAZ NEREGULARITY JAZYKA
Pokud je L reg, pak existuje n z N s vlastnosti:
ProKazde slovo u z L, ktere je delsi nez n, ho lze rozdelit na 3 casti u=xwy tak, ze:
1. |xw| <= n //y muze byt prazdne slovo
2. w je neprazdne
3. ProKazde i z N plati: xw^iy patri do L // tedy mohu pumpovat w a slovo bude stale patrit do jazyka L.
Pokud vetsinou 3. podminka je porusena -> spor s regularitou jazyka => jayzk NENI regularni
TIM ALE NEMOHU DOKAZAT REGULARITU
Tvrzeni - jazyk L neni regularni, dokaze Pumping Lemmatem
L = {0^m 1^m | m >=0}, tedy je to 00…0011…11
Kdyby L byl reg, pak existuje n takove, ze pro kazde slovo delsi nez n musi platit tri vlastnosti.
Zvolim si tedy slovo provazane s n, aby bylo delsi nez n. Tedy zvolim si treba 0^n1^n = u, Pak |u| = 2n > n OK. Pak musi platit:
u = xwy. Nakreslim si jak by vypadalo slovo:
00..00 n-krat 11…111 n-krat.
- |xw| <= n // tedy xw = 0^L, musi to byt same nuly, aby |xw|<=n
- w != prazdne, tedy w = 0^k, nekolik 0 tam musi byt
- Pak pro kazde i musi platit: xw^iy splnuje jazyk L, tedy byt ve tvaru
xwy = 0^n1^n:
vezmu i=2, pak xw^2y = 0^(n+k)1^n, coz nepatri do L pro K >0.
Tedy pridal jsem tam k-krat 0 navic, coz porusilo L
Obecne nakreslim jak by slovo vypadalo a snazim se pridat do nejake casti pumpingem tolik symbolu, abych porusil L
Nerodova veta
PRO DUKAZ I VYVRACENI REGULARITY, vetsinou pro vyvraceni
Jazyk L je reg p.t.k existuje ekvivalence T takova, ze:
1. L je sjednoceni nekterych trid ekvivalenci T
2. Jestlize pro dve slova plati uTv, pak i pro libovolne w plati: uwTvw
3. T ma pouze konecne mnoho trid ekvivalenci
Dokazte, ze jazyk L = {0^m 1^m | m >=0}, neni regularni Nerodovou vetou
Chci dokazat, ze neexistuje ekvivalence T splnujici 3 podminky regularnich jazyku.
Kdyby L byl reg, pak existuje ekv. T sp[lnujici 3 podminky.
1. Zvolim nekonecnou posloupnost slov nad abecedou L - treba
0, 0^2, 0^3… 0^k. Je to nekonecna posloupnost, ale T ma pouze konecne trid ekvivalence, takze je omezena a nektera ruzna slova se musi nutne vejit do stejne tridy ekvivalence (neco jako krabickovy princip z DMA).
2. Existuje tedy takovy i!=j, ze (0^i)T(0^j).
3. Chci tady dokazat, ze pokud neco pridam napravo, tak jedna strana mi nebude lezet v L, zvolim si tedy jako w=1^i.
4. Pak (0^i1^i) T (0^i1^j), ale 0^i1^j nelezi v L, tudiz L neni sjednoceni nekterych trid ekvivalence T -> spor -> jazyk neni regularni
Tedy obecne najdu nejakou nekonecnou posloupnost a snazim se pridat takovou pravou stranu, aby v jednom pripade nove slovo bylo v L ale druhe ne.
Dukaz ze jazyk je regualrni pomocni invariant
Mam zadany nejaky jazyk L. Skusim nakreslit jeho DFA graf/automat.
Pak kazdy stav popisu pomoci jeho invariant, tedy ze v tomto stavu skoncim POUZE ZA TECHTO PODMINEK.
Tyto podminky pro vsechny stavy jsou DISJUNKTNI.
Pokud kazdy stav jsem pospal jako disjunktni pomdinky p[okryvajici ale vsechny mozne varianty, tak jsem nasel spravny automat, ktery prijima L, tedy L je regularni.
delta*(q0, u) = pi p.t.k slovo treba konci 01…
Takze kazdy pi stav popisu nejakou podminkou disjunktni
Ekvivalentni automaty
P.t.k prijimaji stejny jazyk
L(M1) = L(M2)
Dosazitelny stav
Stav p je dosazitelny p.t.k
delta*(q0, u) = p, tedy se tam dostanu z pocatku nejakym slovem u
Ekvivalentni stavy
Stavy p1 a p2 jsou ekvivalentni p.t.k
delta(p1, u) = F <=> delta(p2, u) = F,
tedy oba stavy vedou do koncoveho stavu nebo oba nevedou.
Tedy oba vedou do stejneho stavu stejnymi rpechody -> mohu je slepit dohromady
Redukovany automat
Je to nejmensi mozny automat, ktery prijima totez co jeho rozsirenenjsi verze, ale ma nejmene prvku. (Je jednoznacne urceny)
Tedy odstranuje zbytecne uzly a prechody, ktere se daji redukovat treba na jeden uzel jenom.
Redukovany autoamt nema nedosazitelne stavy a nema ekvivalentni stavy, tj stejne, co delaji totez
Algoritmus redukce tabulkou
Rozepisu si prechody automatu.
1. Krok - rozdelim vsechny stavy na N-nekoncovy, K-koncovy
2. Krok - udelam prechody vsechny, ale tentokrat ne do stavu ale jejich skupiny (N a K).
3. Neco se mi rozbilo a treba z N N jsem dostal N K -> prohlasim to za novy stav treba A (a vsechny stejne uzly s NK prohlasim za A), opakuju to tak dlouho dokud se nebude rovnat posledni a prdposledni sloupec skupin stavu.
Koncove stavy zustavaji koncove uz navzdy.
Obecne:
Pridavam sloupce, kde kazdy novy krok je prechod z nejake SKUPINY stavu do jine nebo stejne skupiny. Jakmile se mi nerovna predchozi a nova skupina - prejmenovavam ji. Skoncim kdyz se mi rovnaji posledni a predposledni pojmenovani uzlu - tj zadna skupina se mi uz nerozpadla.
Pak Spojim stavy ze stejne skupiny - jsou totiz ekvivalentni - do jednoho uzlu a mam JEDNOZNACNY redukovany automat.
Isomorfni automaty
Existuje mezi nimi bijekce, ktera pouze prejmenovava stavy. Jsou to identicke autoamty az na jmena stavu
NFA automat
Prechody muzou byt nejednoznacne pro zadany vstup - tedy mohu napriklad jednickou skocit dal NEBO se zustat tocit v cyklu… Jednicka mi tedy oznacuje DVE MOZNOSTI MISTO JEDNE DETERMINISTICKE - tedy nemohu urcit jiste, kam se vydam - nedetermenisticky automat.
Muze mit i vice vstupnich uzllu - tedu komponent souvislosti jakoby
NFA prijima jazyk L, pokud kazde slovo z L zacne v NEJAKEM q0 a skonci v NEJAKEM F (je jich vice, DFA ma pouze 1)
epsilon-NFA automat
Obsahuje i epsilon-prechody, tedy bez ZADNEHO vstupu se mohu nekam pohybovat. Treba vyrabet (01)^n tak, ze q0 ->(0)q1 ->(1)q2 A ZPATKY DO q0 epsilonem. Tedy uzavru smycku a muzu znovu
Epsilon-uzaver
e-uz(X) je definovan jako:
1. X je podmnozinou sveho uzaveru
2. Je-li p lezi v e-uz(X), pak delta(p, epsilon) je v uzaveru
Tedy v e-uz(X) lezi samotne X a pak vsechny jine stavy, do kterych se dostanu z X pomoci epsilon-prechodu.
Kazdy jazyk prijimany e-NFA automatem je…
Regularni, protoze kazdy e-NFA automat se da prepsat na DFA, takze jazyk je prijiman nejakym DFA -> takze je regularni
Co je podmnozinova konstrukce/k cemu se pouziva
Pro prepis NFA tabulky na neredukovany DFA
Zacnu v pocatecnim bode, koukam, na jake stavy me to posle, do radku pridavam nove/dosud nepopsane stavy tak dlouho, dokud jsem nepokryl vsechny stavy vsemi prechody. Neresim uzavery pokud to nema e-prechody.
Algoritmus nalezeni DFA pro zadany e-NFA
Mam treba zadanou tabulku prechodu, kde p je pocateni, s je koncovy stav:
e 0 1 p {q,s} nic nic q nic r nic r nic nic s s q nic nic
- Udelam e-uzavery kazdeho prvku jako: samotny prvek + vsechny prvky, kam se z nej dostanu e-prechodem (plus jejich vlastni uzavery rekurzivne…):
uz(q) = q
uz(r) = r
uz(s) = {s} + uz(q) = {s,q}
uz(p) = {p} + uz(q) + uz(s) = {p,q,s} - Delam novou tabulku ALE UZ BEZ E-PRECHODU SLOUPCE
Zacnu uzvarem vsech pocatecnich stavu:
tedy uz(p) = {p,q,s} je muj PRVNI NOVY POCATECNY STAV a koukam, kam bych se dostal z jeho VSECH pod-stavu v puvodni tabulce (koukam na cely sloupec pro p, q i s) a beru pak UZAVERY CILU, tedy pokud {p,q,s} v puvodni tabulce me nulou poslou do (nic, r, nic) -> tak v nove tabulce to bude {p,q,s} nulou prejde na (uz(nic), uz(r), uz(nic)) = r a jednickou nikam. Tedy vezmu skupinu, podivam se do jakych stavu me dostane v puvodni tabulce a pak na misto techto stavu beru jejich uzavery. Pokud mi vznikne prechod do NOVEHO STAVU -> pridam ho do dalsiho radku VCETNA PRAZDNEHO STAVU A JEHO PRAZDNYCH PRECHODU0 1 {p,q,s} r nic // dostal jsem DVA NOVE STAVY -> HNED JE ZAPISU: 0 1 {p,q,s} r nic r nic {s,q} //dostal jsem novy stav {s,q} -> pridavam ho nic nic nic 0 1 {p,q,s} r nic r nic {s,q} nic nic nic {s,q} r nic //NEPRIDAL jsem novy stav -> KONEC
Toto je NEredukovany DFA, pocatecni stav je ten, kde byl puvodni pocatecni, tedy {pq,s} je novy pocatecni stav, ktery mohu slepit do jehnodo, koncovy je tam, kde byl puvodni koncovy, tedy {pq,s} {sq}
Operace s jazyky 6 typu
- Sjednoceni: (L1 sjednoceno s L2)
- Prunik: (L1 prunik s L2)
- Doplnek: L1 doplnek = Sigma+ i L1
- Zretezeni: L1L2 = {uv | u z L1, v z L2}
- Kleeneho operace: L* = opakovani/mocneni = L^1 s L^2 s L^3…
- Reverze: L^R = {wR | w z L}
Regularni jazyky jsou uzavrene na vsech 6 operaci
Regularni vyraz definice
Je dana abeceda symbolu Sigma. Mnozina vsech regularnich vyrazu je definovana induktivne:
- prazdna mnozina, prazdne slovo, symbol ze Sigma jsou regularni vyrazy zakladni
- Jsou-li u,v regularni vyrazy, pak u+v, uv, u* jsou regularni vyrazy
Kazdy jazyk reprezentovany regularnim vyrazem je…
Regularni - tedy na kazdy regularni vyraz jsem schopen sestavit DFA ktery ho znazornuje/prijima
Kleeneho veta
Kazdy jazyk prijimany konecnym automatem (tedy regularni jazyk) je mozne prepsat na regularni vyraz
Definice ekvivalence dvou regularnich vyrazu p,q
Regularni vyrazy jsou ekvivalentni p.t.k jimi reprezentovane jazyky jsou stejne, znacime p |=| q a plati:
- p+q |=| q+p
- (p+q)r |=| pr + qr |=| r(p+q) |=| rp + rq
- (r) = r*
…
Dva zpusoby jak z reg. vyrazu nakreslit automat
- Pomoci Kleeneho vety - z vyrazu rovnou zakresluju, a pomoci epsilon-prechodu rozlisuju smycky, je to ale riskantni, nemusim si vsimnout vsech prechodu
- Primou metodou - algoritmus, spolehlivejsi.
- Ocisluju vsechny symboly vyrazu
- Cim vyraz muze zacinat?
- Cim muze koncit?
- Ktera dve pismena mohou byt hned za sebou?
- Muze reg. vyraz byt jenom prazdne slovo?
Tim jsem dostal vlastne vsechny pocatecni stavy v 2. kroku, koncove stavy v 3. kroku a prechody ve 4. kroku (kde prechody reaguji na stejna pismena jako jsou stavy, treba a1 muze prejit do a2 ACKEM nebo do b1 BECKEM, tedy prechody jsou podle pismenka stavu).
Pokud je splnena 5. podminka, tak pridam hlavni pocatecni i koncovy stav S, ze ktereho mi vedou prechody do pocatecnich stavu podle jejich pismenek.
Algoritmus, jak ze zadaneho automatu ziskat reg. vyraz
- Pridam Start a Finish
- Ze startu pridam e-prechody do vsech pocatecnich stavu
- Ze vsech koncovych stavu pridam e-prechody do Finish stavu
- Odstranim vsechny smycky jako jejich * opakovani (treba smycka s prechodem a -> a, tato a se nalepi na vsechny vychazejici hrany z daneho stavu
- Odstranuju paralelni hrany jako +, treba mi vedou dve hrany: a, b -> nova hrana je jenom jedna: a+b
- Odstranuju vrcholy tak, ze slepim vsechny mozne cesty ktere do nej vchazely s temi, ktere z nej vychazeji
Algoritmus konci, kdyz jsem odstranil posledni uzel a zustaly mi pouze Start a Finish a mezi nimi jedna jedina hrana s vyslednym regexem.
Na poradi kroku nezalezi, mohou mi podle ruznych kroku vyjit zdanlive ruzne vyrazy na konci, ale jsou ekvivalentni, pouze ruzne zapisy
Gramatika definice
Gramatike G je ctverice (N, Sigma, S, P), kde
N - konecna mnozina neterminalu,
Sigma - konecna mnozina terminalu,
S - startovaci symbol,
P - konecna mnozina pravidel typu alfa->beta, kde alfa a beta jsou slova nad NaSigma takova, ze alfa obsahuje alespon jeden neterminal // tedy pravidla typu Aa -> cokoliv, kde a je terminal, A neterminal
Prime odvozeni z gramatiky
Je dana gramatika G=(N, Sigma, S, P). Rekneme, ze delta se primo odvodi z gamma, jestlize existuje pravidlo takove alfa->beta a slova u,v, tak, ze:
gamma = ualfav a delta=ubetav, tedy delta vznikne z gamma nahrazenim leveho vyskytu alfa jeho pravou stranou beta
Derivace gramatiky
Je to “odvozeni”, tedy gamma=gdelta, tedy gamma aplikuje odvozeni opakovane a ziskava deltu
Jazyk generovany gramatikou, definice
L(G) = {w | S =>g*w}, tedy je mnozina slov takovych, ze ze startovniho symbolu se postupnym odvozovanim dostaneme tato slova. Tedy gramatika G “generuje” slova postupnym aplikovanim pravidel
Ctyri typy gramatik
- Kontextova - ma pravidla s kontextem, treba neterminal se prepise na neco POUZE POKUD JE NECIM OBKLOPEN:
0S -> 01, tedy nemohu prepsat S->1, protoze tam potrebuju ten kontext zleva 0. - Bezkontextova - muze cisty neterminal prepsat na cokoliv
- Regularni - generuje regularni jazyky
4.
Nevypousteci gramatika
Je to gramatika takova, ze nema zadne pravidlo typu:
neterminal -> epsilon (prazdne slovo),
Tedy nejde “vypustit” neterminal, zapomenout ho, prepsat na nic.
Takova gramatika neumi vygenerovat prazdne slovo
Tvrzeni: Ke kazde bezkontextove gramatice existuje nevypousteci gramatika tak, ze generuje…
Uplne vsechno, co ta prvni, ale bez prazdnych slov.
Tedy ji prepisu na nevypousteci gramatiku, ale ponecham vsecnhno co generuje az na epsilon
Algoritmus sestaveni nevypousteci gramatiky
Mam zadanou gramatiku treba:
S -> aSc | A
A -> bAc | e
- Hledam vsechna pravidla, ktera se prepisou rovnou na e v “jednom” kroku: u1 = {A}
- Hledam pravidla, ktera se prepisou na u0, tedy na e ve “dvou” krocich: u2 = u1 + {S} = {A, S}
- Hledam pravidla, ktera se prepisou na u1, tedy na e ve “trech” krocich: u3 = u2 + {…}
OBECNE:
Pridavam do me ui mnoziny pravidel takova pravidla, ktera za i-kroku vidi na epsilon - tedy postupne ji doplnuju jako:
ui = u(i-1) + pravidla, ktera se prepisou na CISTA pravidla z u(i-1).
Koncim, kdyz jsem v dalsim kroku nic nepridal.
Tedy tady mam u2 = {A, S} - vypusteci prvky. Ted vezmu puvodni gramatiku a prepisu jeji puvodni pravidla vsechny ALE BEZ EPSILONU UZ:
S -> aSc | A
A -> bAc |
Pote se podivam na prave strany pravidel a pro kazdy vyskyt takovych neterminalu, ktere mam v u2 (vypustecich prvcich) a pridam takova pravidla, ze je v puvodnich vynecham, tedy pokud X -> necoVYPOUSTECIneco, tak to prepisu na X -> necoVYPOUSTECIneco | neconeco…
Tedy:
S -> aSc | A | ac | (vynecham A, ale to by bylo e, takze nic uz nepisu)
A -> bAc | bc
Vynechal jsem S a A
Veta: K regularni gramatice umim najit…
e-NFA automat.
Algoritmus hledani e-NFA k zadane gramatice
PRIKLAD:
S -> A|B
A -> aaA | bba
B -> bA | e
e-NFA sestavim tak, ze pro kazdy stav popisu jeho prechody bud pomoci a,b nebo bez prechodu, tedy pomoci e. Chci neco jako:
Z S se dostanu do A,B pomoci e-prechodu, z B se dostanu do A pomoci b-prechodu atd…
Potrebuju proto vsechna pravidla prepsat pouze na tvary typu:
Net -> Net | Net
Net -> pismenko Net | e // e v tomto pripade znaci koncovy stav
Tedy v zadane gramatice pravidla S, B mi vyhovuji, uz jsou ve spravnem tvaru. Potrebuju prepsat A tak, ze bude (pismenko Net), tedy pridam nove neterminaly, kam “schovam” aA a bb:
S -> A|B // OK
B -> bA | e //OK
A -> aA1 | bC1 //tedy aA jsem schoval do noveho neterminalu a ba
A1 -> aA
C1 -> bC2 //protoze nemuzu mit pravidlo Net -> term term, schovam “a” za novy neterminal C2
C2 -> aC3 // protoze nejde Net -> term, pridam tedy C3 ktere hned zapomenu
C3 -> e
HOTOVO
Automat vypada jako:
S je pocatecni stav, ktery e-prechody prejde do A nebo B,
A prejde ackem do A1, nebo beckem do C1,
A1 prejde ackem do A,
C1 prejde beckem do C2,
C2 prejde ackem do C3,
C3 je koncovy stav
B prejde beckem do A a je koncovy
Ukazka derivace/odovozeni slova z gramatiky
S -> AB
A -> 0A0 | 1A1 | e
B -> 2B | e
S=>AB=>0A0B=>0A02B=>01A102B=>01102
Problematika jednoznacnosti derivace
Derivace nemusi byt jednoznacna, protoze muzu pouzivat pravidla nechronologicky, ale jak chci, tim padem se mi mohou navzajem ovlivnovat a cpat se mezi sebe. Tedy derivace v tomto pripade muze vyjit ruzne.
Pokud ale pouzivam levou derivaci - vzdy prepisuju nejvic levy neterminal - pak je derivace jednoznacna
Derivacni strom
Graficke znazorneni derivace gramatiky - ukazuje jak jsem prepisoval pravidla od pocatecniho pravidla dolu na odvozena. Kazdy krok je deleni stromu - pouziti prepisovaciho pravidla
Vysledne slovo prectu jako posledni prvky kazdeho “podstromu”
Jednoznacna gramatika
Gramatika je jednoznacna p.t.k pro kazde slovo, ktere gramatika generuje, existuje pouze jeden derivacni strom
Nejednoznacna gramatika
Pokud pro alespon jedno slovo, ktere je generovano gramatikou, existujou dva ruzne derivacni stromy.
Treba
S -> S+S | a, chci slovo w=a+a+a+a
- Derivacni strom pulim rovnomerne pro kazde S a na konci vsechno zmenim na a.
- Derivacni strom odvozuju “doleva” - prepisuju leva S na S+S a prava S na a
Tedy mam 2 ruzne derivacni stromy -> nejednoznacna gramatika
Viceznacny jazyk
Jazyk je viceznacny p.t.k kazda gramatika, ktera ho generuje, je viceznacna
Co musim prokazat, kdyz navrhnu gramatiku, ktera ma generovat nejaky jazyk?
- Vygeneruje vsechna slova daneho jazyka - dokazuju tak, ze po i-krocich a treba j-prepisech nutne musim dojit do stavu, ktery predepisuje jazyk ze zadani
- Nevygeneruje nic navic - dokazuju tak, ze po jistych upravach nejaka pravidla musi nutne zmizet takze nejde vytvorit neco mimo jazyk…
Chomskeho normalni tvar gramatiky
Gramatika je v Chomskeho normalnim tvaru p.t.k
ma pravidla pouze dvou typu:
1. Net -> NetNet
2. Net -> term
Pro kazdou gramatiku existuje chomskeho normalni tvar, ktery generuje totez az na prazdne slovo
Obecny postup na transformaci gramatiky na jeji chomskeho normalni tvar
Obecny postup:
1. Sestrojim nevypousteci gramatiku
2. Odstranim pravidla typu A->B tak, ze primo dosadim pravidla B
3. Odstranim X->aY tak, ze X->ZY, kde Z je nove pravidlo Z->a
4. Zkracujeme pravidla delsi nez 2 tak, ze pridavam nova pravidla treba A->ABC prepisu jako A->AD, kde D->BC…
Prevedte gramatiku na chomskeho norm. tvar:
S->SCA |a
A->aCb | e
C->AA | b
- Nevypousteci gramatika:
u1 = {A}, u2 = u1 + {C} = {A,C} = u3:
S-> SCA|SA|SC|a
A->aCb|ab
C->AA|A|b - Zbavim se pravidel typu Net->Net:
tady mi vadi C->A, takze za A dosadim primo jeho pravidla:
C-> AA|(aCb|ab) - pravidla A | b
Novy tvar je tedy:
S-> SCA|SA|SC|a
A->aCb|ab
C->AA|aCb|ab|b
- Zbavim se pravidel typu X->aNetb tak, ze pridam Z->a, W->b, ale ne v pripade X->a, tady to splnuje chomskeho tvar:
tady mi vadi A->aCb, A->ab, C->aCb, C->ab, takze pridam
X->a, Y->b a novy tvar je:
S-> SCA|SA|SC|a
A->XCY|XY
C->AA|XCY|XY|b
X->a
Y->b
- Roztrham pravidla delsi nez 2:
Tedy A->ABC nahradim A->AD, kde D->BC…
tady mi vadi: S->SCA, A->XCY, C->XCY, takze pridam B->CA, D->CY, novy tvar je:
S-> SB|SA|SC|a
A->XD|XY
C->AA|XD|XY|b
X->a
Y->b
B->CA,
D->CY
- Novy tvar splnuje chmomskeho normalni tvar -> hotovo
Obecny postup redukce gramatiky
Neobsahuje zbytecna pravidla, tedy redukovana gramatika je takova, ktera vygeneruje to stejny co jeji rozsirena verze, akorat ma nejmensi mozny pocet pravidel.
- Sestrojim mnozinu V jako mnozinu neterminalu, ktere vedou na terminaly v n-krocich.:
v1 = neterminaly, ktere se ihned prepisou na terminal v “jednom” kroku
v2 = v1 + neterminaly, ktere se prepisou na terminal ve “dvou” krocich, tedy takove, ktere se prepisou na aXb, kde X uz lezi v1 - tedy pridam takova pravidla, ktera se prepisou na bud samotny neterminal, nebo obklopeny terminaly neterminal, ktery je uz v predchozi mnozine, tedy nesmi tu byt X->YZ, kde Y je ve v, ale Z neni
v3 = v2 + {…}
Pokud vi = v(i-1) - koncim prvni fazi.
Pokud startovni pravidlo S nelezi ve V -> pak grmatika nic negeneruje.
L(G) = prazdna mnozina
- Z puvodni gramatiky necham pouze takova pravidla, jejichz neterminaly jsou ve V, zbytek pravidel, ktere nejsou ve V, vyhodim
- Sestrojim induktivne mnozinu U jako mnozinu pravidel takovych, ze ze startovniho symbolu S se dopracuju do stavu aXb, tedy se ptam v kazdem kroku - kam se dostanu z S, do jakych neterminalu treba obklopenych terminaly.
u1 = {S} - startovni symbol vzdy
u2 = u1 + {kam se dostanu z S, do jakych neterminalu se dostanu z S, tady uz neresim jestli ciste, nebo obklopene a cim}
u3 = u2 + {kam se dostanu z pravidel z u2…}
Koncim kdyz u3=u4 treba. - Zase vyhodim vsechna pravidla, ktera se nedostala do mnoziny U.
Redukujte gramatiku:
S->SA|SB|e
A->bSA|baS
B->aB|Ba|DA
C->aCB|bA
D->AB
- Sestrojim mnozinu V - pravidla, ktera se za n-kroku dostanou do terminalu:
v1 = {S}
v2 = v1 + {pravidla, ktera se prepisou na S samostane nebo obklopene terminaly} = {S,A}
v3 = v2 + {co se prepise na samostatne A, nebo A s terminaly} = {S,A,C}, neni tam B, protoze B->DA, tedy ANet, coz porusuje V, to same pro D->AB, A neni samostane nebo pouze s terminaly…
v4 = v3 = V, S patri do V - gramatika neco generuje - Vyhodim vsechny neterminaly vcetne pravidel s jejich vyskytem, ktere se nedostaly do V:
S->SA|e
A->bSA|baS
C->bA - Sestrojim U - {S} + pravidla, do kterych se dostanu z S:
u1 = {S} vzdy
u2 = u1 + {kam se dostanu z S} = {S, A}
u3 = u2 + {kam se dostanu z A} = {S, A} = u2 -> hotovo. - Vyhodim vsechny neterminaly vcetne pravidel s jejich vyskytem, ktere se nedostaly do U:
S->SA|e
A->bSA|baS - Vysledna gramatika je redukovana a generuje totez, co puvodni
Pumping Lemma pro ContextFree gramatiku
Pro kazdou CF gramatiku s jazykem L existuje m prirozene tak, ze pro vsechna slova z L takova, ze |w| >= m, je lze rozdelit na 5 casti:
z = uvwxy tak, ze
1. |vwx| <= m
2. vx je neprazdne (alespon jedno z nich)
3. ProVs i >=0 plati: uv^iwx^iy lezi v L
Pumping lemmatem dokazte, ze jazyk L={0^n1^n2^n | n>=0} neni CF
Kdyby byl CF, pak existuje m prirozene takove, ze pro vsechna slova z L delsi nez m plati 3 podminky…
Zvolim si slovo z=0^m1^m2^m, lezi v L a |z| = 3m >= m
Pak ho lze rozdelin na z=uvwxy a plati:
1. |vwx| <= m -> takze obsahuje obsahuje MAXIMALNE dva ruzne symboly (muze se schovat treba do 0^m, nebo 1^m, nebo 2^m, nebo byt mezi nimi, ale nemuze byt mezi vsemi tremi naraz.
2. Pak ale kdybych pumpoval pro i=o:
uv^0wx^0y = uwy, tedy odebral jsem nejake symboly, NELEZI V L, protoze nesplnuje podminku L.
Tedy to NENI CF jazyk.
CYK algoritmus, co dela
Rozhoduje, zda zadana gramatika generuje nejake slovo a jeho derivacni strom.
Zada se tabulka pyramidova, kam do spodniho radku napisu pravidla, ktera se rovnou prepisujou na jednotliva pismenka slova. Pak kazdy radek vys je o bunku kratsi a vznika kombinaci, jaka pravidla mohla byt generovana. Na uplnou spicku se mi musi vejit S, pokud tam neni S, tak gramatika negeneruje slovo. Pak zpetnym prechodem mohu urcit derivacni strom. Celou dobu delam jakousi primku, ktera se postupne naklonuje proti smeru hodinovych rucicek
Zasobnikovy automat definice
ZA je sedmice:
A = (Q, Sigma, Gamma, delta, q0, Z0, F), kde
Q - mnozina stavu
Sigma - mnozina vstupu
delta - prechodova fce
q0 - pocatecni stav
Z0 - vrchol zasobniku
F - koncove stavy
Funguje jako:
cte vstupy na pasce - precte vstup - koukne na aktualni stav - prejde do jineho stavu - zapise na zasobnik - cte dal.
Situace ZA, definice
Je-li ZA ve stavu q, na pasce je jeste neprectene slovo u a obsah zasobniku je slovo gama, pak situace je trojice:
(q, u, gamma), kde gamma je vrchol zasobniku
Jeden krok ZA ze situace (q, au, xgamma)
Znaci se |-A, kde A je zas. automat
Tedy jsem ve stavu q, ctu symbol a (zbytek slova u me zatim nezajima, krok je pouze po jednom znaku) a na zasobniku mam xgamma.
Prectu a, stav po kroku je nasledujici:
(p, u, betagamma), tedy presel jsem do noveho stavu p, ze vstupu mi zbylo slovo u (acko jsem totiz precetl) a na zasobnik jsem pridal nejake nove bettagamma
Jazyk prijimany koncovym stavem
Je to takovy jazyk, ktery po prubehu zas. automatem nenecha na vstupou zadne neprectene slovo, tedy kazde slovo z tohoto jazyka skonci v nejakem koncovem stavu automatu a na vstupu je prazdne slovo:
L(A) = {u | (q0, u, z0) |-* (p, e, gamma), p lezi v F}
Tedy je to mnozina takovych slov, ktere kdyz zacnou v poc. stavu zas. automatu, skonci v nejakem koncovem stavu PLNE PRECTENE.
Nezajima me, co je na zasobniku, muze byt prazdny nebo tam neco je.
Jazyk prijimany prazdnym zasobnikem
Je to takovy jazyk, ktery po prubehu zas. atomatem nemusi skoncit v koncovem stavu, ale cele slovo je precteno a zasobnik je prazdny:
N(A) = {u | (q0, u, z0) |-* (p, e, e), p lezi v Q}
Tedy je to mnozina takovych slov, ktera se cela prectou zas. automatem a v ten moment se vyprazdni zasobnik. Nemusi skoncit v koncovem stavu.
Obecne je to podmnozina jazyka prijimaneho koncovym stavem, protoze z nej umime vyrobit automat prijimacici prazdnym zasobnikem, ale ne naopak.
Kdy je slovo prijato ZA? Rozdil mezi kocnovym stavem/prazdnym zasobnikem
Slovo je prijato p.t.k je cele precteno, tedy na konci mam situaci:
(p, e, neco), p je koncovy stav - slovo prijato koncovym stavem
NEBO
(p, e, e), p nemusi byt koncovy stav - slovo prijato prazd. zasobnikem
Pokud jsem v koncovem stavu, ale neprecetl jsem cele slovo, nebo mi dosel zasobnik driv, nez jsem precetl cele slovo - slovo je neprijato
Ke kazdemu automatu, ktery prijima prazdnym zasobnikem, existuje automat, co to slovo prijme…
Koncovym stavem a naopak
Tedy pro zas. automaty A a B
N(A) = L(B),
L(A) = N(B)
Ke kazde bezkontextove gramatice existuje zas. automat, takovy, ze…
Prijme jazyk generovany gramatikou koncovym stavem,
tedy
L(G) = L(A)
PRIKLAD:
Pro jazyk L={a^ib^ic^(i+j)} zkonstruujte ZA
- Zpusob - pres gramatiku, ktera generuje L, je to ale horsi a slozitejsi zpusob, protoze musim nejdriv vyvmslet gramatiku, pak dokazat, ze je spravna (2 kroky) a pak az pres odvozovani prechodne funkce….
- Lepsi zpusob - hned to zakresluju do automatu.
Tedy chci nejdriv i-krat acko, pak j-krat becko, pak i+j-krat cecko:
tzn z pocatecniho stavu dokud ctu acko - pridavam na zasobnik X, dokud ctu becko - pridavam na zasobnik X, dokud ctu cecko - odebiram ze zasobniku X, na konci prectu posledni C a vyprazdnim zasobnik. Tedy:
q0 -> a, Z0/XZ0 -> q1 //pokud ve q0 ctu (a, Z0), kde a je symbol, Z0 je pocatek zasobniku, tak prejdu do q1, smazu a, na zasobnik vlozim X.
q1 -> a,X/XX -> q1 //dokud ctu acko tak pridavam na zasobnik X
q1 -> b,X/XX -> q2 //precteno prvni becko, prejdu do dalsiho stavu
q2 -> b,X/XX -> q2 //dokud ctu becko tak pridavam na zasobnik X
q2 -> c,X/e ->q3 //precteno prvni cecko, prejdu dal a smazu prvni X ze zasobniku
q3 -> c,X/e //dokud ctu cecko tak mazu X
q3 -> e,Z0/e //pokud uz nemam co cist a jsem na konci zasobniku, vymaz ho.
Skoncim tedy ve stavu (q3, e, e,) a jazyk je prijaty koncovym stavem a prazdnym zasobnikem.
Priklad behu nad slovem (abcc)
(q0, abcc, Z0) |- (q0, bcc, XZ0) |- (q0, cc, XXZ0) |- (q0, c, XZ0) |- (q0, e, Z0) |- (q0, e, e) - hotovo
Deterministicky ZA, definice
Splnuje dve podminky:
1. Pro nejakou situaci (q, a, X) existuje nejvyse jedna instrukce, kam se posunout. Tedy nejde mit (q, a, X) |- (p1, neco, neco) NEBO (p2, neco, neco), musi byt pouze jedna varianta prechodu nebo zadna
2. Jestlize je mozne provest e-prechod, tak s tim zaroven neni mozne nacist symbol ze vstupu, tedy e-prechod pouze ovlivnuje zasobnik, ale ne vstup.
Deterministicky jazyk, definice
Jazyk je deterministicky p.t.k je prijiman deterministickym zas. automatem koncovym stavem
Bezprefixovy jazyk, definice
Jazyk je bezprefixovy p.t.k. je prijiman deterministickym zas. automatem prazdnym zasobnikem
Leva rekurze, analyza shora, greibachova normalni forma, turingovy stroje
?TODO?
