Automaty a formální jazyky
Přednáška IV.
Gramatiky
Gramatiky - motivace
• Sada pravidel pro vytváření slov (řetězců), jež
patří do daného jazyka.
• Původně: přirozené jazyky
• Formalizováno pro studium přirozených jazyků
a popis jazyků umělých
• V IT: popis programovacích jazyků (C, Java, …)
Jak to vypadá?
• Definujeme sadu pravidel pro generování jazyka
• Vycházíme z počátečního symbolu a ten postupně
rozvíjíme
• Končíme, když celý řetězec obsahuje znaky z
abecedy
Neformální příklad – zápis matematického výrazu:
V: A * B
A: celé číslo
B: celé číslo
Produkční (přepisovací) systém
• Produkční systém R je dvojice (V, P) kde
– V je konečná abeceda
– P je konečná množina produkčních (přepisovacích) pravidel
– Pravidlo je uspořádaná dvojice (u,v), kde u,v ∈ V*,
zapisujeme zpravidla u → v
• Příklad:
V = {0,1,P}
P → 0P0
P → 1
Opakovaným používáním přepisovacích pravidel získáváme
jazyk, jenž obsahuje řetězce:
010 00100 0001000 0P0 00P00
Přímé a nepřímé přepsání
• Definice: Slovo u se přímo přepisuje na slovo v, pokud
existují taková slova u,v,w,x,y,z∈ V*, pro která platí:
v = xyz, u = xwz, y → w je přepisovací pravidlo.
• Definice: Slovo u se přepíše na v, pokud existují slova
u1, u2,…, un ∈ V* takové, že
u → u1 → u2 → … → un → v
Značíme u →* v
• Posloupnost u1, u2,…, un nazýváme odvozením
(derivací)
• Minimální derivace je taková derivace, kde žádné dva
prvky nejsou shodné.
Generativní gramatika - formálně
• Definice: Generativní gramatika je
uspořádaná čtveřice G = (∏, ∑, S, P) kde:
– ∏ je konečná množina (neterminály)
– ∑ je konečná množina (terminály)
– S ∈∏ je počáteční symbol
– P je množina produkčních pravidel u → v:
u, v ∈ (∑∏)*
řetězec u obsahuje alespoň jeden neterminální
symbol.
Co to znamená?
• Terminály = tvořeny z „cílové“ abecedy, přepisování zde
končí
• Neterminály = pomocné symboly pro sestavení odvození
• Příklad: Jazyk obsahuje kombinace nul a jedniček, slovo
nezačíná nulou.
∑ = {0,1} , ∏ = {A,B,C}, poč. symbol A
Produkční pravidla:
A → BC
B → 0
C → C
C → 1
C → 0
Domluva pro zápis
• Neterminály:
– Velká písmena v jednodušším zápisu
– Uzavřeno do závorek <>, použijeme-li slovo, abychom
zápisu rozuměli: <číslo>
• Terminály jsou prvky abecedy, která tvoří
generovaný jazyk, zde žádná dohoda nemůže být.
• Přepisovací pravidla se stejnou levou stranou se
slučují s pomocí symbolu |:
A → BC
B → 0 | 1 | C
Gramatika a jazyk
• Definice: Jazyk L(G) je generován gramatikou
G právě tehdy, když všechna slova jazyka lze
odvodit z počátečního symbolu gramatiky.
L(G) = {w; w ∈ ∑*, S →*w}
• Definice: Gramatiky G1 a G2 jsou si
ekvivalentní právě tehdy, když L(G1) = L(G2).
Chomského hierarchie
• Rozdělení gramatik do 4 skupin podle jejich
vlastností (záleží na tvaru produkčních pravidel).
• Třída 0: Gramatiky typu 0 mají obecná produkční
pravidla.
• Třída 1: Gramatiky typu 1 – kontextové jazyky
mají produkční pravidla ve tvaru
1. αXβ→ αYβ
kde X∈∏, α,β∈(∏∑)*, Y∈(∏∑)+
1. Smí obsahovat pravidlo tvaru S → ε; ale S se pak
nesmí vyskytovat na pravé straně žádného pravidla.
Chomského hierarchie II.
• Třída 2: Gramatiky typu 2 – bezkontextové
jazyky mají produkční pravidla pouze ve tvaru
X → w, kde X ∈ ∏, w ∈ (∏ ∑)*
• Třída 3: Gramatiky typu 3 – regulární jazyky
mají pouze pravidla ve tvaru:
X → wY, X → w, kde kde X,Y ∈ ∏, w ∈ ∑*
Vztah mezi třídami CH. H.
• Věta:
L(G0) ⊃ L(G1) ⊃ L(G2) ⊃ L(G3)
(Indexy u gramatik označují třídu jednotlivých
gramatik v Chomského hierarchii.)