Obsah přednášky Formální lingvistika Formální gramatika Konečný automat O oooo OOOO ooo Základy matematiky a statistiky pro humanitní obory 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ář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Formální lingvistika oooo Obsah přednášky Formální gramatika OOOO Konečný automat ooo Q Formální lingvistika B Formální gramatika H Konečný automat Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Formální lingvistika Formální gramatika Konečný automat O »000 oooo ooo 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 Obsah přednášky Formální lingvistika Formální gramatika Konečný automat o omoo oooo ooo Základní pojmy Formální lingvistika - základní pojmy abeceda množina symbolů Z (např. {a, b}) slovo ■ libovolná konečná posloupnoust prvků Z ■ např. aabab délka slova \v\ ■ počet prvků této posloupnosti ■ např. \aabab\ = 5 prázdné slovo e ■ slovo nulové délky □ S1 Obsah přednášky Formální lingvistika Formální gramatika Konečný automat o oo«o oooo ooo Základní pojmy Formální lingvistika - základní pojmy (II) množina Z* ■ množina všech slov nad abecedou Z ■ např. {a, b}* = {e, a, b, aa, bb, ab, ba, aab, abb,.. operace zřetězení slov ■ pro slova v: u.v — uv ■ např. aab.ab = aabab mocnina slova u1 ■ definována induktivně: u° = e; = l/.l/' ■ např. (ab)3 = ababab Jazyk ■ množina (některých) slov nad danou abecedou ■ pro každý jazyk L platí [Cl* } Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Formální lingvistika Formální gramatika Konečný automat o ooo» oooo ooo Základní pojmy Formální lingvistika - základní pojmy (III) zřetězení jazyků ■ L1.L2 = {u.v | u G Li A v G L2} podobně i další operace nad jazyky Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Formální lingvistika Formální gramatika Konečný automat O OOOO »000 ooo Formální gramatika Formální gramatika ■ Čtveřice (A/,E,P,S) ■ N - množina neterminálů ■ Z - množina terminálů (symbolů abecedy) ■ -> A/nl = 0 ■ —> N U Z označíme V (množina symbolů) ■ PC (V*.N.V*)x(V*) - množina pravidel ■ S - počáteční symbol gramatiky ■ Pravidla gramatiky ■ (a, /3) zapisujeme jako a —> (3 ■ a, /3 jsou slova nad V (řetězce terminálů a neterminálů) ■ kde a obsahuje alespoň jeden neterminál Pavel Rychlý, Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat o oooo o»oo ooo 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ře p i sova c í 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ář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Formální lingvistika Formální gramatika Konečný automat O OOOO 0090 ooo Odvození z gramatiky Odvození z gramatiky - příklad ■ Gramatika . Z = {a,b},A/ = {S,/\} ■ 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? = >T) Q rv Pavel Rychlý, Vojtěch Kovář Fl MU Brno Základy matematiky a statistiky pro humanitní obory I Obsah přednášky Formální lingvistika Formální gramatika Konečný automat O OOOO 0009 ooo Chomského hierarchie gramatik Chomského hierarchie gramatik Typy gramatik podle omezení na pravidla typ 0 ■ žádná omezení typ 1 typ 2 typ 3 pro každé pravidlo a —> (3 je též kontextová gramatika každé pravidlo je tvaru A—> (3 (A e N) též bezkontextová gramatika každé pravidlo je tvaru A —>> aB nebo A —>> a (A, B e N; a G Z) též regulární gramatika Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky O Konečný automat Formálni lingvistika oooo Formálni gramatika OOOO Konečný automat •oo Konečný automat Jiný model charakterizující jazyky Pětice (Q,Z,S,q0,F) m Q - neprázdna konečná množina stavů ■ Z - konečná množina vstupních symbolů (abeceda) ■ S : QxZ —>> Q - přechodová funkce ■ qo - 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ář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky O Konečný automat Formálni lingvistika oooo Formálni gramatika OOOO Konečný automat o«o Konečný automat a h a h a Pavel Rychlý, Vojtěch Kovář Základy matematiky a statistiky pro humanitní obory I :l MU Brno Obsah přednášky Formální lingvistika Formální gramatika Konečný automat o oooo oooo oom Automaty a jazyky Automaty a jazyky Automaty a jazyky ■ automat akceptuje slovo, pokud po jeho zpracování skončiv 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ář Základy matematiky a statistiky pro humanitní obory I :l MU Brno