11. Formální jazyky
Chomského hierarchie
Konečné automaty
Nedeterminismus
Regulární jazyky
Determinizace
Uzávěrové vlastnosti regulárních jazyků
reprezentace
pojmy
slovo
jazyk nad abecedou
abeceda
kontextové gramatiky
bezkontextové gramatiky
frázové gramatiky
regulární gramatiky
generují regulární jazyky
generují bezkontextové jazyky
generují kontextové jazyky
generují všechny formální jazyky
pravidla: A -> aB | A -> a
pravo/levo lineární - nelze kombinovat, jsou ekvivalentní
S -> e (pokud S na pravé straně žádného pravidla) - ex. alg. převodu
generované kon. automatem
S -> e (pokud S na pravé straně žádného pravidla) - ex. alg. převodu
pravidla: A -> γ (γ - neprázdný řetězec net. a term.)
rozpoznatelné nedeterm. zásobníkovým automatem
S -> e (pokud S na pravé straně žádného pravidla)
pravidla: αA -> γ (α může být prázdné)
jazyky rozpoznatelné lineárně ohran. TM
pravidla: žádná omezení
kazyky rozpoznatelné TM
jazyk je regulární, právě když (alespoň 1)
popsán regulárním výrazem
akceptován determ. kon. automatem
generován regulární gram.
akceptovaný nedeterm. kon. automatem
regulární gramatika
čtveřice (N, ∑, P, S)
∑ - kon. množ. terminálů (N ∩ ∑ = nic; N U ∑ = V)
P - kon. množ. pravidel (⊆ VNV x V*)
N - nepr. kon. množ. neterminálů
S ∈ N - poč. neterminál
pravidla: A -> aB | A -> a
pravolineární (aB), levolineární (Ba)
pumping lemma
generují reg. jazyky
regulární výrazy RE(∑)
Kl. věta: lib. jazyk je popsatelný reg. výrazem, pokud je rozpoznatelný kon. automatem
množina RE nad ∑
řetězec popisující množ. řetězců
- e, nic a a pro každé a ∈ ∑ jsou reg. výrazy nad ∑
- jsou-li E, F reg. výrazy nad ∑, E.F, E+F, E* jsou také reg. výrazy nad ∑
- každý reg. výraz vznikne po konečném počtu 1 a 2
použití: důkaz, že jazyk není regulární - nutní (ale nepostačující) podmínka regularity - obměna
obměna: pro lib. n z N, dále pevné, existuje lib. w z L, |w| >= n: při lib. rozdělení slova w, s = xyz, |xy| <= n a y není e, existuje min 1 i z N0: xy^iz není z L --> L není regulární
každé slovo může být rozděleno na části - zopakování - opět slovo z daného jazyka
každý jazyk z dané třídy může být napumpován
třída jazyků je uzavřena na operaci o, pokud pro lib. jazyky patřící do třídy platí, že o(jazyky) patří do třídy
výsledek operace nad lib. prvky opět náleží do množiny
uzavřená na
průnik
komplement
sjednocení
rozdíl
zřetězení
iterace
pozitivní iterace
zrcadlový obraz
FA
generují reg. gramatiky
výpočetní model prim. PC, z několika stavů (konečné množ.), přechodů, dokáže přijmout/zamítnout slovo
obsahuje
konečně stavovou řídící jednotku - paměť
čtecí hlava
páska - zapsané vstupní slovo
průběh výpočtu
automat na základě přečteného symbolu a akt. stavu stav změní a posune čtecí hlavu o 1 políčko vpravo
konec výpočtu: zablokuje/přečte slovo
začátek: hlava na nejlevějším políčku pásky
slovo akceptováno - přečteno + stav je koncový
množina všech akceptovaných slov = regulární jazyk
DFA
L(M) přijímaný kon. automatem M
regulární jazyk = rozpoznatelný kon. automatem
pětice (Q, ∑, δ, q0, F)
∑ - kon. množ. vstupních symbolů, abeceda
δ - Q x ∑ -> Q (NFA: 2^Q) parc. přechodová fce
Q - neprázdná kon. množ. stavů
q0 z Q - počáteční stav
F - podmnožina Q, množ. koncových stavů
tvořen právě všemi slovy, pod kterými automat přejde z poč. stavu do některého z koncových
ekvivalentní automaty, pokud L(M1) = L(M2)
reprezentace - uspořádaná pětice, tabulka, přechodový graf, výpočetní strom
Varianty konečných automatů
s e-kroky
deterministický
nedeterministický
totální
více následujících stavů
δ: Q x ∑ -> 2^Q
může změnit stav bez přečtení vstupního symbolu
následující stav určen jednoznačně
δ: Q x ∑ -> Q
deterministický s totální přechodovou fcí
definované přechody ze všech stavů pro všechny symboly vstupní abecedy
vytvoří se nový stav - míří do něj chybějící přechody + cyklí
následující stav nemusí být jednoznačný
lehčí navrhnout NFA
ke každému NFA existuje DFA - algoritmus
NFA: pětice, složky stejné krom přechodové fce
DFA - speciální NFA
není předem jasné, do jakého stavu se po zoracování slova dostane
slovo akceptováno - pokud alespoň 1 z výpočtů skončí v koncovém stavu
NFA -> DFA
vstup: NFA
výstup: ekvivalentní DFA bez nedosažitelných stavů s tpf
postup
doplníme původní stavy
koncové - alespoň 1 původní koncový
slučuji <stavy>, postupně po řádcích
kanonizace
pro každou množ. přechodů pod konkr. písmenem - nový stav
začnu v prvním
postupně přejmenujeme všechny přechody
převody
reg. gramatika -> FA
FA -> reg. gramatika
k dané reg. gramatice lze sestrojit kon. automat a naopak
třídy rozpoznatelných/generovaných jazyků jsou si rovny
ke každé reg. gramatice existuje NFA, L(G) = L(M)
pro každý FA existuje reg. gramatika, L(M) = L(G)
typy jazyků
operace nad slovy
operace nad jazyky
mocnina
zrcadlový obraz
zřetězení
iterace
poz. iterace
mocnina
doplněk
zrcadlový obraz
zřetězení
U, průnik, -
rozhodnutelné problémy pro třídy reg. jazyků
příslušnost slova k jazyku
prázdnost jazyka
inkluze jazyků
univerzalita jazyka
ekvivalence jazyků
knečnost jazyka
každý reg. výraz E nad abecedou jednoznačně určuje jazyk L(E) - pravidla
regulární přechodový graf
pětice (Q, ∑, δ, I, F)
slovo je automatem
jazyk je automatem
akceptování
zamítnuto
přijímaný (rozpoznatelný, akcept.)
δ: Q x (∑ U {e}) -> 2^Q
De - epsilon okolí - kam se dostanu jen přes e kroky
synchronní paralelní kompozice
sestrojení průniku, sjednocení, rozdílu automatů
tpf
automat pro komplement
nutná tpf
minimalizace
minimální FA
postup
- ztotožnění ekvivalentních stavů
- odstranění nedos. stavů
tabulka
ztotálním
I - ven, II - ostatní
pokračujeme
nakonci zapíšu jen názvy tříd
využití FA: lexikální analýza