A1. Kapitoly z teorie form´ aln´ıch jazyk˚ u a automat˚ u c
Milan Schwarz (2006)
1) Sekvenˇ cn´ı a paraleln´ı gramatiky Derivace v gramatik´ ach: • Sekvenˇcn´ı postup – sekvenˇcn´ı gramatiky (napˇr. gramatiky v Chomsk´eho hierarchii) - v kaˇzd´em kroku derivace je vybr´ano a pouˇzito jedno pravidlo gramatiky na jeden netermin´al. • Paraleln´ı postup – paraleln´ı gramatiky (napˇr. Lindenmayerovy syst´emy) - v kaˇzd´em kroku derivace jsou najednou pˇreps´any vˇsechny netermin´aly ve slovˇe, mohou b´ yt paralelnˇe pouˇzita r˚ uzn´a pravidla, jedno pravidlo i v´ıcekr´at na r˚ uzn´ ych m´ıstech. a)Sekvenˇ cn´ı gramatiky - Chomsk´ eho klasifikace gramatik: Tato klasifikace vymezuje ˇctyˇri druhy gramatik, podle tvaru pˇrepisovac´ıch pravidel, jeˇz obsahuje mnoˇzina pˇrepisovac´ıch pravidel P. Tyto typy se oznaˇcuj´ı jako typ 0, typ 1, typ 2 a typ 3. Typ 0 (neomezen´e) : Gramatika typu 0 obsahuje pravidla v nejobecnˇejˇs´ım tvaru, shodn´ ymi s definic´ı gramatiky: P Def.: Gramatika G je ˇctveˇrice G = (N, , P, S), kde N - je koneˇcn´a mnoˇzina netermin´aln´ıch symbol˚ u P P - je koneˇcn´a mnoˇzina termin´aln´ıch symbol˚ u, N ∩ = ⊘ P P P - je koneˇcn´a podmnoˇzina kart´ezsk´eho souˇcinu (N ∪ )∗ N (N ∪ )∗ × (N ∪ P ∗ ) S ∈ N je v´ ychoz´ı (tak´e poˇc´ateˇcn´ı) symbol gramatiky Z tohoto duvodu jsou gramatiky typu 0 oznaˇcov´any jako gramatiky neomezen´e. Pˇr´ıkladem takov´e gramatiky muˇze b´ yt jak´akoliv gramatika. Typ 1 (kontextov´e) : Gramatika typu 1 obsahuje pravidla tvaru : P P αAβ → αγβ, A ∈ N, α, β ∈ (N ∪ )∗ , γ ∈ (N ∪ )+ nebo S → ǫ Gramatiky typu 1 naz´ yv´ame gramatikami kontextov´ ymi, protoˇze tvar pravidla t´eto gramatiky implikuje, ˇze netermin´al A muˇze b´ yt nahrazen ˇretˇezcem γ pouze tehdy, je - li jeho prav´ ym kontextem β a lev´ ym kontextem α. Kontextov´e gramatiky nepˇripouˇstˇej´ı pravidla typu A → ǫ, tedy nahrazov´an´ı netermin´alu pr´azdn´ ym ˇretˇezcem. Jedinou v´ yjimku tvoˇr´ı pravidlo S → ǫ (S je v´ ychoz´ı symbol gramatiky), ale S se nesm´ı vyskytovat na prav´e stranˇe 1
ˇz´adn´eho pravidla. T´ım lze vyj´adˇrit pˇr´ısluˇsnost pr´azdn´eho ˇretˇezce k jazyku, kter´ y dan´a gramatika generuje. Pˇr.: L = {ai bi ci |i ≥ 1} Typ 2 (bezkontextov´e) : Gramatika typu 2 obsahuje pravidla tvaru : P A → γ, A ∈ N, γ ∈ (N ∪ )∗ Gramatiky typu 2 naz´ yv´ame gramatikami bezkontextov´ ymi, protoˇze substituc´ı lev´e strany γ pravidla za netermin´al A lze prov´adˇet bez ohledu na kontext, ve kter´em je netermin´al A uloˇzen. Na rozd´ıl od kontextov´ ych gramatik se v bezkontextov´ ych gramatik´ach mohou objevovat pravidla tvaru A → ǫ. Kaˇzdou bezkontextovou gramatiku lze transformovat na gramatiku obsahuj´ıc´ı nejv´ yˇse jedno takov´e pravidlo a to S → ǫ, pˇriˇcemˇz S se nevyskytuje na prav´e stranˇe ˇz´adn´eho pravidla. Pˇr.: L = {ai bi |i ≥ 1} Typ 3 (regul´arn´ı) : Gramatika typu 3 obsahuje pravidla typu : P A → aB nebo A → a, kde A, B ∈ N, a ∈ Pˇr.: L = {a}; L = {ai |i ≥ 1} b)Paraleln´ı gramatiky - Lindenmayerovy syst´ emy: Viz. ot´azka 2 a 3.
2
A1. Kapitoly z teorie form´ aln´ıch jazyk˚ u a automat˚ u c
Milan Schwarz (2006)
2) Lindenmayerovy syst´ emy, z´ akladn´ı charakteristiky • Nem´ame startovac´ı netermin´al, ale startovac´ı slovo – axiom (m˚ uˇze b´ yt v´ıce symbol˚ u). • V´ ypoˇcet prob´ıh´a paralelnˇe (vˇsechny symboly, kter´e lze pˇrepisovat, se v kaˇzd´em kroku pˇrep´ıˇsou). • Obvykle nerozliˇsujeme termin´aln´ı a netermin´aln´ı symboly, m´ame jedinou abecedu (kromˇe nˇekter´ ych typ˚ u L-syst´em˚ u, kter´e maj´ı zvl´aˇstn´ı abecedu termin´aln´ıch symbol˚ u, ta slouˇz´ı k zastaven´ı v´ ypoˇctu – kdyˇz se slovo skl´ad´a pouze z tˇechto symbol˚ u, v´ ypoˇcet se zastav´ı). • Obecnˇe m˚ uˇze b´ yt v´ ypoˇcet nekoneˇcn´ y nebo se zastav´ı po pˇredem zadan´em poˇctu krok˚ u, bˇehem v´ ypoˇctu slovo tak´e m˚ uˇze zaniknout (pouˇz´ıv´an´ım epsilonov´ ych pravidel). 0L-syst´ emy (Lindemayer˚ uv syst´ emy typu 0) P Def.: 0L-syst´emem naz´ yv´ame kaˇzdou trojici G = ( , P, w0 ), kde: P je koneˇcn´a abeceda P P P mnoˇzina pˇrepisovac´ıch pravidel tvaru a → α, kde a ∈ , α ∈ ∗ P w0 ∈ + axiom syst´emu (startovac´ı symbol); m˚ uˇzeme zaˇc´ınat ze slova a ne pouze ze startovac´ıho symbolu S, vˇetˇsinou nejkratˇs´ı slovo z jazyka. 0 v oznaˇcen´ı znamen´a, ˇze se jedn´a o L-syst´emy bez interakce, tzn. na pˇremˇenu symbolu nemaj´ı vliv sousedn´ı symboly. (Pozn.: Tvar pravidel analogick´ ys tvarem bezkontextov´ ych jazyk˚ u.) P
P
Def.: Slovo u = a1 ...an ∈ + lze v 0L syst´emu G = ( , P, 0), bezprostˇrednˇe pˇrepsat na slovo v, jestliˇze existuj´ı pravidla a1 → α1 , ..., an → αn ∈ P takov´a, ˇze, α1 ...αn = v. Znaˇc´ıme to u → v. P´ıˇseme w ⇒∗ z, jestliˇze slovo w lze v koneˇcnˇe mnoha kroc´ıch pˇrepsat na z. Jazykem generovan´ ym syst´emem G naz´ yv´ame jazyk L(G) = {w|w ∈ P∗ ∗ ∧w0 ⇒ w}. Termin´aly se vyv´ıj´ı bez interakce: ai → αi ∈ P, a1 a2 ...an ⇒ α1 α2 ...αn , tj. vˇsechny termin´aly jsou najednou pˇreps´any...paralelismus. V 0L syst´emech mus´ıme m´ıt pravidlo pro kaˇzd´e p´ısmeno. 1
L0L ...mnoˇzina jazyk˚ u, kter´e lze generovat 0L gramatikami k Napˇr.: G = ({a}, {a → aa}, a); L(G) = {a2 } {a, aa} ∈ / L0L Vˇeta: Existuje koneˇcn´ y jazyk, kter´ y nen´ı 0L. D˚ ukaz sporem pomoc´ı jazyka L={a, aa}: 1. Nechˇt w0 = a, tedy a →∗ aa. Je zˇrejm´e, ˇze lze vˇsak tak´e a →∗ a4 , z ˇcehoˇz plyne, ˇze a4 ∈ L(G) a tedy L 6= L(G). 2. Nechˇt w0 = aa, tedy aa →∗ a. Je zˇrejm´e, ˇze lze vˇsak tak´e aa →∗ ǫ, z ˇcehoˇz plyne, ˇze ǫ ∈ L(G) a tedy L 6= L(G). Moˇzno zapojit ot´azku ˇc. 3 a 6.
2
A1. Kapitoly z teorie form´ aln´ıch jazyk˚ u a automat˚ u c
Milan Schwarz (2006)
3) Typy Lindenmayerov´ ych syst´ em˚ u a) 0L-syst´ emy: viz. 2. ot´azka b) D0L-syst´ emy: Oznaˇcuje deterministick´ y syst´em, tj. mezi pˇrepisovac´ımi pravidly neexisP tuj´ı dvˇe r˚ uzn´a pravidla se stejnou levou stranou, tj., kdyˇz ∀a ∈ ∃!(pr´avˇe jedno pravidlo) a → α c) P0L-syst´ emy: P(propagating) oznaˇcuje rozp´ınav´e syst´emy. Na prav´e stranˇe ˇz´adn´eho pravidla nen´ı pr´azdn´e slovo, tj. nedovoluje uˇzit´ı ǫ-pravidla. Mus´ı platit, ˇze nejkratˇs´ı slovo z jazyka je axiom, protoˇze slovo se m˚ uˇze pouze rozˇsiˇrovat. Z axiomu mus´ı b´ yt odvoditeln´e druh´e nejkratˇs´ı slovo z jazyka atd. d) PD0L-syst´ emy: PD0L - nevymaz´avac´ı deterministick´ y 0L-syst´em. Vˇeta: L0L jsou vlastn´ı nadtˇr´ıdou LD0L a LP 0L , tzn. 1)LD0L ⊆ L0L 2)LP 0L ⊆ L0L 3)LP D0L ⊆ LD0L 4)LP D0L ⊆ LP 0L ukazu lze Napˇr. - Vˇeta: Jazyky LD0L a LP 0L jsou neporovnateln´e (jazyky v d˚ totoˇznˇe pouˇz´ıt pro d˚ ukazy 1, 2) 1. Nechˇt G = ({a, b, c}, {a → aa, b → cab, c → ǫ}, b). Je zˇrejm´e, ˇze L(G) je D0L jazyk, kter´ y neobsahuje ǫ. Lze snadno ovˇeˇrit, ˇze L(G) = 2n −2 {b} ∪ {a cab|n ≥ 1}. Pˇredpokl´adejme, ˇze existuje P0L syst´em H = P P ( , P, w0 ) takov´ y, ˇze L(H)=L(G), pak = {a, b, c} a mus´ı w0 = b. P Je zˇrejm´e, ˇze P obsahuje pouze jedin´e pravidlo b → α, α ∈ ∗ , a to b → cab. Pak tedy b ⇒ cab ⇒ a2 cab, z ˇcehoˇz plyne, ˇze a → a a c → a. To znamen´a, ˇze existuje tak´e derivace a2 cab ⇒ a4 cab, tedy a4 cab ∈ L(H), L(H) 6= L(G). L(G) tedy nen´ı P0L jazyk. 2. Nechˇt G = ({a}, {a → a, a → aa}, a). L(G) = {a}+ je P0L jazyk. D0L jazyk nad abecedou {a} m˚ uˇze b´ yt definov´an pouze D0L syst´emem ve tvaru H = ({a}, {a → ak }, ai ). Jazyk generovan´ y D0L syst´emem i∗kn L(H) = {a |n ≥ 0}. Pro ˇz´adnou volbu parametr˚ u i, k neprob´ıh´a funkce f (n) = i ∗ k n vˇsechna pˇrirozen´a ˇc´ısla. Tedy {a}+ nen´ı D0L jazyk. e) E0L-syst´ emy(extended): P P Def.: G = ( , ∆, P, w0 ), kde G′ = ( , P, w0 ) je 0L syst´em a ∆ je termin´aln´ı 1
P
abeceda takov´a, ˇze ∆ ⊆ . Jazyk generovan´ y syst´emem G je definov´an jako L(G) = L(G′ ) ∩ ∆∗ , tj. vybereme pouze termin´aln´ı slova. P P Pˇr.: L = {an bn an |n ≥ 1}, kde G = { , ∆, P, w0 = S}, = {S, A, B, A′ , B ′ , F, a, b}, ∆ = {a, b}, P : S → ABA, A → AA′ , B → BB ′ , A′ → A′ , B ′ → B ′ , F → F, a → F, b → F, A → a, B → b, A′ → a, B ′ → b Vˇeta: L0L ⊆ LE0L ⇒ LEOL−0L = {a, aa} Synchronizovan´ y E0L-syst´ em: P Def.: E0L-syst´em G = ( , ∆, P, w0 ) je synchronizovan´ y, jestliˇze, pro ∀a ∈ ∆ plat´ı, ˇze a ⇒∗ α, kde α ∈ / ∆∗ (jestliˇze odvod´ıme α, tak α nepatˇr´ı do ∆, z termin´alu uˇz neodvod´ıme dalˇs´ı termin´al) P P y 0L-syst´em G = ( , P, w0 ) je i E0L-syst´em G = ( , ∆, P, w0 ); Vˇeta: Kaˇzd´ P P ∆ ⊆ , pr´avˇe tehdy kdyˇz = ∆ ⇒ 0L = E0L. f ) T0L-syst´ emy: P P Def.: G = ( , P, w0 ), kde je koneˇcn´a abeceda, P mnoˇzina tabulek P = P {P1 , ...Pk }, pˇriˇcemˇz ( , Pi , w0 ) je 0L syst´em a z´aroveˇ n v jednom kroku odvozen´ı P∗ lze vˇzdy pouˇz´ıt pouze jednu tabulku; w0 ∈ je startovac´ı axiom syst´emu. 2 4 8 Vˇeta: L0L ⊆ LT 0L ⇒ LT OL−0L = {b , a , a } g) ET0L-syst´ emy: P P P ′ ˇ Def.: Necht G = ( , P, w0 ) je T0L-syst´em a ∆ ⊆ . Syst´em G = ( , ∆, P, w0 ) naz´ yv´ame ETOL-syst´emem, kde L(G) = L(G′ ) ∩ ∆∗ (kde ∆ je koncov´a abeceda). Pˇr.:L(G) = {an , bm , an |n ≥ 0, m ≥ n}, G = ({a, b, c, d}, {a, b}, P, cd), kde P : {a → a, b → b, c → acb, d → da}, {a → a, b → b, c → cb, d → d}, {a → a, b → b, c → ǫ, d → ǫ} h) Interaktivn´ı syst´ emy: Viz. ot´azka ˇc. 6.
2
A1. Kapitoly z teorie form´ aln´ıch jazyk˚ u a automat˚ u c
Milan Schwarz (2006)
4) E0L syst´ emy a tˇ r´ıdy jazyk˚ u Chomsk´ eho hierarchie E0L-syst´ emy: viz. 3. ot´azka (moˇznost definovat PE0L, DE0L, PDE0L podobnˇe jako pro 0L jazyky) Chomsk´ eho hierarchie: viz. 1. ot´azka y koneˇcn´ y jazyk je E0L jazyk (kaˇzd´ y koneˇcn´ y jazyk je regul´arn´ı). Vˇeta: Kaˇzd´ P ˇ D˚ ukaz: Necht L = {αi |1 ≤ i ≤ n} je koneˇcn´ y jazyk nad abecedou a nechˇt P P S∈ / .Nechˇt G = ( ∪{S}, ∆, P, w0 ) je E0L syst´em, kde P = {S → αi |1 ≤ P i ≤ n} ∪ {a → a|a ∈ } . Potom L=L(G). Jedin´ y koneˇcn´ y jazyk, kter´ y nen´ı v poˇzadovan´e formˇe, je pr´azdn´ y jazyk. Ten je generovan´ y PDE0L syst´emem. y, potom je tento jazyk L tak E0LVˇeta: Jestliˇze jazyk L je bezkontextov´ jazyk. LBK ⊆ LE0L ⊆ LK . D˚ ukaz: 1. Nechˇt G = (N, T, P, S) je bezkontextov´a gramatika, kde L(G) = L ∈ LBK . Pak LE0L (G′ ) = L(G), kde G′ = (N ∪ T, T, P ∪ {a → a|a ∈ T }, S) 2. L ∈ LE0L−BK ; L = {ai bi ci |i > 0}: G = {{S, A, B, C, A′ , B ′ , C ′ , F, a, b, c}, {a, b, c}, P, S},P : S → ABC, A → AA′ , B → BB ′ , C → CC ′ , A′ → A′ , B ′ → B ′ , C ′ → C ′ , F → F, a → F, b → F, c → F, A → a, B → b, C → c, A′ → a, B ′ → b, C ′ → c Vˇeta (Uz´avˇerov´e vlastnosti E0L): Jestliˇze L1 , L2 jsou E0L jazyky, pak jsou ∗ tak´e E0L jazyky L1 ∪ L2 , L1 L2 , L+ 1 , L1 . y E0L syst´em G1 = D˚ ukaz: Jestliˇze L1 a L2 ∈ LE0L , existuje synchronizovan´ P P y, ˇze L(G1 ) = L1 a L(G2 ) = ( 1 , ∆1 , P1 , w1 ) a G2 = ( 2 , ∆2 , P2 , w2 ) takov´ P L2 . Potom m˚ uˇzeme vybrat G1 a G2 takov´ ym zp˚ usobem, ˇze ( 1 −∆2 ) ∩ P ˇ S, S1 , S2 symboly nepatˇr´ıc´ı do P1 ∪ P2 . ( 2 −∆2 ) = ⊘. Bud P
1. L1 ∪ L2 = L(G), kde G = ( w1 , S → w2 }, S) P
1
∪
P
P
2
∪{S}, ∆1 ∪ ∆2 , P1 ∪ P2 ∪ {S →
2. L1 L2 = L(G), kde G = ( 1 ∪ 2 ∪{S, S1 , S2 }, ∆1 ∪ ∆2 , P1 ∪ P2 ∪ {S → S1 S2 , S1 → S1 , S2 → S2 , S1 → w1 , S2 → w2 }, S) 1
P
3. L+ 1 = L(G), kde G = (
∪{S}, ∆1 , P1 ∪{S → SS, S → S, S → w1 }, S)
1
P
4. L∗1 = L(G), kde G = ( w1 , S → ǫ}, S)
1
∪{S}, ∆1 , P1 ∪ {S → SS, S → S, S →
2
A1. Kapitoly z teorie form´ aln´ıch jazyk˚ u a automat˚ u c
Milan Schwarz (2006)
5) T0L syst´ emy, stupeˇ n synchronizace a determinismu P
P
Def.: G = ( , P, w0 ), kde je koneˇcn´a abeceda, P mnoˇzina tabulek P P = {P1 , ...Pk }, pˇriˇcemˇz ( , Pi , w0 ) je 0L syst´em a z´aroveˇ n v jednom kroku P∗ odvozen´ı lze vˇzdy pouˇz´ıt pouze jednu tabulku; w0 ∈ je startovac´ı axiom syst´emu. ˇ G = (P, P, w0 ) T0L syst´em, bud ˇ x = a1 ...an slovo nad abeceDef.: Bud P P ∗ ˇy∈ dou , n ≥ 0, pro 1 ≤ j ≤ n, bud . Z x lze pˇr´ımo odvodit y, plat´ı-li y = α1 α2 ...αn tak, ˇze existuje p ∈ P a existuje (a1 → α1 , a2 → α2 , ..., an → αn ) ∈ p. P Def.: T0L syst´em G = ( , P, w0 ) se naz´ yv´a nevymaz´avaj´ıc´ı, jestliˇze ˇz´adn´a mnoˇzina pravidel p ∈ P neobsahuje pravidla typu a → ǫ. P Def.: syst´em G = ( , P, w0 ) se naz´ yv´a deterministick´ y, jestliˇze pro kaˇzd´e P P p ∈ P a pro kaˇzd´e a ∈ existuje pr´avˇe jedno pravidlo a → α, α ∈ ∗ . ˇ G = (P, P, w0 ) T0L syst´em: Def.: Bud 1. stupeˇ n synchronizace T0L syst´emu G oznaˇcujeme Syn G a je roven poˇctu tabulek n´aleˇz´ıc´ıch P , tedy Syn G = |P |. ˇa∈ 2. Bud
P
, p ∈ P , oznaˇcme A(a, p) = {α|a →p α}
• stupeˇ n nedeterminismu p´ısmene a vzhledem k tabulce p je DetG (a, p) = |A(a, p)| • stupeˇ n nedeterminismu tabulky p je DetG p = maxa∈P DetG (a, p) • stupeˇ n nedeterminismu syst´emu G je Det G = maxp∈P DetG p ˇ L T0L jazyk: Def.: Bud 1. stupeˇ n synchronizace L je Syn L = min{Syn G|L(G) = L} 2. stupeˇ n nedeterminismu L je Det L = min{Det G|L(G) = L} Pozn.: T0L jazyk L je deterministick´ y, tehdy a jen tehdy, kdyˇz Det L = 1. Pˇr.: Pro libovoln´e kladn´e ˇc´ıslo k, definujme jazyk Lk = {b, a, a2 , ..., ak }. 1. Lk = L(G), kde G je T0L syst´em ({a, b}, {b → a, b → a2 , ..., b → ak , a → a}, b). Syn G = 1, Det G = k, tud´ıˇz Syn Lk = 1, Det Lk ≤ k. 1
2. Lk = L(H), kde H je T0L syst´em ({a, b}, {b → a, a → a}, {b → a2 , a → a}, ..., {b → ak , a → a}, b). Syn H = k, Det H = 1, tud´ıˇz Syn Lk ≤ k, Det Lk = 1. 3. z bod˚ u 1,2 plyne, ˇze Syn Lk = 1 a Det Lk = 1 ych pˇrirozen´ ych ˇc´ısel k, l existuje koneˇcn´ y Vˇeta: Pro kaˇzdou dvojici kladn´ T0L jazyk Lk,l , kde: Det Lk,l = k, Syn Lk,l = l. Vˇeta: L0L ⊆ LT 0L ⇒ LT OL−0L = {b2 , a4 , a8 }
2
A1. Kapitoly z teorie formálních jazyků a automatů © Milan Schwarz (2006)
6) Interaktivní systémy, vliv velikosti interakce na generativní sílu. ǯDZȱµȱ k, l ȱ£¤¤ȱ¤ȱ²Çǯȱ
k, l systém (nazýváme také IL systém) je čtveřice G = Σ, P, g , ω , kde Σ je konečná abeceda, ω ∈ Σ * je axiom, g ∉ Σ je značkovací symbol (zarážka).
P je konečná neprázdná množina pravidel, P ⊂ (Σ ∪ {g }) × Σ × (Σ ∪ {g }) × Σ* taková, že k
l
(1) pro w1 , a, w3 , w4 ∈ P platí: (1.1)
jestliže w1 = w 1 g w 1 pro libovolné w 1 , w 1 ∈ (Σ ∪ {g })
(1.2)
jestliže w3 = w 3 g w 3 pro libovolné w 3 , w 3 ∈ (Σ ∪ {g })
*
a (2) pro každé
*
w1 , a, w3 ∈ (Σ ∪ {g }) × Σ × (Σ ∪ {g }) k
l
pak w 1 ∈ {g } , *
,
,
pak w 3 ∈ {g } , *
takové, že w1 a w3 splňují
podmínky (1.1) a (1.2), existuje w4 ∈ Σ * takové, že w1 , a, w3 , w4 ∈ P. Jestliže w1 , a, w3 , w4 ∈ P , značíme w1 , a, w3 → w4 nebo také w1 , a, w3 → w4 . P
Buď k číslo, m ≥ k ≥ 0 . Pro slovo w = a1 a 2 ...a m je Suf k ( w) = a m −( m − k )+1 a m −( m − k )+ 2 ...a m a Pref k ( w) = a1 a 2 ...a k .
Def.: Buď G = Σ, P, g , ω IL systém, x = a1 ...a m ∈ Σ * a y ∈ Σ * . Z x = a1 ,..., a m lze přímo odvodit y (značíme x ⇒ y ), platí-li: y = α 1 ...α m , kde G
g , a1 , Pr ef l (a 2 ...a m g ) → α 1 , k
l
P
Suf k ( g a1 ), a 2 , Pr ef l (a3 ...a m g l ) → α 2 , k
P
… Suf k ( g k a1 ...a m −1 ), a m , g l → α m . P
Def.: Buď G = Σ, P, g , ω IL systém. Jazyk generovaný IL systémem G , značíme L(G ) , je *
definován: L(G ) = { x ∈ Σ * ω ⇒ x }. G
Def.: Buďte k , l nezáporná celá čísla. Jestliže L je jazyk takový, že existuje IL systém G , pro který platí L(G ) = L , pak L se nazývá IL jazyk. Def.: Buď G = Σ, P, g , ω IL systém:
A1.6
1
i) G se nazývá nevymazávající (PIL), jestliže ω ≠ λ a pro každé w1 , w2 , w3 , w4 ∈ P je w4 ≠ λ . ii) G se nazývá deterministický (DIL), jestliže pro každou trojici w1 , a, w3 existuje jediné pravidlo w4 ∈ Σ * takové, že w1 , a, w3 → w4 ∈ P.
Př.: L(G ) = {c, ba} ∪ { a 2 P:
n
n ≥ 1} , G = {a, b, c}, P, g , c ,
1. x, a, λ → a 2 , x ∈ {a, c, g }, 2. b, a, λ → a ,
3. x, c, λ → ba, x ∈ {a, b, c, g}, 4. x, c, λ → a 2 , x ∈ {a, b, c, g }, 5. x, b, λ → b, x ∈ {a, b, c, g}.
Postupným derivováním axiomu c získáme slova: 5, 2
3
5, 2
5, 2
5, 2
a) pokud použijeme jako první 3. pravidlo: c ⇒ ba ⇒ ba ⇒ ba ⇒ ... ⇒ ba 4
2
1,1
4
1,1,1,1
12
( n − 1)
b) pokud použijeme jako první 4. pravidlo: c ⇒ a ⇒ a ⇒ ... ⇒ a 2
n
Věta: Platí následující diagram
F (4L) F (<3,0 >L)
F (3L)
F (<0,3>L)
F (<2,0 >L)
F (2L)
F (<0,2>L)
F (<1,0 >L)
F (<0,1>L)
F (0L) Diagram ilustruje vztahy mezi všemi třídy IL jazyků. Všechny inkluze vyplývají z lemma 1, věty 1 a 2. Lemma 1: Jestliže pro nezáporná celá čísla k1 , k 2 , l1 , l 2 platí k1 ≤ k 2 a l1 ≤ l 2 , pak
F ( k1 , l1 ) ⊂ F ( k 2 , l 2 ) .
Věta 1:Nechť k , k ′, l , l ′ jsou celá čísla taková, že 0 ≤ k ′ ≤ k , 0 ≤ l ′ ≤ l a k ′ + l ′ < k + l. Pak F ( k ′, l ′ )⊂ F ( k , l ). ≠ Věta 2: Pro libovolnou dvojici kladných celých čísel k a l platí, že F ( k ,0 ) a F jsou neporovnatelné, ale ne disjunktní. Důkazy k těmto větám jsou masíčko - jestli má někdo zájem, klidně poskytnu:-)
A1.6
2
( 0, l )
A1. Kapitoly z teorie formálních jazyků a automatů © Milan Schwarz (2006)
7) Maticové gramatiky. Definice, příklady, základní poznatky. Maticová gramatika: ǯDZ¤ȱȱȱ²ìȱ G = ( N,T,S , M ) ǰȱȱ - N je množina neterminálních symbolů, - T je množina terminálních symbolů, - S je startovací symbol, - M = {m1 , m2 , K , mn } , n ≥ 1 , je konečná množina sekvencí mi = ( pi 1 , K , pi k (i ) ) , k (i ) ≥ 1 , 1 ≤ i ≤ n ,
kde všechna pi j , 1 ≤ i ≤ n , 1 ≤ j ≤ k (i ) , jsou bezkontextová pravidla,
Def.: Pro mi , 1 ≤ i ≤ n , a x, y ∈ VG∗ , definujeme x ⇒ mi y jako
x = x0 ⇒ pi 1 x1 ⇒ pi 2 x 2 ⇒ pi 3 K ⇒ pi k ( i ) y ,
kde mi = ( p i 1 , K , p i k (i ) ) ∈ M .
Def.: Jazyk L(G ) generovaný gramatikou G je definován jako množina všech slov w ∈ T ∗ takových, že existuje derivace S ⇒ m j 1 y1 ⇒ m j 2 y 2 ⇒ m j 3 K ⇒ m j s w , pro nějaké s ≥ 1 , 1 ≤ ji ≤ n , 1 ≤ i ≤ s . Př.: L(G) = {aibici: i ≥ 1}∉ do množiny jazyků generovaných bezkontextovými gramatikami m1: (S → ABC) ⇒ zvýšení generativní síly m2: (A → aA, B → bB, C → cC) … bezkontextové pravidla m3: (A → a, B → b, C → c)
Maticová gramatika s testováním výskytu: Def.: Maticová gramatika s testováním výskytu (matrix grammar with appearance checking) je pětice G = ( N,T,S , M , F ) , kde - N, T, S, M jsou definovány stejně jako v maticové gramatice v předchozí definici, - F je podmnožina množiny všech pravidel v maticích, tzn. F ⊆ pi j 1 ≤ i ≤ n, 1 ≤ j ≤ k (i ) .
{
}
Def.: Pro mi , 1 ≤ i ≤ n , a x, y ∈ VG∗ , definujeme x ⇒ amci y jako x = x0 ⇒ apci x1 ⇒ apci x2 ⇒ apci K ⇒ apci 1
2
3
k (i )
y,
Def.: Jazyk L(G ) generovaný maticovou gramatikou G s testováním výskytu je definován jako množina všech slov w ∈ T ∗ takových, že existuje derivace
A1.7
1
S ⇒ amcj y1 ⇒ amcj y2 ⇒ amcj K ⇒ amcj w , 1
2
3
s
pro nějaké s ≥ 1 , 1 ≤ ji ≤ n , 1 ≤ i ≤ s .
Def.: G je maticová gramatika bez testování výskytu právě tehdy, když F = 0/ . Př.: L(G ) = a n b m c n d m n, m ≥ 1
{
}
G = ({S , A, B, C , D}, {a, b, c, d }, {m1 ,K, m4 }, S ,0/ ) m1 = ( A → aA, C → cC ) m2 = ( A → a, B → b, C → c, D → d ) m3 = (S → ABCD ) m4 = (B → bB, D → dD )
{
}
Př.: L = a 2 n ≥ 0 ∈ L M a c n
G = ({A, U , X , Y , Z }, {a}, X , {m1 , K , m5 }, {X → U , Y → U , Z → U , A → U })
m1 = (Y → U , A → U , X → ZZ ) m3 = ( X → U , Z → Y ) m4 = ( X → U , A → a )
m2 = (Y → U , Z → U , X → A) m 5 = (Z → U , Y → X )
Jestliže jsou všechny matice maticové gramatiky jednoprvkové, jedná se o běžnou bezkontextovou gramatiku. Tedy ke každé bezkontextové gramatice existuje maticová gramatika. Z toho plyne L (CF ) ⊆ L (M ) , kde L (CF ) je rodina jazyků příslušných rodině bezkontextových gramatik a L (M ) je rodina jazyků příslušných rodině maticových gramatik. Jestliže v odvozovaném slově existuje terminál, jehož pravidlo se nachází v množině F, musíme toto pravidlo aplikovat (není tedy možné toto pravidlo vynechat).
A1.7
2
A1. Kapitoly z teorie formálních jazyků a automatů © Milan Schwarz (2006)
8) Programové gramatiky a gramatiky s náhodným kontextem. Definice, příklady, základní poznatky. Programové gramatiky: Def.: G = (N, T, P, S), kde - N je konečná množina neterminálů; - T je konečná množina terminálů; - S je startovací symbol; - P: (r: A →α, σ(r), ϕ(r)) ∈ P; Zn(P) je množina značek pravidel taková, že σ(r) ⊆ Zn(P), ϕ(r) ⊆ Zn(P) Def. (Krok odvození): x se za použití pravidel se značkou r1 přepíše na (y, r2), tedy (x, r1) ⇒ (y, r2), kde r1, r2∈ Zn(P); (r1: A→α, σ(r1), ϕ(r2)) pak: 1.) jestliže x je tvaru x = x1A1y1, pak y = x1α1y1 a r2∈ P(r1) (r2 je jedno z pravidel z σ(r1)) 2.) y = x r2∈ σ(r1) … jestliže nelze pravidlem r1 přepsat x, nepřepíšeme ho, ale další použité pravidlo bude z σ(r1) Def.: Jazykem generovaný programovanou gramatikou G nazýváme jazyk L(G) = { w∈ T*; (S, r1) ⇒* (w, r2), r1, r2 ∈ Zn(P)}. Pozn.: Dokážeme generovat jazyky bohatší než jazyky bezkontextové. Př.:L(G) = {an bn cn: n ≥ 1},G=({S,A,B,C},{a,b,c},{r1,r2,...,r7},S) je to lineární jazyk,ale není bezkontextový (r1: S → ABC, {r2, r5}, ∅) …r1 je značka pravidla, {r1, r2} je to, co se použije po aplikaci r1 (r2: A → aA, {r3}, ∅) tvoří iteraci k jednotlivým písmenům (r3: B → bB, {r4}, ∅) (r4: C → cC, {r2, r5}, ∅) (r5: A → a, {r6}, ∅) (r6: B → b, {r7}, ∅) ∅, tj. prázdná množina, znamená, že v případě neúspěchu nemůžeme (r7: C → c, ∅, ∅) pokračovat Př.: L(G) = {a2na n-tou: n ≥ 1} …složitější kontextový jazyk (r1: S → AA, {r1}, {r2, r3}) {r2, r3} jsou „zamítací“ pravidla (r2: A → S, {r2}, {r1}) (r3: A → a, {r3}, ∅) (r3: A → a, {r3}, ∅) nutí k paralelismu na jedno písmeno
Gramatiky s náhodným kontextem: Def.: G = (N, T, P, S), kde - N je konečná množina neterminálů; - T je konečná množina terminálů; - S je startovací symbol; - P: pravidlo má takovouto podobu (A →α, Q, R); R, Q ⊆ N (R a Q je množina neterminálních symbolů).
A1.8
1
Def.(Krok odvození): x se přepíše na y x⇒y, x = x´Ax´´ a y = x´αx´´; x´, x´´ obsahuje všechny písmena z Q a neobsahují žádný symbol z R. Q je tedy tzv. přítomný kontext a R nazýváme nepřítomným kontextem. Pozn.: Vygenerujeme každý bezkontextový jazyk. Př.: L(G) = {an bn cn: n ≥ 1}, G=({S,A,B,C},{a,b,c},{r1,r2,...,r7},S) (S → ABC, ∅, ∅) ∅, ∅… nemám žádný kontext, přepisuji S (A → aA´, {B}, ∅) {B} je to, co máme ve větné formě (B → bB´, {C}, ∅) (C → cC´, {A´}, ∅) (A´ → A, {B´}, ∅) (B´ → B, {C´}, ∅) (C´ → C, {A}, ∅) (A → a, {B}, ∅) (B → b, {C}, ∅) (C → c, ∅, ∅) ∅, ∅ … nekontrolujeme žádný neterminál
A1.8
2
A1. Kapitoly z teorie form´ aln´ıch jazyk˚ u a automat˚ u c
Milan Schwarz (2006)
9) Regulovan´ e L-syst´ emy - budeme pouˇz´ıvat tabulkov´e TOL syst´emy (viz 5. ot´azka) a) Maticov´ y TOL syst´ em (MT0L) P Def.: Maticov´ ym T0L-syst´emem budeme naz´ yvat kaˇzdou ˇctveˇrici G = ( , P, M, w0 ), P kde ( , P, w0 ) je T0L syst´em, M = {m1 , m2 , ..., mn }, M je matice, tj. koneˇcn´a mnoˇzina posloupnost´ı mi = (i1 , i2 , ..., iki ); 1 ≤ i ≤ s, 1 ≤ it ≤ k Def. (krok odvozen´ı): x ⇒mi y, x = x1 ⇒Pi1 x2 ⇒Pi2 x3 ⇒ ... ⇒ xki ⇒Pki y. L(G) = {w|w0 ⇒mi1 w1 ⇒mi2 w2 ⇒ ... ⇒mit wr ⇒Pi1 w1′ ⇒Pi2 w2′ ⇒ ... ⇒ wr′ ; r ≤ ki } - pˇri posledn´ım odvozen´ı nemus´ıme pouˇz´ıt vˇsechna pravidla z pˇr´ısluˇsn´e tabulky pouˇzit´e jako posledn´ı. Vˇeta: LT 0L ⊆ LP DM T 0L ; LP DM T 0L−T 0L = {a2 , a4 , b4 }, G = ({a, b}, {P1 , P2 }, {{1, 2}}, a2 ), P1 = {a → a2 , b → b}, P2 = {a → b, b → b} LDM T 0L ⊆ LP T 0L ; LP T 0L−DM T 0L = {an |n ≥ 1}, P1 = {a → a, a → aa} y na ∪,∩,.,+,bez ǫ homomorfismus,inverzn´ı Vˇeta: LM T 0L syst´em nen´ı uzavˇren´ homomorfismus n m / LM T 0L D˚ ukaz(∪): L = {a2 |n ≥ 1}, L′ = {b3 |m ≥ 1}; L ∪ L′ ∈ k 2k0 i2 0 2k0 s a ⇒ b ; i 6= 3 n m D˚ ukaz(.): L = {a2 |n ≥ 1} je 0L. L′ = {ab2 |m ≥ 1} je 0L. L.L′ ∈ / LM T 0L = 2n +1 2m {a b |m, n ≥ 1} P : (a → ai , b → bj ) m 2m m 2m a3 b2 ⇒ a3 bj , a3 b2 ⇒ a6 bj , napˇr. a5 bt nelze vygenerovat! b) Programov´ y TOL syst´ em Def.: Programov´ ym T0L-syst´emem budeme naz´ yvat kaˇzdou trojici G = P ( , P, w0 ), kde: σ(p) ≤ P , p ∈ P ; w0 ⇒Pi1 w1 ⇒Pi2 w2 ⇒ ... ⇒ Pij+1 ∈ σ(Pij ) c) TOL syst´ em s n´ ahodn´ ym kontextem Def.: T0L-syst´emem s n´ahodn´ ym kontextem budeme naz´ yvat kaˇzdou trojici P G = ( , P, w0 ), kde: P p ∈ P ; Q ⊆ ; w0 ⇒Pi1 w1 ⇒Pi2 w2 ⇒ ... ⇒ Def.(krok odvozen´ı): x ⇒P y, pokud se v x vyskytuj´ı vˇsechna p´ısmena z mnoˇziny Q.
1
