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ý, Vojtech Kovář (Fl MU Brno) PLIN004 rast 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álni lingvistika Formálni lingvistika Formálni 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 prirazený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) PLIN0O4 Eáu 7 3/13 Formální lingvistika Základní pojmy Formální lingvistika - základní pojmy ► abeceda ► množina symbolů Y. (např. {a,b}) ► slovo ► libovolná konečná posloupnoust prvků Y. ► např. aabab ► délka slova v ► počet prvků této posloupnosti ► např. \aabab\ = 5 ► prázdné slovo e ► slovo nulové délky Pavel Rychíý, Vojtěch Kovář (Fl MU Brno) ľlll'' část 7 4/13 Formální lingvistika 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 u, v: u.v = uv ► např. aab.ab = aabab ► mocnina slova u' ► definována induktivně: u° = e; u'+1 = u.ď ► např. (ab)3 = ababab ► Jazyk ► množina (některých) slov nad danou abecedou ► pro každý jazyk L platí tCP Pavel Rychlý. Vojtěch Kovář (Fl MU Brno) PLIN004 ř^: 7 5/13 Formální lingvistika Základní pojmy Formální lingvistika - základní pojmy (III) ► zřetězení jazyků ► Li.L2 = {u-v 1 u e Z-i A v e L2} ► podobně i další operace nad jazyky Pavel Rychíý, Vojtěch Kovář (Fl MU Brno) ľl 1 1 , , část 7 6/13 Foti.i r- iy.ir-i.r.i'.., I.rnar ranďď.ď Formální gramatika ► Čtveřice (A/, Z, P, S) ► N - množina neterminálů ► Y. - množina terminálů (symbolů abecedy) ► -> wnz = 0 ► -> WUI označíme V (množina symbolů) ► PC (V.N.V')x(V') - množina pravidel ► S - počáteční symbol gramatiky ► Pravidla gramatiky ► (a, ff) zapisujeme jako a —> [i ► 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) PLIW004 čá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) P1IN004 fcast 7 S/13 Formální gramatika Odvození z gramatiky Odvození z gramatiky - příklad ► Gramatika ► Z = {a, b}, N = {S, A} ► P = { S -> A, A -> A4, -4 -> a } ► Příklady odvození ► S /4 ^ a ► S =^ ,4 =^ A4 =$> a,4 =$> aA4 =4> aa^ aaa ► kolik slov obsahuje jazyk generovaný touto gramatikou? Pavel Rychlý, Vojtěch Kovář (Fl MU Brno) ľlľľ'V čá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 —> fj je \a < \[í\ ► též kontextová gramatika ► typ 2 ► každé pravidlo je tvaru A ->• p (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,T,S,q0,F) ► 0 - neprázdná konečná množina stavů ► E - konečná množina vstupních symbolů (abeceda) ► S : QxY. —■> Q - přechodová funkce ► Po - 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) lili" část 7 11/13 Konečný automat Konečný automat Konečný automat b r i X 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á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ář (Fl MU Brno) PLINOW část 7 13/13