Základy matematiky a statistiky pro humanitní obory 1 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ář (Fl 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ář (Fl 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álni 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ář (Fl MU Brno) PLIN004 část 7 3/13 Formální lingvistika Základní pojmy Formální lingvistika - základní pojmy ► abeceda ► množina symbolů Z (např. {a, £>}) ► 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 Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 7 4/13 Formální lingvistika Základní pojmy Formální lingvistika - základní pojmy (II) ► množina T.* ► množina všech slov nad abecedou Z ► např. {a, £>}* = {e, 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 u' ► definována induktivně: u° = e; ul+1 = u.u' ► např. (ab)3 = ababab ► Jazyk ► množina (některých) slov nad danou abecedou ► pro každý jazyk L platí Í.CI* Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 7 5/13 Formální lingvistika Základní pojmy Formální lingvistika - základní pojmy (III) ► zřetězení jazyků ► L\±2 = {u.v \ u € Li A v € L2} ► podobně i další operace nad jazyky Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 7 6/13 Formální gramatika Formální gramatika Formální gramatika ► Čtveřice (N,T, P, S) ► N - množina neterminálů ► T. - množina terminálů (symbolů abecedy) ► ->■ A/ni = 0 ► —> N U T. 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, j3 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) 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ář (Fl MU Brno) PLIN004 čásL 7 8/13 Formální gramatika Odvození z gramatiky Odvození z gramatiky - příklad ► Gramatika ► T = {a,b},N = {S,A} ► P = { S ->• A AA, A-> a } ► Příklady odvození ► S => A => a ► S => ,4 => A4 3/4 3/4/4 =^> 33/4 =4> 333 ► kolik slov obsahuje jazyk generovaný touto gramatikou? Pavel Rychlý, Vojtěch Kovář (Fl 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 a —)■ /3 je |a| < |/3| ► též kontextová gramatika ► typ 2 ► každé pravidlo je tvaru A ->• /3 (A e N) ► též bezkontextová gramatika ► typ 3 ► každé pravidlo je tvaru A —> aB nebo A —> a (A, B e N; a (E T) ► též regulární gramatika Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) PLIN004 část 7 10/13 Konečný automat Konečný automat Konečný automat ► Jiný model charakterizující jazyky ► Pětice (Q,H,S,q0,F) ► Q - neprázdná konečná množina stavů ► T. — konečná množina vstupních symbolů (abeceda) ► ô : QxH —> Q - přechodová funkce ► go _ 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ář (Fl MU Brno) PLIN004 část 7 11/13 Konečný automat Konečný automat Konečný automat b ( \ 1 J a Pavel Rychlý, Vojtěch Kovář (Fl 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árni 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ář (Fl MU Brno) PLIN004 část 7 13/13