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, 20.9.2010
1
Slovo (řetězec) nad abecedou S je libovolná konečná posloupnost znaků teto abecedy.
Prázdne posloupnosti znaků odpovídá prázdně slovo, označovane e. Počet členů posloupnosti v značíme |v| a nazývame dělkou slová. PoCet výskytU znaku a ve slove v značíme #a(v).
IB102 Automaty a gramatiky, 20. 9. 2010 2
Jazyk nad abecedou S je libovolná množina slov nad S.
Množinu vsech slov nad abecedou S žnaCíme S*, množinu vsech nepraždných slov S+.
Jažyky nad S jsou tedý prave podmnožiny S*.
IB102 Automaty a gramatiky, 20.9.2010
3
Operace a relace nad slovy
Binární operace zretezení, označována    která je definována předpisem
u.v = uv
Operace zřetezen í je asociativn í, tj. u.(v.w) = (u.v).w pro libovolna slova u, v, w.
e se chova jako jednotkový prvek, tj. u.e = e.u = u pro libovolne slovo u.
IB102 Automaty a gramatiky, 20.9.2010
4
Slovo u je podslovem slova v, jestliže existují slova x, y taková, že v = x.u.y.
Pokud navíc x = e, ríkáme že slovo u je předponou (prefixem) slova v, což žnaCíme u ■< v. Je-li y = e, nazveme u příponou (sufixem) slova v.
IB102 Automaty a gramatiky, 20.9.2010
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 S. Pak
• u0 = e
• ui+1 = u.u1
IB102 Automaty a gramatiky, 20.9.2010
6
Operace nad jazyky
L je jažyk nad abecedou E, K je jažyk nad abecedou A Vysledkem je vždy jažyk nad abecedou E U A.
• Standardní množinove operace sjednocen í (U),   průnik (n) a rozd íl (\).
• Zretezen ím jažyku K a L je jažyk K.L = {u.v | u G K, v G L}.
Platí     0.L = L.0 = 0      a      {e}.L = L.{e} = L.
IB102 Automaty a gramatiky, 20. 9. 2010
7
i-tá mocnina jazyka L definována induktivně pro i G N0:
1. L0 = [e]
2. Li+1 = L.L*
00 = [e]
0* = 0 pro libovolně i G N [e]j = [e] pro libovolně j G N0
IB102 Automaty a gramatiky, 20.9.2010
8
• Iterace jažyka L je jažyk L* = [j°=0 L*.
0* = [e}
• Pozitivní iterace jažyka L je jažyk L+ = [j?=, L*.
0+ = 0.
IB102 Automaty a gramatiky, 20. Q. 2010
Q
• Doplněk jazyka L je jazyk co-L = S* \ L.
• Zrcadlovým obrazem slova w = ay... an nazývame slovo
wR = an ... a-y (eR =
Zrcadlový obraz jazýka L definujeme LR = {wR | w G L}.
IB102 Automaty a gramatiky, 20.9.2010
10
Necht L je trída jažykU a o je n-arní operace na jazycích. Řekneme, že L je uzavřená na o, pokud pro libovolne jažyky L1,... , Ln patricí do L platí, že take jažyk o(L1,..., Ln) patrí do L.
IB102 Automaty a gramatiky, 20. 9. 2010
11
Aplikace
IB102 Automaty a gramatiky, 20.9.2010
12
Konečná reprezentace jazyka
• potreba konečné reprezentace
• co je konečna reprezentace
• automaty a gramatiky
• ??? existuje konečna reprezentace pro kaZdy jazyk ???
• ??? jake vlastnosti mají jazyky, ktere jsou konecne reprezentovatelne ???
IB102 Automaty a gramatiky, 20. 9. 2010 13
Pojém gramatiky
Popis jazyka pomocí pravidél, podlé ktéřych sé vytvářejí vSéchny slova daného jazyka.
<veta> — <podmetna cast><prísudkova cast> <podmetna cast> — <podstatne jmeno> <podstatne jmeno> — JANA
<prísudkova cast> — <sloveso><predmetova cast> <sloveso> — CTE
<predmetova cast> — <podstatne jmeno> <podstatne jmeno> — KNIHU
Zadaní syntaxe vyssích programovacích jažyku — Backus-Naurova normalní forma (BNF)
IB102 Automaty a gramatiky, 20. 9. 2010
14
Definice 1.   Gramatika G je čtveřice (N, S,P, S), kde
• N je neprazdna konečna množina neterminainích symbolů (stručneji: neterminaiů).
• S je konečna množina terminainích symbolů (terminaiů) takova, že N n S = 0. Sjednocením N a S obdržíme množinu vSech symbolů gramatiky, kterou obvykle ožnačujeme symbolem V.
• P C V *NV * x V * je konečna množina pravidel. Pravidlo (a, P) obvykle žapisujeme ve tvaru a —» P (a čteme jako "a přepis na P").
• S G N je spečialní pocatecní neterminal (nažyvany take koren gramatiky).
IB102 Automaty a gramatiky, 20. 9. 2010
15
Příklad gramatiky
IB102 Automaty a gramatiky, 20.9.2010
16
Gramatika G = (N, Y,, P, S) urCuje
• relaci =^>g přímého odvození na mnoZině V *
Y =^>g ô pravě kdyZ existuje pravidlo a — /? G P a slova n, Q G V * takova, Ze y = naQ a ô = n P Q.
PouZíva se i oznaCení krok odvození.
IB102 Automaty a gramatiky, 20. 9. 2010
17
• relaci =^>g odvození v k krocích pro k G No - 4>g je identická relace
k+1 k
IB102 Automaty a gramatiky, 20.9.2010
18
<k
• relaci    g odvozen í v nejvýše k kroc ích pro k G No
• relaci =^>g odvozen í
^    _   i F \
g   - Ui=o
Relace =^>g je reflexivn í a tranzitivn í uzaver =^>g. • relaci       netriviáln ího odvozen í
g   — Ui=i
Relace      je tedy tranzitivn í uzaver relace =^>g.
IB102 Automaty a gramatiky, 20.9.2010
19
Větná fomiá gramatiky G je kazdy retez z mnoziny V*, který lze odvodit z počatečního neterminalu gramatiky.
Větá gramatiky G je kazda vetna forma, ktera obsahuje pouze terminaly.
Jazyk gěněřováný gřámátikou G, L(G) je mnozina vsečh vet gramatiky
L(G) = {w G S* | S ^* w}.
Gramatiky Gi a G2 nazveme jázykově ěkviválěntní, prave kdyz generují tentyz jazyk, tj. L(Gi) = L(G2).
IB102 Automaty a gramatiky, 20. 9. 2010
20
Konvěncě
IB102 Automaty a gramatiky, 20.9.2010
21
Príklad
G = ({S,X}, {a,b},P,S) P = { S     — abS S     — bX
bbX - babS bbX - e }
IB102 Automaty a gramatiky, 20.9.2010
22
Príklad
G = ([S,X}, [a,b},P,S) P = [ S     — abS S     — bX
bbX - babS bbX - e }
IB102 Automaty a gramatiky, 20. Q. 2010
23
DU: Zjistěte, jaky jazyk generuje gramatika
G = ([S,A], [0,1],P,S)
P = [ S — 1S   | 0S   | 101A A — 1A | 0A  | e ]
IB102 Automaty a gramatiky, 20. 9. 2010
24
Chomskěho hierarchie gramatik
Klasifikace gramatik podle tvaru přepisovacích pravidel
týp 0 pravidla v obecnem tvaru (frazově gramatiky)
týp 1 pro kaZde její pravidlo a —3 platí |a| < |3| s eventuelní výjimkou pravidla S — e, pokud se S nevyskytuje na prave strane Zadneho pravidla (kontextově gramatiký)
týp 2 kaZde jej í pravidlo je tvaru A — a, kde |a| > 1 s eventueln í vyjimkou pravidla S — e, pokud se S nevyskytuje na prave stranře řzadneho pravidla (bězkontěxtově gramatiký)
týp 3 kaZde jej í pravidlo je tvaru A — aB nebo A — a s eventueln í vyjimkou pravidla S — e, pokud se S nevyskytuje na prave strane Zadneho pravidla (rěgularní gramatiký)
IB102 Automaty a gramatiky, 20. 9. 2010
25
Chomskeho hierarchie jazyků
Hierarchie gramatik urcuje hierarchii jazyku.
Jazyk L je typů 0 (rekůrsivne spočetný) pokud existuje gramatika G typu 0 takova, ze L(G) = L.
Analogicky: kontextový, bezkontextovy, regůlarní
C0 trída vsech rekursivne spocetnych jazyku Cl trída vsech kontextovych jazyku C2 trída vsech bezkontextovych jazyku C3 trída vsech reguiarních jazyku
Co DCi D C2 D C3
(Důkaz později)
IB102 Automaty a gramatiky, 20. 9. 2010
26
Veta 1.   Nad abecedou {a} existuje jažyk, ktery není typu 0. Důkaz.
• množina vsech slov nad abecedou {a} je spocetne nekonecna
• množina vsech jažyku nad touto abecedou ma proto mohutnost 2K° (je tedy nespocetna)
• gramatik typu 0 nad abecedou {a} je použe spocetne mnoho:
— bud M libovolna, ale pevne žvolena spocetna množina
— b.u.n.o. každa gramatika ma neterminaly ž M
— kadžda gramatika je slovo nad abecedou
M U {a,        (,),{,}, J
— vsech slov delky i nad touto abecedou je     =     pro lib. i G N
— vsech slov nad touto abecedou je tedy spocetne mnoho (sjednocení spočetně mnoha spočetných mn. je spočetné) □
IB102 Automaty a gramatiky, 20. 9. 2010
27