FORMÁLNI
LINGVISTIKA
ZÁKLADNÍ P O J M Y
Abeceda je konečná množina symbolů. Např. {a, b}.
Slovo je libovolná konečná posloupnost prvků I, např. aabab.
Délka slova je velikost této posloupnosti, např. \aabab\ = 5.
Prázdné slovo je slovo nulové délky, značíme je e.
ZÁKLADNÍ P O J M Y
I* je množina všech slov nad abecedou I, např. {a, b}* = {e, a, b,
aa, bb, ab, ba, aab, abb, ...}.
Operace zřetězení slov, značíme tečkou (.), je pro dvě slova u a v
definována jako u . v - uv, např. aab . ab - aabab.
Mocnina slova je pro slovo u a přirozené číslo i značena ui a je
definována induktivně: uO = e, = u.ui Např. (ab)3 = ababab.
Jazyk je množina některých slov nad danou abecedou, tedy pro
každý jazyk L platí L Q I*
FORMÁLNÍ
G R A M A T I K A
Formální gramatika přepisovací systém, jímž lze vygenerovat
slova jazyka.
Formálně, gramatika je čtveřice (Af,I, P, 5), kde:
N je množina neterminálů (značíme nejčastěji velkými písmeny)
I je množina terminálů (symbolů abecedy, značíme malými
písmeny), je disjunktní s množinou N a N u I označujeme jako V
(množina všech symbolů)
P je množina pravidel, tj. množina dvojic, kde prvním prvkem je
řetězec obsahující alespoň jeden neterminál a druhým prvkem je
libovolný řetězec.
S je počáteční symbol gramatiky
G R A M A T I K A
Pravidla gramatiky jako dvojice řetězců (slov nad množinou V) (
a, /?) zapisujeme jako a —• /?. a nazýváme levou stranou pravidla
a musí obsahovat alespoň jeden neterminál. /? nazýváme pravou
stranou pravidla.
Gramatika je modelem, kterým lze generovat slova jazyka:
začneme z počátečního symbolu gramatiky S a pravidla gramatiky
používáme jako přepisovací systém, to znamená, že v jednom
kroku přepisu můžeme nahradit některý řetězec terminálů a
neterminálů, který je současně na levé straně nějakého pravidla,
pravou stranou tohoto pravidla. Tento postup opakujeme, dokud
nedostaneme řetězec terminálních symbolů (čili slovo nad I).
Tomuto procesu říkáme odvození slova z gramatiky.
G R A M A T I K A
Řekneme, že gramatika G generuje jazyk L, pokud existuje odvození
každého slova jazyka L z gramatiky G. Jazyk generovaný gramatikou
G značíme většinou L(G).
Príklad!
Mějme gramatiku (]V,I, P, S), kde
Z = {a, b}
N = {S,A}
P = { S ^ A, A ^ AA, A ^ a}
S ^ A^> a
CHOMSKÉHO
H I E R A R C H I E JAZYKŮ
Gramatika typu 0 neklade žádná omezení na množinu pravidel, libovolná
gramatika je gramatikou typu 0.
Gramatika typu 1 neboli kontextová gramatika klade na všechna pravidla a
/? podmínku \a\ ^ |/?|, tedy levá strana každého pravidla musí být kratší než
jeho pravá strana. Výjimkou z tohoto omezení je pravidlo S —• e, které může
být přítomno.
Gramatika typu 2 neboli bezkontextová gramatika má všechna pravidla ve
tvaru A —• /? (tak, že A e N), tedy na levé straně je vždy právě jeden
neterminál a /? je neprázdné. Výjimkou z tohoto omezení je pravidlo S —• e,
které může být přítomno.
Gramatika typu 3 neboli regulární gramatika má všechna pravidla ve tvaru A
—• aB nebo A^ a, kde A,B jsou neterminály a a je terminál. Výjimkou z
tohoto omezení je pravidlo S —• e, které může být přítomno.