Please enable JavaScript.
Coggle requires JavaScript to display documents.
11. Formální jazyky (Konečné automaty (Nedeterminismus (následující stav…
11. Formální jazyky
Chomského hierarchie
-
-
-
regulární gramatiky
-
-
pravo/levo lineární - nelze kombinovat, jsou ekvivalentní
-
-
Konečné automaty
Nedeterminismus
-
-
-
NFA: pětice, složky stejné krom přechodové fce
-
Determinizace
-
-
-
postup
-
-
slučuji <stavy>, postupně po řádcích
-
-
FA
-
výpočetní model prim. PC, z několika stavů (konečné množ.), přechodů, dokáže přijmout/zamítnout 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
-
-
DFA
pětice (Q, ∑, δ, q0, F)
∑ - kon. množ. vstupních symbolů, abeceda
-
-
-
F - podmnožina Q, množ. koncových stavů
-
-
ekvivalentní automaty, pokud L(M1) = L(M2)
reprezentace - uspořádaná pětice, tabulka, přechodový graf, výpočetní strom
-
převody
reg. gramatika -> FA
ke každé reg. gramatice existuje NFA, L(G) = L(M)
FA -> reg. gramatika
pro každý FA existuje reg. gramatika, L(M) = L(G)
-
-
-
-
minimalizace
-
postup
- ztotožnění ekvivalentních stavů
-
-
-
-
Regulární jazyky
-
reprezentace
regulární gramatika
-
-
pravolineární (aB), levolineární (Ba)
-
regulární výrazy RE(∑)
Kl. věta: lib. jazyk je popsatelný reg. výrazem, pokud je rozpoznatelný kon. automatem
množina RE nad ∑
- 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
-
-
-
jazyk je regulární, právě když (alespoň 1)
-
-
-
-
pumping lemma
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í
-
-
-
pojmy
-
-
-
-
-
-
-
jazyk je automatem
přijímaný (rozpoznatelný, akcept.)
-