Formální jazyk abeceda - slovo - jazyk Abeceda je libovolná konečná množina. Prvky abecedy nazýváme znaky / písmena / symboly. IB102 Automaty a gramatiky, 16.9.2019 1/26 Slovo (řetězec) nad abecedou Z je libovolná konečná posloupnost znaků této abecedy. Prázdné posloupnosti znaků odpovídá prázdné slovo, označované e, Počet členů posloupnosti v značíme \ v\ a nazýváme délkou slova. Počet výskytů znaku a ve slově v značíme #a(v). IB102 Automaty a gramatiky, 16.9.2019 2/26 Jazyk nad abecedou Z je libovolná množina slov nad Z. Množinu všech slov nad abecedou Z značíme Z*, množinu všech neprázdných slov Z+. Jazyky nad Z jsou tedy právě podmnožiny Z*. IB102 Automaty a gramatiky, 16.9.2019 3/26 Operace a relace nad slovy Binární operace zřetězení, označována •, která je definována předpisem: u.v = uv Operace zřetězení je asociativní, tj. u.(v.w) = (u.v).w pro libovolná slova u, v, w. s se chová jako jednotkový prvek, tj. u.e = e.u = u pro libovolné slovo u. IB102 Automaty a gramatiky, 16.9.2019 4/26 Slovo u je podslovem slova v, jestliže existují slova x, y taková, že v = x.u.y. Pokud navíc x = s, říkáme že slovo u je předponou (prefixem) slova v, což značíme u ^ v. Je-li y = e, nazveme u příponou (sufixem) slova v. IB102 Automaty a gramatiky, 16.9.2019 5/26 Unární operace Mé mocniny slova, která je definovaná induktivně pro každé / g N0 takto: nechť Z je libovolná abeceda, u libovolné slovo nad abecedou Z. Pak ■ u° = e ■ = u.u' IB102 Automaty a gramatiky, 16.9.2019 6/26 Operace nad jazyky Nechť L je jazyk nad abecedou Z, K je jazyk nad abecedou A. Výsledkem je vždy jazyk nad abecedou Z u A. ■ Standardní množinové operace sjednocení (u), průnik (n) a rozdíl (\). ■ Zřetězením jazyků L a K je jazyk L K = {u.v | u e L, v e K}. Platí 0.L = L0 = 0 a {e}.L=L{e} = L IB102 Automaty a gramatiky, 16.9.2019 7/26 Má mocnina jazyka L definována induktivně pro / e N0: L° = {e} L/+1 = L/.' 0° = {e} 0' = 0 pro libovolné / e N {s}J = {^} pro libovolné j e N0 IB102 Automaty a gramatiky, 16.9.2019 8/26 Iterace jazyka L je jazyk Ľ = \J^0 Ľ- 0* = {e} Pozitivní iterace jazyka L je jazyk L+ = |J^1 Ľ 0+ = 0. IB102 Automaty a gramatiky, 16.9.2019 9/26 Doplněk jazyka L je jazyk co-L = Z* \ L Zrcadlovým obrazem slova w = a^ ...an nazýváme slovo wR = an... a-i (čh = e). Zrcadlový obraz jazyka L definujeme LR = {wR \ w e L}. IB102 Automaty a gramatiky, 16.9.2019 10/26 Nechť C je třída jazyků a o je n-ární operace na jazycích. Řekneme, že C je uzavřená na o, pokud pro libovolné jazyky Li,...,Ln patřící do C platí, že také jazyk o{L^...,Ln) patří do Ĺ. IB102 Automaty a gramatiky, 16.9.2019 11/26 Aplikace IB102 Automaty a gramatiky, 16.9.2019 12/26 Konečná reprezentace jazyka ■ potřeba konečné reprezentace ■ co je konečná reprezentace ■ automaty a gramatiky ■ existuje konečná reprezentace pro každý jazyk? ■ jaké vlastnosti mají jazyky, které jsou konečně reprezentovatelné? IB102 Automaty a gramatiky, 16.9.2019 13/26 Gramatika Gramatika je popis jazyka pomocí pravidel, podle kterých se vytvářejí všechna slova daného jazyka. JANA ČTE KNIHU Zadání syntaxe vyšších programovacích jazyků — Backus-Naurova normální forma (BNF) IB102 Automaty a gramatiky, 16.9.2019 14/26 Definice. Gramatika Q je čtveřice (A/, Z, P, S), kde ■ N je neprázdná konečná množina neterminálních symbolů (stručněji neterminálů), ■ Z je konečná množina terminálních symbolů (terminálů) taková, že N n Z = 0. Množinu všech symbolů gramatiky definujeme jako V = NuZ, ■ Pc V*NV* x \/* je konečná množina pravidel. Pravidlo (a,/3) obvykle zapisujeme ve tvaru a /3 (a čteme jako „a přepis na /3"), ■ S g A/ je speciální počáteční neterminál (nazývaný také kořen gramatiky). IB102 Automaty a gramatiky, 16.9.2019 15/26 Příklad IB102 Automaty a gramatiky, 16.9.2019 16/26 Gramatika Q = (A/, Z, P, S) určuje ■ relaci přímého odvození na množině V* 7 =>g 5 právě když existuje pravidlo a -»f3 e P a slova r],g e V taková, že 7 = 770^ a S = 77/?^. Používá se i označení krok odvození. IB102 Automaty a gramatiky, 16.9.2019 17/26 ■ relaci =4>g odvození v k krocích pro k e N0 4>g je identická relace /c+1 k g = ^g o^g IB102 Automaty a gramatiky, 16.9.2019 18/26 g odvození a relaci =4>g. Relace =>í je tranzitivní uzávěr relace =4>g. IB102 Automaty a gramatiky, 16.9.2019 19/26 Větná forma gramatiky Q je každý řetěz z množiny V*, který lze odvodit z počátečního neterminálu gramatiky. Věta gramatiky Q je každá větná forma, která obsahuje pouze terminály. Jazyk generovaný gramatikou Q je množina L(Q) všech vět gramatiky L{Q) = {weZ* \S^*g w}. Gramatiky a Q2 nazveme jazykově ekvivalentní, právě když generují tentýž jazyk, tj. L(0i) = /.(&)■ IB102 Automaty a gramatiky, 16.9.2019 20/26 Konvence IB102 Automaty a gramatiky, 16.9.2019 21/26 Příklad g = ({S,X},{a,b},P, S) P={S abS S ->• bX bbX^ babS bbX^ s } IB102 Automaty a gramatiky, 16.9.2019 22/26 Příklad g = ({S,X},{a,b},P, S) P={S abS S ->• bX bbX^ babS bbX^ s } IB102 Automaty a gramatiky, 16.9.2019 23/26 Chomského hierarchie gramatik Klasifikace gramatik podle tvaru přepisovacích pravidel: typ 0 pravidla v obecném tvaru (frázové gramatiky) typ 1 pro každé pravidlo a f3 platí \a\ < |/3| s eventuální výjimkou pravidla S e, pokud se S nevyskytuje na pravé straně žádného pravidla (kontextové gramatiky) typ 2 každé pravidlo je tvaru A a, kde \a\ > 1, s eventuální výjimkou pravidla S e, pokud se S nevyskytuje na pravé straně žádného pravidla (bezkontextové gramatiky (bez ^-pravidel)) typ 3 každé pravidlo je tvaru A aB nebo A^ř as eventuální výjimkou pravidla S e, pokud se S nevyskytuje na pravé straně žádného pravidla (regulární gramatiky) IB102 Automaty a gramatiky, 16.9.2019 24/26 Chomského hierarchie jazyků Hierarchie gramatik určuje hierarchii jazyků. Jazyk L je typu 0 (rekursivně spočetný), pokud existuje gramatika Q typu 0 taková, že L{Q) = L Analogicky: kontextový, bezkontextový, regulární C0 třída všech rekursivně spočetných jazyků £1 třída všech kontextových jazyků £2 třída všech bezkontextových jazyků £3 třída všech regulárních jazyků (Dokážeme později.) IB102 Automaty a gramatiky, 16.9.2019 25/26 Věta. Nad abecedou {a} existuje jazyk, který není typu 0. Důkaz. Množina všech slov nad abecedou {a} je spočetně nekonečná. Množina všech jazyků nad touto abecedou má proto mohutnost 2K° (je tedy nespočetná). Gramatik typu 0 nad abecedou {a} je pouze spočetně mnoho: ■ buď M libovolná, ale pevně zvolená spočetná množina ■ b.ú.n.o. každá gramatika má neterminály z M ■ každá gramatika je slovo nad abecedou M u {a, (,),{,},,} ■ všech slov délky / nad touto abecedou je W0 = tt0 pro lib. / g N ■ všech slov nad touto abecedou je tedy spočetně mnoho (sjednocení spočetně mnoha spočetných množin je spočetné) IB102 Automaty a gramatiky, 16.9.2019