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, 21.9.2009
Slovo (řetězec)  nad  abecedou  S 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 |i;| a nazýváme délkou slova. Počet výskytů znaku a ve slově v značíme #a(^)-
IB102 Automaty a gramatiky, 21.9.2009
Jazyk nad abecedou S je libovolná množina slov nad
Množinu všech slov nad abecedou S značíme S*, množinu všech neprázdných slov S+.
Jazyky nad S jsou tedy právě podmnožiny S*.
IB102 Automaty a gramatiky, 21.9.2009
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.{y.w) = (u.v).w pro libovolná slova u,v,w.
e se chová jako jednotkový prvek,  tj. u.e = e.u = u pro libovolné slovo u.
IB102 Automaty a gramatiky, 21.9.2009
4
Slovo u je podslovem slova v, jestliže existují slova x, y taková, že v = x.u.y.
Pokud navíc x = e, ří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, 21.9.2009
5
Unární operace i-té mocniny slova, která je definovaná induktivně pro každé i G No takto: necht S je libovolná abeceda, u libobolne slovo nad abecedou £. Pak
•  u° = e
•  ul+1 = u.u1
IB102 Automaty a gramatiky, 21.9.2009
6
Operace nad jazyky
L je jazyk nad abecedou E,   K je jazyk nad abecedou A Výsledkem je vždy jazyk nad abecedou S U A.
•  Standardní   množinové   operace   sjednocení   (U),    průnik   (n)   a rozdíl (\).
•  Zřetězením jazyků K a L je jazyk K.L = {u.v | u G K, v G L}.
Platí      0.L = LS = 0        a        {č}.L = L.{e} = L.
IB102 Automaty a gramatiky, 21.9.2009
7
• i-tá mocnina jazyka L definována induktivně pro i G No:
1.  L° = {s}
2.  Li+1 = L.IŠ
0° = {e}
0* = 0 pro libovolné i e N
{e}-7 = {e} pro libovolné j G No
IB102 Automaty a gramatiky, 21.9.2009                                                                                                                                                                           8
• Iterace jazyka L je jazyk L* = Ui^o ^-
0* = {e} • Pozitivní iterace jazyka L je jazyk L+
0+ = 0.
IB102 Automaty a gramatiky, 21.9.2009
U£i£V
9
Doplněk jazyka L je jazyk co-L = S* \ L
Zrcadlovým obrazem slova w = a\.. ,an nazýváme slovo
wR = an ... a\ [eR — e).
Zrcadlový obraz jazyka L definujeme LK = {wK   w G  L}.
IB102 Automaty a gramatiky, 21. 9. 2009                                                                                                                                                                                          10
Necht 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(Li,..., Ln) patří do C
IB102 Automaty a gramatiky, 21.9.2009
11
Aplikace
IB102 Automaty a gramatiky, 21.9.2009
12
Konečná reprezentace jazyka
•  potřeba konečné reprezentace
•  co je konečná reprezentace
•  automaty a gramatiky
•  111 existuje konečná reprezentace pro každý jazyk 111
•  ??? jaké vlastnosti mají jazyky, které jsou konečně reprezentovatelné 111
IB102 Automaty a gramatiky, 21. 9. 2009                                                                                                                                                                         13
Pojem gramatiky
Popis jazyka pomocí pravidel, podle kterých se vytvářejí všechny slova daného jazyka.
<věta> —> <podmětná částXpřísudková část>
<podmětná část> —» <podstatné jméno>
<podstatné jméno> —>   JANA
<přísudková část> —> <sloveso><předmětová část>
<sloveso> —>   CTE
<předmětová část> —» <podstatné jméno>
<podstatné jméno> —»   KNIHU
Zadání syntaxe  vyšších   programovacích  jazyků   —   Backus-Naurova normální forma (BNF)
IB102 Automaty a gramatiky, 21.9.2009
14
78
Definice 1.    Gramatika Q je čtveřice (TV, E, P, 5), kde
•  N je neprázdna konečná množina neterminálních symbolů (stručněji: neterminálů).
•  S je konečná množina terminálních symbolů (terminálů) taková, že NaT = 0. Sjednocením JVaS obdržíme množinu všech symbolů gramatiky, kterou obvykle označujeme symbolem V.
•  PC V*NV* x I/* je konečná množina pravidel. Pravidlo (a,ß) obvykle zapisujeme ve tvaru a —» ß (a čteme jako ua prepis na /?").
•  S G TV je speciální počáteční neterminál (nazývaný také kořen gramatiky).
IB102 Automaty a gramatiky, 21.9.2009
15
Příklad gramatiky
IB102 Automaty a gramatiky, 21.9.2009
16
Gramatika Q = (TV, S, P, S) určuje
• relaci ^g přímého odvození na množině V*
7 ^g ô právě když existuje pravidlo a —» ß G P a slova 77, £ G V taková, že 7 = r/a g a 5 = 77/?^.
Používá se i označení krok odvození.
IBIO2 Automaty a gramatiky, 21.9.2009
17
k
• relaci ^g odvození v k krocích pro k G No - ^g je identická relace
fc+l                k
IB102 Automaty a gramatiky, 21.9.2009
18
<k
relaci ^>g odvození v nejvýše k krocích pro fcGNo
<k        _    nk        i
^Q    -    Ui=o ^Q
relaci =>g odvození
g    -    U;=o =^6
Relace =>g je reflexivní a tranzitivní uzávěr ^g relaci =^<t~ netriviálního odvození
+
Relace =^<t je tedy tranzitivní uzávěr relace ^g
IB102 Automaty a gramatiky, 21. 9. 2009                                                                                                                                                                         19
Větná  forma gramatiky Q je každý řetěz z množiny 1/*,   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,   L{Q)   je   množina   všech   vět gramatiky
L(Q) = {we£* | S ^* w}.
Gramatiky Q\ a G2 nazveme jazykově ekvivalentní, právě když generují tentýž jazyk, tj. L(Qi) = L(Q2).
IBIO2 Automaty a gramatiky, 21.9.2009
20
Konvence
IB102 Automaty a gramatiky, 21.9.2009
21
Příklad
g = ({S,X},{a,b},P,S)
P = {S      ->  abS
S      -».  bX
bbX    -»■    &ač>S
bbX  ^  e       }
IB102 Automaty a gramatiky, 21.9.2009
22
Příklad
g = ({S,X},{a,b},P,S)
P = {S      ->  abS
S      -».  bX
bbX    -»■    &ač>S
bbX  ^  e       }
IB102 Automaty a gramatiky, 21.9.2009
23
DU:   Zjistěte, jaký jazyk generuje gramatika
g = ({s,A},{o,i},p,s)
P = {S A
IS 1A
OS OA
101A
£
}
IB102 Automaty a gramatiky, 21.9.2009
24
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é její pravidlo a —» ß platí \a\ < \ß\ s eventuelní výjimkou pravidla S —» e, pokud se S nevyskytuje na pravé straně žádného pravidla (kontextové gramatiky)
typ 2 každé její pravidlo je tvaru A —» a, kde \a\ > 1 s eventuelní výjimkou pravidla S —» e, pokud se S nevyskytuje na pravé straně žádného pravidla (bezkontextové gramatiky)
typ 3 každé její pravidlo je tvaru A —» aB nebo A ^ a s eventuelní výjimkou pravidla S —» e, pokud se S nevyskytuje na pravé straně žádného pravidla (regulární gramatiky)
IB102 Automaty a gramatiky, 21.9.2009
25
Chomského hierarchie jazyků
Hierarchie gramatik určuje hierarchii jazyků.
Jazyk L je typu 0 (rekursivne spočetný) pokud existuje gramatika Q typu 0 taková, že L{Q) = L.
Analogicky: kontextový, bezkontextový, regulární
Co třída všech rekursivne spočetných jazyků L\ třída všech kontextových jazyků C2 třída všech bez kontextových jazyků £3 třída všech regulárních jazyků
£0 D A D £2 D £3 (Důkaz později)
IBIO2 Automaty a gramatiky, 21.9.2009
26
Věta 1.    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:
-  bud 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, -,e, (,),{,}, ,}
-  všech slov délky i nad touto abecedou je W0 = H0 Pr° üb. i G N
-  všech slov nad touto abecedou je tedy spočetně mnoho (sjednocení spočetně mnoha spočetných mn. je spočetné)             D
IB102 Automaty a gramatiky, 21.9.2009
27