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, 15.9.2014
1/26
Slovo (řetězec) nad abecedou T. 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(^)-
IB102 Automaty, gramatiky a složitost, 15.9.2014 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, gramatiky a složitost, 15.9.2014
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.
e se chová jako jednotkový prvek, tj. u.e = e.u = u pro libovolné slovo u.
IB102 Automaty, gramatiky a složitost, 15.9.2014
4/26
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 ív příponou (sufixem) slova y.
IB102 Automaty, gramatiky a složitost, 15.9.2014
5/26
Unární operace /'-té 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°=6
■ t/+1 = u.u'
IB102 Automaty, gramatiky a složitost, 15.9.2014
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 g K}.
Platí 0.L = L0 = 0  a   {e}.L = L {e} = L.
IB102 Automaty, gramatiky a složitost, 15.9.2014
■ /-tá mocnina jazyka L definována induktivně pro
L° = {e} Li+: = L. ľ
0° = {s}
0' = 0 pro libovolné / g N
= {e} pro libovolné j g N0
IB102 Automaty, gramatiky a složitost, 15.9.2014
■ Iterace jazyka L je jazyk ľ = \J°10 ľ.
0* = {£}
■ Pozitivní iterace jazyka L je jazyk L
0+ =0.
IB102 Automaty, gramatiky a složitost, 15.9.2014
■ Doplněk jazyka l je jazyk co-l = Z* \ l.
m Zrcadlovým obrazem slova w = a-i... an nazýváme slovo
WR = an ■ ■ ■ a-i (eR = e).
Zrcadlový obraz jazyka l definujeme lr = {wR \ w g ľ}.
IB102 Automaty, gramatiky a složitost, 15.9.2014
10/26
Nechť Ĺ je třída jazyků a o je /i-ární operace na jazycích. Řekneme, že Ĺ je uzavřená na o, pokud pro libovolné jazyky L\,...,Ln patřící do Ĺ platí, že také jazyk o(L-\ ,...,Ln) patří do Ĺ.
IB102 Automaty, gramatiky a složitost, 15.9.2014
11/26
Aplikace
IB102 Automaty, gramatiky a složitost, 15.9.2014
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, gramatiky a složitost, 15.9.2014
Gramatika
Gramatika je popis jazyka pomocí pravidel, podle kterých se vytvářejí všechna slova daného jazyka.
<věta> ->• <podmětná částxpřísudková část> <podmětná část> ->• <podstatné jméno ► JANA
<slovesoxpředmětová část>
<podstatné jméno <přísudková část> -<sloveso> ->• ČTE <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, 15.9.2014
14/26
Definice. Gramatika Q je čtveřice (N, 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 = A/UZ,
i Pc v*NV* x V* 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, gramatiky a složitost, 15.9.2014
15/26
Příklad
IB102 Automaty, gramatiky a složitost, 15.9.2014
Gramatika Q = (N, Z, P, S) určuje ■ relaci =4>g přímého odvození na množině V*
7 S právě když existuje pravidlo a-í/?ePa slova r), g e 1/* taková, že 7 =      a á = 77/3,0.
Používá se i označení krok odvození.
IB102 Automaty, gramatiky a složitost, 15.9.2014
17/26
■ relaci     odvození v k krocích pro k e N0
=>g je identická relace
k+"\ k
=> g  = °
IB102 Automaty, gramatiky a složitost, 15.9.2014
18/26
relaci =>g odvození v nejvýše k krocích pro k e N0
k
<k i   i i
^g = \J^g
i=0
relaci =^ odvození a relaci =4><t netriviálního odvození
OO OO
Relace     je reflexivní a tranzitivní uzávěr relace =>g. Relace =^ je tranzitivní uzávěr relace =>g.
IB102 Automaty, gramatiky a složitost, 15.9.2014
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{G) = {weT.*\S^*g w}.
Gramatiky Q-\ a Q2 nazveme jazykově ekvivalentní, právě když generují tentýž jazyk, tj. L(£i) = L{Q2).
IB102 Automaty, gramatiky a složitost, 15.9.2014
20/26
Konvence
IB102 Automaty, gramatiky a složitost, 15.9.2014
21/26
Příklad
G = ({S,X},{a,b},P, S)
P = {S   -+ abS S   ->• bX bbX^ babS bbX^ e }
IB102 Automaty, gramatiky a složitost, 15.9.2014
22/26
Příklad
G = ({S,X},{a,b},P, S)
P = {S   -+ abS S   ->• bX bbX^ babS bbX^ e }
IB102 Automaty, gramatiky a složitost, 15.9.2014
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 ->•(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é 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é pravidlo je tvaru A    aB nebo A^ as 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, 15.9.2014
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í
Cq 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, gramatiky a složitost, 15.9.2014 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 m každá gramatika je slovo nad abecedou
M u {a,    £,(,), {,},,}
■ všech slov délky / nad touto abecedou je tt'Q = ft0 Pr° lib- / e 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, gramatiky a složitost, 15.9.2014