FORMÁLNÍ LINGVISTIKA



ZÁKLADNÍ POJMY
Abeceda je konečná množina symbolů. Např. {𝑎, 𝑏}.
Slovo je libovolná konečná posloupnost prvků Σ, např. 𝑎𝑎𝑏𝑎𝑏.
Délka slova je velikost této posloupnosti, např. |𝑎𝑎𝑏𝑎𝑏| = 5.
Prázdné slovo je slovo nulové délky, značíme je 𝜖.

ZÁKLADNÍ POJMY
Σ* je množina všech slov nad abecedou Σ, např. {𝑎, 𝑏}* = {𝜖, 𝑎, 𝑏, 𝑎𝑎, 𝑏𝑏, 𝑎𝑏, 𝑏𝑎, 𝑎𝑎𝑏, 𝑎𝑏𝑏, ...}.
Operace zřetězení slov, značíme tečkou (.), je pro dvě slova 𝑢 a 𝑣 definována jako 𝑢 . 𝑣 = 𝑢𝑣,
např. 𝑎𝑎𝑏 . 𝑎𝑏 = 𝑎𝑎𝑏𝑎𝑏.
Mocnina slova je pro slovo 𝑢 a přirozené číslo 𝑖 značena 𝑢𝑖 a je definována induktivně: 𝑢0 = 𝜖,
𝑢𝑖+1 = 𝑢.𝑢𝑖 Např. (𝑎𝑏)3 = 𝑎𝑏𝑎𝑏𝑎𝑏.
Jazyk je množina některých slov nad danou abecedou, tedy pro každý jazyk 𝐿 platí 𝐿 ⊆ Σ*

FORMÁLNÍ GRAMATIKA
Formální gramatika přepisovací systém, jímž lze vygenerovat slova jazyka.
Formálně, gramatika je čtveřice (𝑁,Σ, 𝑃, 𝑆), kde:
𝑁 je množina neterminálů (značíme nejčastěji velkými písmeny)
Σ je množina terminálů (symbolů abecedy, značíme malými písmeny), je disjunktní s množinou 𝑁 a 𝑁 ∪
Σ označujeme jako 𝑉 (množina všech symbolů)
𝑃 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.
𝑆 je počáteční symbol gramatiky

GRAMATIKA
Pravidla gramatiky jako dvojice řetězců (slov nad množinou 𝑉 )   (𝛼, 𝛽) zapisujeme jako 𝛼 → 𝛽. 𝛼
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 𝑆 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 Σ).
Tomuto procesu říkáme odvození slova z gramatiky.

GRAMATIKA
Řekneme, že gramatika 𝐺 generuje jazyk 𝐿, pokud existuje odvození každého slova jazyka 𝐿 z
gramatiky 𝐺. Jazyk generovaný gramatikou 𝐺 značíme většinou 𝐿(𝐺).
Příklad!
Mějme gramatiku (𝑁,Σ, 𝑃, 𝑆), kde
Σ = {𝑎, 𝑏}
𝑁 = {𝑆,𝐴}
𝑃 = { 𝑆 → 𝐴, 𝐴 → 𝐴𝐴, 𝐴 → 𝑎 }
𝑆 ⇒ 𝐴 ⇒ 𝑎
𝑆 ⇒ 𝐴 ⇒ 𝐴𝐴 ⇒ 𝑎𝐴 ⇒ 𝑎𝐴𝐴 ⇒ 𝑎𝑎𝐴 ⇒ 𝑎𝑎𝑎

CHOMSKÉHO HIERARCHIE 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 𝛼 → 𝛽 podmínku |𝛼| ≤ |𝛽|,
tedy levá strana každého pravidla musí být kratší než jeho pravá strana. Výjimkou z tohoto
omezení je pravidlo 𝑆 → 𝜖, které může být přítomno.
Gramatika typu 2 neboli bezkontextová gramatika má všechna pravidla ve tvaru 𝐴 → 𝛽 (tak, že 𝐴 ∈ 𝑁),
tedy na levé straně je vždy právě jeden neterminál a 𝛽 je neprázdné. Výjimkou z tohoto omezení je
pravidlo 𝑆 → 𝜖, které může být přítomno.
Gramatika typu 3 neboli regulární gramatika má všechna pravidla ve tvaru 𝐴 → 𝑎𝐵 nebo 𝐴 → 𝑎, kde 𝐴,𝐵
jsou neterminály a 𝑎 je terminál. Výjimkou z tohoto omezení je pravidlo 𝑆 → 𝜖, které může být
přítomno.