Formální jazyk
Abeceda - slovo - jazyk
Abeceda je libovolná konečná množina
Prvky abecedy nazýváme znaky / písmena / symboly
IB102 Automaty, gramatiky a složitost, 16.9.2013
Slovo (řetězec) nad abecedou S je libovolná konečná posloupnost znaků této abecedy.
Prázdne posloupnosti znaků odpovídá prázdné slovo, označované e, Počet členů posloupnosti v značíme     a nazýváme délkou slova. Počet výskytů znaku a ve slově v značíme #a(^)-
IB102 Automaty, gramatiky a složitost, 16.9.2013
Jazyk nad abecedou S je libovolná množina slov nad S.
Množinu všech slov nad abecedou S značíme E*, množinu všech neprázdných slov S+.
Jazyky nad S jsou tedy právě podmnožiny E*.
IB102 Automaty, gramatiky a složitost, 16. 9. 2013 3
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    v, w.
e se chová jako jednotkový prvek, tj. u.e = e.u = u pro libovolné slovo u.
IB102 Automaty, gramatiky a složitost, 16.9.2013
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, gramatiky a složitost, 16.9.2013
Unární operace i-té mocniny slova, která je definovaná induktivně pro každé i G No takto: necht S je libovolná abeceda, u libobolné slovo nad abecedou S. Pak
u° = e
u%Jrl = u.u1
IB102 Automaty, gramatiky a složitost, 16.9.2013
6
Operace nad jazyky
L je jazyk nad abecedou S, 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 £ K, v G L}.
Platí     0.L = L.0 = 0      a      {e}.L = L.{e} = L.
IB102 Automaty, gramatiky a složitost, 16.9.2013
7
i-tá mocnina jazyka L definována induktivně pro i G No
1. L° = {e}
2. Li+1 = L.Ů
0° = {s}
0* = 0 pro libovolné i G N
= {e} pro libovolné j G No
IB102 Automaty, gramatiky a složitost, 16.9.2013
8
Iterace jazyka L je jazyk L* = Ui^o ^1 -
0* = {e}
Pozitivní iterace jazyka L je jazyk L+ = Uí^i L'
0+ = 0,
IB102 Automaty, gramatiky a složitost, 16.9.2013
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 LR = {w^ \ w G L}
IB102 Automaty, gramatiky a složitost, 16.9.2013
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 £.
IB102 Automaty, gramatiky a složitost, 16.9.2013
11
Aplikace
IB102 Automaty, gramatiky a složitost, 16.9.2013
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, gramatiky a složitost, 16. 9. 2013 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, gramatiky a složitost, 16.9.2013
14
Definice 1.   Gramatika Q je čtveřice (iV,       5), kde
• iV je neprázdná 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 iVnE = 0. Sjednocením iVaS obdržíme množinu všech symbolů gramatiky, kterou obvykle označujeme symbolem V.
• PC V*NV* x 1/* je konečná množina pravidel. Pravidlo (a,/3) obvykle zapisujeme ve tvaru a —> (3 (a čteme jako "a přepis na fi").
• S G N je speciální počáteční neterminál (nazývaný také kořen gramatiky).
IB102 Automaty, gramatiky a složitost, 16.9.2013
15
Příklad gramatiky
IB102 Automaty, gramatiky a složitost, 16.9.2013
16
Gramatika Q — (iV, E, P, 5) určuje
• relaci =>g přímého odvození na množině V*
7 =>g ô právě když existuje pravidlo a^^GPa slova 77, g G V taková, že 7 = rjag a 5 = rj/3g.
Používá se i označení krok odvození.
IB102 Automaty, gramatiky a složitost, 16.9.2013
17
k
relaci =>g odvození v k krocích pro k £ No - 4>£ je identická relace
fc+l k
g   =   ^g o^g
IB102 Automaty, gramatiky a složitost, 16.9.2013
18
<k
relaci ^g odvození v nejvýše k krocích pro k £ No
<k      _   \ \k i
relaci =>g odvození
^g   = USo
Relace =>g je reflexivní a tranzitivní uzávěr relaci =^><t netriviálního odvození
Relace =^<t je tedy tranzitivní uzávěr relace
IB102 Automaty, gramatiky a složitost, 16.9.2013 19
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, L(Q) je množina všech vět gramatiky
L(G) = {w e £* | w}.
Gramatiky Q\ a Q2 nazveme jazykově ekvivalentní, právě když generují tentýž jazyk, tj. L(Qi) = L(Q2)-
IB102 Automaty, gramatiky a složitost, 16.9.2013
20
Konvence
IB102 Automaty, gramatiky a složitost, 16.9.2013
Příklad
g = ({S,X},{a,b},P,S)
P = {S ->• abS
S bX
bbX ->• öakS
bbX ^ e }
IB102 Automaty, gramatiky a složitost, 16.9.2013
22
Příklad
g = ({S,X},{a,b},P,S)
P = {S ->• abS
S bX
bbX ->• öakS
bbX ^ e }
IB102 Automaty, gramatiky a složitost, 16.9.2013
23
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 —> (3 platí \a\ < \/3\ 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 (bez e-pravidel))
typ 3 každé její pravidlo je tvaru A —> aB nebo Í4as eventuelní výjimkou pravidla S e, pokud se S nevyskytuje na pravé straně žádného pravidla (regulární gramatiky)
IB102 Automaty, gramatiky a složitost, 16. 9. 2013 24
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í
Co třída všech rekursivně spočetných jazyků Ci 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ů
Co D A D C2 D C3
(Důkaz později)
IB102 Automaty, gramatiky a složitost, 16.9.2013
25
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 2^° (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, ->,£;, (,),{,}, ,}
- všech slov délky i nad touto abecedou je     =     Pr° lib. 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é) □
IB102 Automaty, gramatiky a složitost, 16.9.2013
26