Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 30. 11. 2010 Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat Obsah přednášky 1 Formální lingvistika 2 Formální gramatika 3 Konečný automat Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika 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 Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat Konečný automat Konečný automat Pavel Rychlý, Vojtěch Kovář FI MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika 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 Základy matematiky a statistiky pro humanitní obory I