Základy matematiky a statistiky
pro humanitní obory
I
Pavel Rychlý Vojtěch Kovář
Fakulta informatiky, Masarykova univerzita
Botanická 68a, 602 00 Brno, Czech Republic
{pary, xkovar3}@fi.muni.cz
část 7
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 1 / 13
Obsah přednášky
Obsah přednášky
Formální lingvistika
Formální gramatika
Konečný automat
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 2 / 13
Formální lingvistika Formální lingvistika
Formální lingvistika
Matematické modely jazyka
jazyk = množina slov nad nějakou abecedou
prvky abecedy mohou být znaky, slova, ...
původně navrženy k popisu přirozených jazyků
dnes rozlišujeme tzv. formální jazyky
Cíl přednášky
seznámit se se základními konstrukcemi teorie formálních
jazyků
→ schopnost používat je v dalších kurzech
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 3 / 13
Formální lingvistika Základní pojmy
Formální lingvistika – základní pojmy
abeceda
množina symbolů Σ (např. {a, b})
slovo
libovolná konečná posloupnoust prvků Σ
např. aabab
délka slova |v|
počet prvků této posloupnosti
např. |aabab| = 5
prázdné slovo
slovo nulové délky
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 4 / 13
Formální lingvistika Základní pojmy
Formální lingvistika – základní pojmy (II)
množina Σ∗
množina všech slov nad abecedou Σ
např. {a, b}∗ = { , a, b, aa, bb, ab, ba, aab, abb, ...}
operace zřetězení slov „.”
pro slova u, v: u.v = uv
např. aab.ab = aabab
mocnina slova ui
definována induktivně: u0 = ; ui+1 = u.ui
např. (ab)3 = ababab
Jazyk
množina (některých) slov nad danou abecedou
pro každý jazyk L platí L ⊆ Σ∗
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 5 / 13
Formální lingvistika Základní pojmy
Formální lingvistika – základní pojmy (III)
zřetězení jazyků
L1.L2 = {u.v | u ∈ L1 ∧ v ∈ L2}
podobně i další operace nad jazyky
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 6 / 13
Formální gramatika Formální gramatika
Formální gramatika
Čtveřice (N, Σ, P, S)
N – množina neterminálů
Σ – množina terminálů (symbolů abecedy)
→ N ∩ Σ = ∅
→ N ∪ Σ označíme V (množina symbolů)
P ⊆ (V ∗.N.V ∗)x(V ∗) – množina pravidel
S – počáteční symbol gramatiky
Pravidla gramatiky
(α, β) zapisujeme jako α → β
α, β jsou slova nad V (řetězce terminálů a neterminálů)
kde α obsahuje alespoň jeden neterminál
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 7 / 13
Formální gramatika Odvození z gramatiky
Odvození z gramatiky
Gramatika je model, který generuje jazyk
začneme počátečním neterminálem
používáme pravidla gramatiky jako přepisovací systém
→ tj. levou stranu pravidla nahradíme pravou
přepisujeme tak dlouho, dokud nedostaneme řetězec terminálů
Vztah jazyka a gramatiky
gramatika G generuje jazyk L, pokud existuje odvození
každého slova jazyka L z gramatiky G
značíme L(G)
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 8 / 13
Formální gramatika Odvození z gramatiky
Odvození z gramatiky – příklad
Gramatika
Σ = {a, b}, N = {S, A}
P = { S → A, A → AA, A → a }
Příklady odvození
S ⇒ A ⇒ a
S ⇒ A ⇒ AA ⇒ aA ⇒ aAA ⇒ aaA ⇒ aaa
kolik slov obsahuje jazyk generovaný touto gramatikou?
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 9 / 13
Formální gramatika Chomského hierarchie gramatik
Chomského hierarchie gramatik
Typy gramatik podle omezení na pravidla
typ 0
žádná omezení
typ 1
pro každé pravidlo α → β je |α| ≤ |β|
též kontextová gramatika
typ 2
každé pravidlo je tvaru A → β (A ∈ N)
též bezkontextová gramatika
typ 3
každé pravidlo je tvaru A → aB (A, B ∈ N; a ∈ Σ)
též regulární gramatika
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 10 / 13
Konečný automat Konečný automat
Konečný automat
Jiný model charakterizující jazyky
Pětice (Q, Σ, δ, q0F)
Q – neprázdná konečná množina stavů
Σ – konečná množina vstupních symbolů (abeceda)
δ : QxΣ → Q – přechodová funkce
q0 – počáteční stav
F – množina koncových stavů
Automat necháváme běžet nad vstupním slovem
začneme v počátečním stavu
podle dalšího symbolu na vstupu a aktuálního stavu se
přesuneme do jiného stavu
opakujeme, dokud není slovo dočteno do konce
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 11 / 13
Konečný automat Konečný automat
Konečný automat
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 12 / 13
Konečný automat Automaty a jazyky
Automaty a jazyky
Automaty a jazyky
automat akceptuje slovo, pokud po jeho zpracování skončí v
akceptujícím stavu
automat akceptuje jazyk, pokud akceptuje právě slova jazyka
Automaty a gramatiky
pro každou regulární gramatiku G existuje automat, který
akceptuje jazyk L(G) (důkaz existuje :) )
platí i naopak → ekvivalentní formalismy
Co se nevešlo
existují i další typy automatů
některé ekvivalentní s jinými typy gramatik
např. zásobníkový automat, Turingův stroj
Pavel Rychlý, Vojtěch Kovář (FI MU Brno) PLIN004 část 7 13 / 13