Please enable JavaScript.
Coggle requires JavaScript to display documents.
Formális nyelvek és automaták (Nyelvtan és nyelv (V+ (teljes nyelv), V*…
Formális nyelvek és automaták
Nyelvtan és nyelv
ábécé
üresszó
V+
teljes nyelv
V*
teljes nyelv + üresszó
konkatenáció
generatív nyelvtan
G = (N, T, S, H)
N - nemterminális betűk ábécéje
T - terminális betűk ábécéje
S - kezdőszimbólum
H - helyettesítési szabályok
nyelv
szavak halmaza
szó
Chomsky-féle nyelvosztályok
0 típusú - mondatszerkezetű
Turing-gép
1 típusú - környezetfüggő
αAβ → αγβ
A - nemterminális
α, β, γ - nemterminális vagy terminális
korlátos nemdeterminisztikus Turing-gép
2 típusú - környezetfüggetlen
A → α
A - nemterminális
α - nemterminális vagy terminális
nemdeterminisztikus veremautomata
3 típusú - reguláris
A → x vagy A → xB
A, B - nemterminális
x - terminális
véges automata
Normálformák
normális alak
A → α
reguláris
gyenge
erős
környezetfüggetlen
Chomsky-féle
Greibach-féle
környezetfüggő
Penttonen-féle
Révész-féle
Szintaktikus elemzés
CYK-féle algoritmus
Earley-féle algoritmus
Az automata fogalma, fajtái
determinisztikus véges
<Q, V, δ, q0, F>
V - bemenő ábécé
δ - állapotátmenet-függvény
q0 - kezdőállapot
F - végállapotok halmaza
Q - belső állapotok halmaza
nemdeterminisztikus véges
csak az állapotátmenet függvényben különbözik a determinisztikustól. QxV->2^Q
Automaták és nyelvek kapcsolata
nemdeterminisztikus
automatákkal felismerhető nyelvek osztálya megegyezik a
determinisztikus
automaták által felismerhető nyelvek osztályával
pumpálási lemma
van olyan környezetfüggetlen nyelv ami nem reguláris
Bar-Hillel lemma
van olyan környezetfüggő nyelv ami nem környezetfüggetlen
nemdeterminisztikus veremautomata
⟨Q, V, W, δ, q0, z0, F⟩
Q - állapotok
V - bemenő ábécé
W - veremábécé
δ - állapotátmenet függvény
q0 - kezdőállapot
z0 - kezdőjel
F - végállapotok
Turing-gép
reguláris
nyelvek osztálya = véges
automatákkal felismerhető
nyelvek osztálya
Véges automaták minimalizálása, analízise, szintézise