Gramatické systémy - teorie a aplikace

Gramatick´e syst´emy - teorie a aplikace Ludˇek Dol´ıhal January 8, 2010

Contents ´ 1 Uvod 1.1 Teorie gramatick´ ych syst´em˚ u . . . . . . . . . . . . . . . . . . . .

2 2

2 CD 2.1 2.2 2.3 2.4 2.5 2.6

gramatick´ e syst´ emy Definice . . . . . . . . . . . . . Pˇr´ıklad . . . . . . . . . . . . . Generativn´ı s´ıla . . . . . . . . . Hybridn´ı syst´emy . . . . . . . . T´ ymov´ y CD gramatick´ y syst´em Aplikace v praxi . . . . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

3 3 4 6 7 7 7

3 PC 3.1 3.2 3.3 3.4 3.5

gramatick´ e syst´ emy Definice . . . . . . . . . . . . . . . . . . . . Pˇr´ıklady . . . . . . . . . . . . . . . . . . . . Nesynchronizovan´e PC gramatick´e syst´emy Gramatick´e syst´emy s komunikac´ı na pˇr´ıkaz Aplikace v praxi . . . . . . . . . . . . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

. . . . .

8 8 11 12 13 14

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

. . . . . .

4 Pˇ r´ıbuzn´ e modely 16 4.1 Eco gramatiky . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16 4.2 Test tube syst´emy . . . . . . . . . . . . . . . . . . . . . . . . . . 18 5 Z´ avˇ er

18

Literatura

19

Seznam zkratek a symbol˚ u

20

1

´ Uvod

1

C´ılem t´eto pr´ace je diskutovat problematiku gramatick´ ych syst´em˚ u ve vztahu k modern´ım programovac´ım metod´ am a jazyk˚ um. Bude pˇredestˇreno teoretick´e pozad´ı gramatick´ ych syst´em˚ u a nˇekter´ ych pˇr´ıbuzn´ ych model˚ u. Detailnˇe budou probr´ any dva z´ akladn´ı typy gramatick´ ych syst´em˚ u a to CD gramatick´e syst´emy a PC gramatick´e syst´emy. Pokus´ım se popsat aplikaci tˇechto syst´em˚ u v praxi a naj´ıt pˇr´ıklady jejich re´ aln´eho vyuˇzit´ı.

1.1

Teorie gramatick´ ych syst´ em˚ u

V bˇeˇzn´e teorii programovac´ıch jazyk˚ u je v´ ypoˇcet prov´adˇen jednou v´ ypoˇcetn´ı jednotkou. To znamen´ a, ˇze jazyk je generov´an jednou gramatikou a pˇrij´ım´ an jedn´ım automatem. Nicm´enˇe v dneˇsn´ı dobˇe hraje st´ale vˇetˇs´ı roli distribuovan´e zpracov´an´ı. Takov´eto syst´emy si vˇsak nevystaˇc´ı se z´ akladn´ı teori´ı programovac´ıch jazyk˚ u. Jsou potˇreba prostˇredky pro z´ apis paralelismu, distribuov´an´ı v´ ypoˇctu, konkurence a jin´ ych. Proto byly zavedeny gramatick´e syst´emy. Gramatick´e syst´emy ve sv´e podstatˇe pˇredstavuj´ı mnoˇzinu gramatik pracuj´ıc´ıch pohromadˇe. Pokud bˇeˇz´ı v´ ypoˇcet na v´ıce stanic´ıch, jsou stanice synchronizov´any pomoc´ı protokolu tak, aby produkovaly jeden jazyk. D˚ uvod˚ u, proˇc se ˇ pˇreklad dˇeje na v´ıce m´ıstech, m˚ uˇze b´ yt cel´ a ˇrada. Uvedme napˇr´ıklad v´ ypoˇcetn´ı n´ aroˇcnost nebo zv´ yˇsen´ı generativn´ı s´ıly. Je jasn´e, ˇze kl´ıˇcovou roli zde bude hr´at pr´avˇe souhra jednotliv´ ych prvk˚ u mnoˇziny. Rozliˇsuj´ı se dva z´ akladn´ı typy gramatick´ ych syst´em˚ u. ♦ sekvenˇcn´ı ♦ paraleln´ı CD gramatick´e syst´emy[6] jsou syst´emy sekvenˇcn´ı. V´ yznam zkratky, stejnˇe jako zkratky PC pouˇzit´e o odstavec n´ıˇze, si m˚ uˇzete naj´ıt v seznamu zkratek, kter´ y je um´ıstˇen na konci pr´ace. D˚ uleˇzit´ ym faktem, kter´ y odliˇsuje tento syst´em od syst´emu PC je to, ˇze vˇsechny ˇca´sti syst´emu maj´ı spoleˇcnou vˇetnou formu. Aktivn´ı je vˇzdy pouze jedna gramatika, a to ta, kter´ a pr´avˇe pracuje na spoleˇcn´e vˇetn´e formˇe. V takov´emto syst´emu jsou nutn´e nˇejak´e prvky, kter´e ud´ avaj´ı, kdy se pr´avˇe aktivn´ı gramatika stane neaktivn´ı a pˇred´ a ˇr´ızen´ı a vˇetnou formu gramatice jin´e. Kter´e, o to se postar´ a protokol. Pˇr´ıkladem takov´ ychto stop prvk˚ u mohou b´ yt napˇr´ıklad z´ avorky nebo if podm´ınka. Nebo lze tak´e ˇr´ıci, ˇze dan´a gramatika bude pracovat pr´avˇe k krok˚ u. Naproti tomu PC gramatick´e syst´emy[6] jsou paraleln´ı. Zde m´a kaˇzd´ a gramatika svou vlastn´ı vˇetnou formu a mohou tedy vˇsechny pracovat paralelnˇe, kaˇzd´ a na sv´e vlastn´ı vˇetn´e formˇe. V tomto typu gramatick´ ych syst´em˚ u je nutn´ y glob´ aln´ı ˇcasovaˇc. Takt´eˇz je velmi podstatn´ a existence takzvan´ ych dotazovac´ıch (query) symbol˚ u. Jejich funkce je n´ asleduj´ıc´ı. Pokud ˇca´st i vygeneruje symbol Qj , pak aktu´aln´ı vˇetn´ a forma komponenty j je zasl´ana ˇca´sti i, kde nahrad´ı vˇsechny v´ yskyty Qj . V kaˇzd´em PC syst´emu existuje jedna komponenta, kter´ a

2

m´a status master, a jazyk generovan´ y touto komponentou je jazyk generovan´ y cel´ ym syst´emem.

2

CD gramatick´ e syst´ emy

Nyn´ı se pod´ıvejme bl´ıˇze na CD gramatick´e syst´emy. Abychom si mohli nadefinovat CD gramatick´ y syst´em, mus´ıme si nejdˇr´ıve nadefinovat gramatiku samotnou. Gramatika G je tedy ˇctveˇrice G = (N, Σ, P, S), kde 1. N je koneˇcn´ a mnoˇzina non termin´aln´ıch symbol˚ u 2. Σ je koneˇcn´ a mnoˇzina termin´aln´ıch symbol˚ u 3. P je koneˇcn´ a mnoˇzina kart´ezsk´eho souˇcinu (N ∪ Σ)∗ N.(N ∪ Σ)∗ × (N ∪ Σ)∗ 4. S∈N je startovac´ı symbol gramatiky G

2.1

Definice

Pokud tedy m´ame definici gramatiky, m˚ uˇzeme si nadefinovat gramatick´ y syst´em. CD gramatick´ y syst´em nadefinujeme n´ asledovnˇe: CD gramatick´ y syst´em stupnˇe n, n≥ 1 je n-tice Γ = (N, T, S, P1 , ..., Pn ) kde N a T jsou disjunktn´ı abecedy, S ∈ N a P1 , ...., Pn jsou koneˇcn´e mnoˇziny pˇrepisovac´ıch pravidel nad N ∪ T. N je mnoˇzina netermin´ alu a T je mnoˇzina termin´ al˚ u. P1 , ...., Pn jsou naz´ yv´ any komponenty syst´emu. Jeˇstˇe, neˇz pˇrejdeme k definici jazyka, kter´ y je generov´an dan´ ym gramatick´ ym syst´emem, mus´ıme si nadefinovat derivaˇcn´ı krok. Derivaˇcn´ı kroky jsou totiˇz celkem ˇctyˇri. Uvedeme si vˇsechny. Nechˇt Γ = (N, T, S, P1 , ..., Pn ) je CD gramatick´ y syst´em. 1. Pro kaˇzd´e i ∈ 1, ..., n koncov´ y derivaˇcn´ı krok, proveden´ y i-tou komponentou, znaˇcen´ y =⇒tP i je definov´an n´ asledovnˇe: x =⇒tP i y pokud x =⇒∗P i y a neexistuje ˇza´dn´e z ∈ V∗ takov´e, ˇze y =⇒P i z. 2. Pro kaˇzd´e i ∈ 1, ..., n k-krokov´a derivace, proveden´ a i-tou komponentou, znaˇcen´ a =⇒=k je definov´ a na n´ a sledovnˇ e : Pi x =⇒=k ı x1 , ..., xk ∈ (N cupT )∗ takov´e, ˇze P i y pokud existuj´ x = x1 , y = yk+1 , a pro kaˇzd´e 1 ≤ j ≤ k, x =⇒P i xj+1 . 3. Pro kaˇzd´e i ∈ 1, ..., n nejv´ yˇse k-krokov´a derivace, proveden´ a i-tou komponentou, znaˇcen´ a =⇒≤k je definov´ a na n´ a sledovnˇ e : Pi 3

=k x =⇒≤k ejak´e k ′ ≤ k. P i y pokud x =⇒P i y pro nˇ ′

4. Pro kaˇzd´e i ∈ 1, ..., n nejm´enˇe k-krokov´a derivace, proveden´ a i-tou komponentou, znaˇcen´ a =⇒≥k ana n´ asledovnˇe: P i je definov´ =k′ x =⇒≥k ejak´e k ′ ≥ k. P i y pokud x =⇒P i y pro nˇ S´emantika t´eto notace je docela jednoduch´ a. Pokud pracujeme v t- m´odu, mus´ı kaˇzd´ a komponenta pˇrispˇet k ˇreˇsen´ı probl´emu pr´avˇe tak dlouho, dokud m˚ uˇze. V k- m´odu udˇel´ a komponenta pr´avˇe k po sobˇe jdouc´ıch krok˚ u. V dalˇs´ıch dvou m´odech je udˇel´ ano alespoˇ n k nebo maxim´ alnˇe k krok˚ u. V *-m´odu z˚ ustane komponenta u prov´adˇen´ı krok˚ u tak dlouho, jak potˇrebuje. Nyn´ı pˇrejdˇeme k definici jazyka generovan´eho dan´ ym syst´emem. Nejdˇr´ıve nadefinujme mnoˇzinu D n´ asledovnˇe: D= {∗, t} ∪ {≤ k, ≥ k, = k|k ≥ 1} Jazyk generovan´ y CD gramatick´ ym syst´emem Γ = (N, T, S, P1 , ..., Pn ) v derivaˇcn´ım m´odu f ∈ D je Lf (Γ) = {w ∈ T ∗ |S =⇒fP i1 w1 =⇒fP i2 ... =⇒fP im wm = w, m ≥ 1, 1 ≤ ij ≤ n, 1 ≤ j ≤ m}.

2.2

Pˇ r´ıklad

Z definice v´ yˇse vypl´ yv´ a, ˇze v Γ je obsaˇzeno nˇekolik jazyk˚ u. Kter´ a z komponent bude pouˇzita, je urˇceno na z´ akladˇe podm´ınek v D. Komponenta Pi zaˇcne pracovat v momentˇe, kdy se v ˇretˇezci w objev´ı lev´a strana pravidla z Pi . Na zaˇca´tku je nedeterministicky urˇceno, kter´ a komponenta zaˇcne pracovat. Uvaˇzujme n´ asleduj´ıc´ı pˇr´ıklad. M´ ame n´ asleduj´ıc´ı gramatick´e syst´emy: Γ1 = ({S, A, A′ , B, B ′ }, {a, b, c}, S, P1 , P2 ), P1 = {S → S, S → AB, A′ → A, B ′ → B}, P2 = {A → aA′ b, B → cB ′ , A → ab, B → c}. Γ2 = ({S, A}, {a}, S, P1, P2 , P3 ), P1 = {S → AA}, P2 = {A → S}, P3 = {A → a}. Γ3 = ({S, A1 , ..., Ak , A′1 , ..., A′k }, {a, b}, S, P1 , P2 ), P1 = {S → S, S → A1 bA2 b...bAk b} ∪ {A′i → Ai |1 ≤ i ≤ k},

4

P2 = {Ai → aA′i a, Ai → aba|1 ≤ i ≤ k}, K ≥ 1. Γ4 = ({S, S ′ } ∪ {Ai , A′i , A′′i |1 ≤ i ≤ k}, {a, b}, S, P0 , P1 , ..., P3k ), P0 = {S → S ′ , S ′ → A1 bA2 b...bAk b}, P1 = {A1 → A1 , A1 → aA′1 a}, Pi+1 = {A′i → A′′i , Ai+1 → aA′i+1 a}, 1 ≤ i ≤ k − 1, Pk+1 = {A′k → A′′k , A′′1 → A′1 }, Pk+i+1 = {A′i → Ai , A′′i+1 → A′i+1 }, 1 ≤ i ≤ k − 2, P2k = {A′k−1 → Ak−1 , A′′k → Ak }, P2k+i = {Ai → Ai , Ai → aba}, 1 ≤ i ≤ k, k ≤ 2. Γ5 = ({S, A, A′ }, {a, b}, S, P1, P2 , P3 ), P1 = {S → S, S → AA, A′ → A}, P2 = {A → AA′ , A → a}, P3 = {A → bA, A → b}. Tyto gramatick´e syst´emy generuj´ı n´ asleduj´ıc´ı jazyky: Lf (Γ1 ) = {an bn cm |m, n ≤ 1}, f ∈ {= 1, ≤ 1, , t} ∪ {≤ k|k ≥ 1}, L=2 (Γ1 ) = L≥2 (Γ1 ) = {an bn cn |n ≤ 1}, L=2 (Γ1 ) = L≥2 (Γ1 ) =6 0, k ≥ 3, n Lt (Γ2 ) = {a2 |n ≥ 1}, L=k (Γ3 ) = L≥k (Γ3 ) = {(an b)2k |n ≥ 1}, L=2 (Γ4 ) = L≥2 (Γ4 ) = {(an b)2k |n ≥ 1}, L=2 (Γ5 ) = L≥2 (Γ5 ) = {ww|w ∈ {a, b}+}. Nyn´ı si dok´ aˇzeme prvn´ı tvrzen´ı, abychom vidˇeli, jak syst´em funguje. Nechˇt Γ1 pracuje v m´odu 2. Stejnˇe jako u libovoln´e jin´e gramatiky mus´ıme zaˇc´ıt naˇsi derivaci ze startovn´ıho symbolu S. Pod´ıv´ ame-li se na mnoˇzinu pravidel, pak je jasn´e, ˇze pouze P1 m˚ uˇze b´ yt aplikov´ano. Derivace tedy bude vypadat n´ asledovnˇe:

S =⇒P1 S =⇒P1 AB.

5

Nyn´ı, kdyˇz se ve vˇetn´e formˇe jiˇz neobjevuje S, nem˚ uˇzeme nad´ale vyuˇz´ıvat P1 . Na AB se d´ a aplikovat pouze mnoˇzina pravidel P2 . Pokud pouˇzijeme nontermin´aln´ı pravidla, tak dostaneme: AB =⇒P2 aA′ bB =⇒P2 aA′ bcB ′ . Obecnˇe m˚ uˇzeme z vˇetn´e formy ve tvaru ai Abj ck B udˇelat derivaˇcn´ı krok do tvaru i+1 ′ j+1 k+1 ′ a A b c B Zaps´ ano matematicky: i+1 ′ j+1 k+1 ′ Ab c B. ai Abj ck B =⇒=2 P1 a

Na takov´ yto ˇretˇezec pak aplikujeme pravidlo z mnoˇziny P1 a dostaneme: i+1 Abj+1 ck+1 B. ai+1 A′ bj+1 ck+1 B ′ =⇒=2 P2 a

Toto je jedin´ a moˇznost, jak pouˇz´ıt mnoˇzinu pravidel P1 v m´odu 2. V mnoˇzinˇe pravidel P2 vˇsak m´ame moˇznost´ı v´ıce. M˚ uˇzeme napˇr´ıklad pouˇz´ıt jedno pravidlo s netermin´ alem a jedno pravidlo obsahuj´ıc´ı pouze termin´aln´ı symboly. Ovˇsem u ˇretˇezce, kter´ y obsahuje pouze jeden netermin´ al r˚ uzn´ y od S, neexistuje ˇreˇsen´ı ˇ dvˇe netermin´ v mnoˇzinˇe P1 . Proto tedy mus´ıme vˇzdy pouˇz´ıt bud aln´ı, nebo dvˇe termin´ aln´ı pravidla z mnoˇziny P2 . To znamen´ a, ˇze vˇsechny derivace Γ1 v m´odu =2 lze vyj´ adˇrit ve tvaru: =2 ′ ′ =2 =2 S =⇒=2 P1 AB =⇒P2 aA bcB =⇒P1 aAbcB =⇒P2 ... n n =2 n+1 n+1 n+1 n ′ n n =2 n b c . =⇒=2 P2 a A b c =⇒P1 a Ab c B =⇒P2 a

Toto plat´ı pro libovoln´e n ≤ 0 a proto tedy plat´ı, ˇze L=2 (Γ1 ) = {an bn cn |n ≤ 1}.

2.3

Generativn´ı s´ıla

Pokud se zamˇeˇr´ıme na generativn´ı s´ılu CD syst´em˚ u pracuj´ıc´ıch v libovoln´em m´odu, brzy zjist´ıme, ˇze se jejich s´ıla nijak nemˇen´ı. To znamen´ a, ˇze m´ame-li CD gramatick´ y syst´em, kter´ y obsahuje pravidla regul´ arn´ı, bezkontextov´a, kontextov´a nebo pravidla tˇr´ıdy 0, pak je takov´ yto syst´em schopn´ y generovat jazyky dan´e tˇr´ıdy. Tj. opˇet jazyky regul´ arn´ı, bezkontextov´e, kontextov´e nebo jazyky rekurzivnˇe vyˇc´ısliteln´e.

6

2.4

Hybridn´ı syst´ emy

Na tomto m´ıstˇe bych r´ ad zm´ınil p´ ar fakt˚ u o hybridn´ıch syst´emech, kter´e jsou velmi zaj´ımav´e a pˇredevˇs´ım velmi bl´ızk´e re´aln´emu ˇzivotu. Zat´ım jsme uvaˇzovali pouze syst´emy homogenn´ı. Tj. syst´emy, kde vˇsechny komponenty pracuj´ı ve stejn´em reˇzimu. V praxi se vˇsak uk´azalo, ˇze je v´ yhodnˇejˇs´ı uvaˇzovat o syst´emu, kde jeho ˇca´sti pracuj´ı v r˚ uzn´ ych m´odech. Takov´ yto syst´em se naz´ yv´ a hybridn´ı syst´em. Ten je definov´an n´ asledovnˇe: Γ = (N, T, S, (P1 , f1 ), ..., (Pn , fn )), n ≥ 1, kde (N, T, S, P1 , ..., Pn ) je bˇeˇzn´ y gramatick´ y syst´em tak, jak jsme si ho nadefinovali a fi ∈ D, 1 ≤ i ≤ n je derivaˇcn´ı m´od i-t´e komponenty. Tyto m´ody mohou b´ yt obecnˇe rozd´ıln´e! V´ıce o tˇechto syst´emech se lze doˇc´ıst zde [6].

2.5

T´ ymov´ y CD gramatick´ y syst´ em

Dalˇs´ı z modifikac´ı, kter´e by nemˇely b´ yt opomenuty, jsou t´ ymov´e CD gramatick´e syst´emy. U bˇeˇzn´ ych CD syst´em˚ u je podm´ınka, ˇze pouze jedna komponenta m˚ uˇze b´ yt v dan´ y okamˇzik aktivn´ı. Pokud tuto podm´ınku odstran´ıme, dost´ av´ ame t´ ym CD gramatick´ ych syst´em˚ u. CD gramatick´ y syst´em s t´ ymy je definov´an n´ asledovnˇe: Γ = (N, T, S, P1 , ..., Pn , R1 , ..., Rn ), n, m ≤ 1

(N, T, S, P1 , ..., Pn ) znaˇc´ı bˇeˇzn´ y gramatick´ y syst´em a R1 , ..., Rn jsou podmnoˇziny P1 , ..., Pn zvan´e t´ ymy. Derivace s pouˇzit´ım t´ ymu pak vypad´ a n´ asledovnˇe: x =⇒ Ri tehdyajentehdy x = x1 A1 x2 A2 ...xs As xs+1 = x1 y1 x2 y2 ...xs ys xs+1 xl ∈ (N ∪ T )∗ , 1 ≤ l ≤ s + 1, Ar → yr ∈ Pjr , 1 ≤ r ≤ s Vzhledem k tomu, ˇze se jedn´a o mnoˇzinu, tak nen´ı urˇceno ˇza´dn´e poˇrad´ı aplikace jednotliv´ ych pravidel. Zaj´ımav´ y je pˇredevˇs´ım fakt, ˇze t´ ymy dok´ aˇz´ı z´ asadnˇe zv´ yˇsit generativn´ı s´ılu CD gramatick´ ych syst´em˚ u. Podle [6] staˇc´ı t´ ymy o velikosti dva, abychom byli schopni generovat jazyky tˇr´ıdy 0. Pˇritom n´ am staˇc´ı, aby pravidla v t´ ymu byla bezkontextov´a. Toto n´ am mimo jin´e d´ av´ a zcela nov´ y zp˚ usob, jak zapisovat rekurzivnˇe vyˇc´ısliteln´e jazyky velmi pˇrehlednˇe.

2.6

Aplikace v praxi

Tento druh gramatick´eho syst´emu m´a sv´e uplatnˇen´ı pˇri pˇrekladu programovac´ıch jazyk˚ u. T´ımto zp˚ usobem je interpretov´an napˇr´ıklad jazyk Python. Interpret je totiˇz sloˇzen ze dvou komponent, kter´e si navz´ ajem pˇred´ avaj´ı ˇr´ızen´ı. 7

Podobn´ y koncept jsem zvolil i ve sv´e bakal´aˇrsk´e pr´aci, kde analyz´ator jazyka takt´eˇz sest´ av´ a ze dvou komponent a pˇred´ av´ an´ı ˇr´ızen´ı je prov´adˇeno na z´ akladˇe stop prvk˚ u. V m´em pˇr´ıpadˇe je jedna ˇca´st analyz´atoru zaloˇzena na rekurzivn´ım sestupu a druh´ a ˇca´st na precedenˇcn´ı anal´ yze. V momentˇe, kdy jedna z ˇca´st´ı naraz´ı na stop prvek, pˇred´ a ˇr´ızen´ı druh´e ˇca´sti. Tento zp˚ usob lze form´alnˇe popsat jako termin´ aln´ı m´od gramatick´eho syst´emu. To znamen´ a, ˇze dan´a komponenta pracuje na pˇrekl´ adan´em ˇretˇezci tak dlouho, dokud je to moˇzn´e. Pro ilustraci si si uvedeme jednoduch´ y pˇr´ıklad:

if (((a + b)/2) > ((2 ∗ a)||(2 ∗ b))); { int c; c := a + b/12; }

V tomto pˇr´ıpadˇe jsou veˇsker´e aritmetick´e v´ yrazy pˇreloˇzeny jednou komponentou a pˇr´ıkazy jako if nebo for jsou pˇreloˇzeny druhou komponentou. Samozˇrejmˇe se m˚ uˇze tak´e vyskytnout pˇr´ıpad, ˇze cel´ y zdrojov´ y k´ od bude m´ıt na starosti pouze jedna komponenta a druh´ a se v˚ ubec nedostane k pˇrekladu. CD gramatcik´e syst´emy maj´ı sv´e vyuˇzit´ı tak´e v multiagentn´ıch syst´emech jak dokl´ ad´ a kniha s n´ azvem Grammar systems: a grammatical approach to distribution and cooperation [1]. V tomto pˇr´ıpadˇe jsou CD gramatick´e syst´emy pouˇzity pro popis komunikace mezi jednotliv´ ymi agenty a pro jejich kooperaci. V t´eto kapitole bylo osvˇetleno, co to jsou a jak funguj´ı CD gramatick´e syst´emy. Tyto syst´emy jsou stejnˇe jako PC syst´emy pouˇz´ıv´ any pˇredevˇs´ım pro z´ apis distribuovan´eho zpracov´an´ı. Stoj´ı na relativnˇe jednoduch´em z´ akladˇe a jsou snadno pochopiteln´e. Po zaveden´ı urˇcit´ ych zmˇen vˇsak disponuj´ı velmi velkou s´ılou. Pˇri pouˇzit´ı bezkontextov´ ych pravidel z´ısk´ame totiˇz s´ılu pˇresahuj´ıc´ı s´ılu bezkontextov´ ych gramatik. Bylo tak´e nast´ınˇeno pouˇzit´ı tohoto modelu v praxi.

3

PC gramatick´ e syst´ emy

V t´eto ˇca´sti se jiˇz budeme zab´ yvat PC gramatick´ ymi syst´emy, kter´e oproti CD syst´em˚ um dovoluj´ı pr´aci na v´ıce vˇetn´ ych form´ach souˇcasnˇe. Nejdˇr´ıve si takov´ y syst´em nadefinujme.

3.1

Definice

PC gramatick´ y syst´em stupnˇe n, n ≥ 1, je (n+3)-tice Γ = (N, K, T, (S1 , P1 ), ..., (Sn , Pn )),

8

kde N je abeceda netermin´ al˚ u, T je abeceda termin´al˚ u, K= Q1 , ..., Qn , Pi je koneˇcn´ a mnoˇzina pˇrepisovac´ıch pravidel nad N ∪ K ∪ T a Si ∈ N pro vˇsechna 1 ≤ i ≤ n. Mnoˇziny Pi , 1 ≤ i ≤ n jsou naz´ yv´ any komponenty syst´emu a elementy Q1 , ..., Qn z K se naz´ yvaj´ı dotazovac´ı symboly. Index i u Qi odkazuje na i-tou komponentu z Γ. Pokud bychom chtˇeli vyj´ adˇrit gramatiku jako souˇca´st PC gramatick´eho syst´emu Γ, lze to zapsat n´ asledovnˇe Γ = (N, K, T, G1 , ..., Gi ), kde Gi = (N ∪ K, T, Si , Pi ), 1 ≤ i ≤ n. Jeˇstˇe neˇz pˇrejdeme k jazyku, kter´ y m˚ uˇze gramatick´ y syst´em generovat, je nutn´e si nadefinovat jeho derivaci. M´ ame-li PC gramatick´ y syst´emΓ = (n, k, t, (S1 , P1 , ..., (Sn , Pn ))) v podobˇe, v jak´e byl nadefinov´an v´ yˇse, pak pro dvˇe n-tice(x1 , x2 , ...xn ), (y1 , y2 , ..., yn ), kde xi , yi ∈ VΓ∗ , 1 ≤ i ≤ n a x1 6∈ T ∗ pak p´ıˇseme (x1 , ...xn ) =⇒ (y1 , ..., yn ), pokud nastal jeden z n´ asleduj´ıc´ıch pˇr´ıpad˚ u: ˇ Pro kaˇzd´e i, 1 ≤ i ≤ n, |xi |K = 0, 1 ≤ i ≤ n a pro kaˇzd´e i1 ≤ i ≤ n m´ame bud xi =⇒ yi pˇri pouˇzit´ı pravidla z Pi , nebo xi = yi ∈ T∗ Existuje takov´e i, 1 ≤ i ≤ n takov´e, ˇze |xi |K > 0. Nechˇt pro kaˇzd´e takov´e i, xi = z1 Qi1 z2 Qi2 ...zt Qit zt+1 , t ≥ 1, pro zj ∈ (N ∪ T )∗ , 1 ≤ j ≤ t + 1. Pokud |xij |k = 0, pro vˇsechna j1 ≤ j ≤ t, pak yi = z1 xi1 z2 xi2 ...zt xit zt+1 a yij = Sij , 1 ≤ j ≤ t. Pokud pro nˇejak´e j 1 ≤ j ≤ t, |xij |K 6= 0, pak yi = xi . Pro vˇsechna i,1 ≤ i ≤ n, takov´a, ˇze yi nen´ı specifikov´ano v´ yˇse, plat´ı xi = yi . Kaˇzd´ a n-tice (x1 , ..., xn ), kde xi ∈ VΓ∗ pro vˇsechna i 1 ≤ i ≤ n je naz´ yv´ ana konfigurace. Konfigurace (x1 , ..., xn ) pˇr´ımo pˇrech´ az´ı v konfiguraci (y1 , ..., yn ) pokud: ˇ adn´ 1. Z´ y dotazovac´ı symbol se neobjevuje v (x1 , ..., xn ), pak m´ame komponentn´ı derivaci, xi =⇒ yi , v kaˇzd´e komponentˇe Pi , 1 ≤ i ≤ n tzn., ˇze v kaˇzd´e komponentˇe je pouˇzito jedno pravidlo, vyjma pˇr´ıpadu, ˇze xi je sloˇzeno z termin´ al˚ u. V tom pˇr´ıpadˇe p´ıˇseme xi = yi . 2. Dotazovac´ı symbol se vyskytuje v nˇejak´em xi . Pokud toto nastane, pak je provedena f´ aze, kter´ a se naz´ yv´ a komunikaˇcn´ı krok. Kaˇzd´ y v´ yskyt Qi v xi je nahrazen xj za pˇredpokladu, ˇze samotn´e xj neobsahuje ˇza´dn´ y dotazovac´ı symbol. Jinak ˇreˇceno, komponenta xi je mˇenˇena, pouze pokud vˇsechny c´ıle, do kter´ ych smˇeˇruj´ı dotazovac´ı symboly, samy neobsahuj´ı dotazovac´ı symboly. V komunikaˇcn´ım kroku je dotazovac´ı symbol Qj nahrazen pˇr´ısluˇsn´ ym ˇretˇezcem xj .Pot´e zaˇcne gramatika Gj opˇet pˇrepisovat od startovac´ıho symbolu. D˚ uleˇzit´e je, ˇze komunikace m´a pˇrednost pˇred pˇrepisov´an´ım. To znamen´ a, ˇze bˇehem komunikace nemohou b´ yt pˇrepisov´any ˇza´dn´e symboly. Dokud tedy nejsou nahrazeny vˇsechny v´ yskyty dotazovac´ıch symbol˚ u, kter´e b´ yt nahrazeny mohou, nedˇeje se ˇza´dn´e pˇrepisov´an´ı. Pokud nem˚ uˇze b´ yt nˇejak´ y dotazovac´ı symbol nahrazen v dan´em komunikaˇcn´ım kroku, protoˇze obsahuje dotazovac´ı symbol, 9

je nahrazen pˇri prvn´ım moˇzn´em n´ asleduj´ıc´ım kroku. Vezmeme-li v potaz v´ yˇse ˇreˇcen´e, pak je jasn´e, ˇze pravidla typu x1 Qi x2 =⇒ x nemohou b´ yt nikdy pouˇzita. M˚ uˇzeme je tedy vypustit z PC gramatick´ ych syst´em˚ u. Tak´e nem´ a smysl definovat pravidla typu (x1 , ...xn ) =⇒ (y1 , ..., yn ), pokud je lev´a strana pravidla sloˇzena z termin´al˚ u. Vzhledem k tomu, ˇze PC gramatick´e syst´emy pracuj´ı paralelnˇe, hroz´ı zde re´ aln´e nebezpeˇc´ı uv´ aznut´ı cel´eho syst´emu. Uv´ aznut´ı m˚ uˇze nastat ve dvou pˇr´ıpadech. Ten prvn´ı je docela zˇrejm´ y. Je to stav, kdy se ˇza´dn´ y dotazovac´ı symbol nevyskytuje v ˇretˇezci, ˇretˇezec (x1 , ...xn ) nen´ı termin´aln´ım ˇretˇezcem a z´ aroveˇ n nelze ˇza´dn´e pravidlo na dan´ y ˇretˇezec aplikovat. Tento typ uv´aznut´ı m˚ uˇze nastat po obou f´ az´ıch. Jak po f´azi pˇrepisov´an´ı, tak po f´azi komunikace. Druh´ a moˇznost, jak by mohl cel´ y syst´em uv´aznout, je tak´e dobˇre zn´ am´ a z paraleln´ıch syst´em˚ u. Jde o kruhovou z´ avislost. Komponenta (Pi1 ) vol´a (Qi2 ), a (Qi3 ), aˇz (Pik−1 ) zavol´a (Qik ) a (Pik ) zavol´a opˇet (Qi1 ). n´ aslednˇe (Pi2 ) zavol´ Je jasn´e, ˇze takov´ato z´ avislost nem˚ uˇze b´ yt vyˇreˇsena, protoˇze se komunikuj´ı pouze ˇretˇezce, kter´e neobsahuj´ı dotazovac´ı symboly. Nyn´ı pˇrejdˇeme k definici jazyka, kter´ y je v pˇr´ıpadˇe, ˇze nenastane uv´aznut´ı, dan´ ym syst´emem generov´an. Jazyk generovan´ y PC gramatick´ ym syst´emem Γ vypad´ a n´ asledovnˇe: L(Γ) = {x ∈ T |(S1 , S2 , ..., Si ) =⇒∗ (x, α2 , ..., αn ), αi ∈ VΓ∗ , 2 ≤ i ≤ n} Zaˇcneme tedy od n-tice startuj´ıc´ıch symbol˚ u (S1 , S2 , ..., Si ) a pokraˇcujeme pˇres pˇrepisovac´ı a komunikaˇcn´ı kroky, dokud komponenta P1 nevyprodukuje ˇretˇezec termin´ al˚ u. Komponenta P1 se naz´ yv´ a master. Je to proto, ˇze v momentˇe, kdy tato prvn´ı komponenta vytvoˇr´ı ˇretˇezec termin´al˚ u, tak cel´ y syst´em ukonˇc´ı derivov´an´ı nez´ avisle na tom, co obsahuj´ı ostatn´ı komponenty. PC gramatick´e syst´emy maj´ı tak´e svoje dˇelen´ı. Existuj´ı dvˇe z´ akladn´ı tˇr´ıdy gramatick´ ych syst´em˚ u. Ty lze klasifikovat podle toho, jak´ y graf vytv´aˇr´ı. Reˇ spektive podle tvaru grafu, jak´ y vytv´aˇr´ı. Pro u ´ plnost si uvedme pˇresnou definici. Nechˇt Γ = (N, K, T, (S1 , P1 ), ..., (Sn , Pn )) je PC gramatick´ y syst´em. Pokud je pouze P1 povoleno generovat dotazovac´ı symboly(Pi ⊆ (N ∪ T )∗ × (N ∪ T )∗ pro 2 ≤ i ≤ n), pak ˇr´ık´ ame, ˇze Γ je centralizovan´ y gramatick´ y syst´em. Pokud m˚ uˇze generovat dotazovac´ı symboly libovoln´ a komponenta, pak je Γ necentralizovan´ y gramatick´ y syst´em. Dalˇs´ı hledisko dˇelen´ı gramatick´ ych syst´em˚ u je podle toho, zda se vrac´ı, ˇci nevrac´ı ke sv´emu poˇca´teˇcn´ımu netermin´ alu. Gramatiku nazveme navracej´ıc´ı se, pokud se pot´e, co poslala sv˚ uj ˇretˇezec jin´e komponentˇe, vr´ at´ı ke sv´emu startuj´ıc´ımu netermin´ alu Si . Pokud se tak nestane, a gramatika tedy pokraˇcuje v prov´adˇen´ı derivaˇcn´ıch krok˚ u, pak ji nazveme nenavracej´ıc´ı gramatikou. Pokud je gramatika nenavracej´ıc´ı, pak je nutn´e vynechat podm´ınku yij = Sij v definici derivace. PC gramatick´ y syst´em nazveme regul´ arn´ı, bezkontextov´ y, kontextov´ y, nebo tˇr´ıdy 0, pokud pravidla tohoto syst´emu jsou dan´e tˇr´ıdy. Pokud nazveme syst´em regul´ arn´ım, tak se vˇetˇsinou jedn´a o syst´em pravˇe line´arn´ı. To znamen´ a, ˇze 10

pravidla maj´ı tvar A −→ xB, A −→ x kde A, B jsou netermin´ aly a x je termin´ al.

3.2

Pˇ r´ıklady

Ukaˇzme si vˇse na nˇekolika jednoduch´ ych pˇr´ıkladech. Uvaˇzujme n´ asleduj´ıc´ı gramatick´e syst´emy: ′

Γ1 = ({S1 , S1 , S2 , S3 }, K, {a, b}, (S1, P1 ), (S2 , P2 ), (S3 , P3 )), ′

′

′

′

P1 = {S1 → abc, S1 → a2 b2 c2 , S1 → aS1 , S1 → a3 Q2 , S1 → aS1 , S1 → 3 a Q2 , S2 → bQ3 , S3 → c}, P2 = {S2 → bS2 }, P3 = {S3 → cS3 }, Γ2 = ({S1 , S2 }, K, {a, b}, (S1, P1 ), (S2 , P2 )), P1 = {S1 → S1 , S1 → Q1 Q2 }, P2 = {S2 → aS2 , S2 → bS2 , S2 → a, S2 → b}, Γ3 = ({S1 , S2 }, K, {a, b}, (S1, P1 ), (S2 , P2 )), P1 = {S1 → S1 , S1 → Q1 Q2 }, P2 = {S2 → aS2 , S2 → S2 b, S2 → ab}. V´ yˇse uveden´e gramatick´e syst´emy zjevnˇe generuj´ı n´asleduj´ıc´ı jazyky: Lr (Γ1 ) = Lnr (Γ1 ) = {an bn cn kn ≥ 1}, Lr (Γ2 ) = Lnr (Γ2 ) = {xxkx ∈ {a, b}+ 1}, Lr (Γ3 ) = Lnr (Γ3 ) = {an bm an bm kn, m ≥ 1}. Ukaˇzme si nyn´ı na gramatick´em syst´emu Γ1 , jak pracuje. Mus´ıme zaˇc´ıt pˇrepisovat od startuj´ıc´ıch termin´al˚ u, tedy od (S1 , S2 , S3 ). Pot´e aplikujeme tˇret´ı a p´ at´e pravidlo z P1 a pravidla z P2 a P3 . Pokud provedeme tyto derivaˇcn´ı kroky, dost´ av´ ame: ′

′

(S1 , S2 , S3 ) =⇒r (aS1 , bS2 , cS3 ) =⇒∗r (an+1 S1 , bn+1 S2 , cn+1 S3 ). Pˇr´ıpadnˇe m˚ uˇzeme pouˇz´ıt ˇsest´e pravidlo z mnoˇziny P1 : ′

′

(an+1 S1 , bn+1 S2 , cn+1 S3 ) =⇒r (an+4 Q2 , bn+1 S2 , cn+2 S3 ). 11

Protoˇze se n´ am vyskytl ve vˇetn´e formˇe dotazovac´ı symbol Q2 , mus´ıme prov´est komunikaˇcn´ı krok. bn+2 S2 je posl´ ano prvn´ı komponentˇe, kde nahrad´ı Q2 . ′

(an+4 Q2 , bn+1 S2 , cn+2 S3 ) =⇒r (an+4 bn+2 S2 , S2 , cn+2 S3 ). Deterministick´ ym zp˚ usobem pak budeme prov´adˇet n´ asleduj´ıc´ı kroky: (an+4 bn+2 S2 , S2 , cn+2 S3 ) =⇒r (an+4 bn+4 Q3 , bS2 , cn+3 S3 ) =⇒r (an+4 bn + 4cn+3 S3 , bS2 , S3 ) =⇒r (an+4 bn+4 cn+3 S3 , bS2 , cS3 ). T´ımto zp˚ usobem m˚ uˇzeme vyprodukovat vˇsechny ˇretˇezce an bn cn , n ≥ 4. To n´ am ovˇsem nestaˇc´ı. Mus´ıme b´ yt schopni vytvoˇrit i ˇretˇezce kratˇs´ı. (S1 , S2 , S3 ) =⇒r (a3 Q2 , bS2 , cS3 ) =⇒r (a3 bS2 , S2 , cS3 ) =⇒r =⇒r (a3 b3 Q3 , bS2 , c2 S3 ) =⇒r (a3 b3 c2 S3 , bS2 , S3 ) =⇒r (a3 b3 c3 , b2 S2 , cS3 ). ˇ ezce abc a a2 b2 c2 dok´ Takto vytvoˇr´ıme ˇretˇezec a3 b3 c3 . Retˇ aˇze vytvoˇrit komponenta P1 sama. Syst´emy Γ2 a Γ3 pracuj´ı n´ asledovnˇe: P1 nedˇel´a nic, dokud P2 generuje ˇretˇezec. Pak P1 vytvoˇr´ı ˇretˇezec Q1Q2 . T´ım p´ adem je ˇretˇezec z P2 zasl´an ˇ ezec mus´ı b´ P1 a je duplikov´an.Retˇ yt tvoˇren termin´aly, jinak dojde k uv´aznut´ı. Vˇsechny v´ yˇse zm´ınˇen´e gramatick´e syst´emy jsou centralizovan´e. Jak vid´ıme, tak tyto relativnˇe jednoduch´e gramatick´e syst´emy mohou generovat jazyky, kter´e nejsou bezkontextov´e.

3.3

Nesynchronizovan´ e PC gramatick´ e syst´ emy

U vˇsech pˇredchoz´ıch gramatick´ ych syst´em˚ u jsme uvaˇzovali synchronizaci pˇrepisovac´ıch krok˚ u. T´ım p´ adem existovaly nˇejak´e hodiny, kter´e ˇr´ıdily cel´ y syst´em. S kaˇzd´ ym tikem hodin musela kaˇzd´ a komponenta pouˇz´ıt pˇrepisovac´ı pravidlo, pokud syst´em nen´ı v komunikaˇcn´ım m´odu. Pokud je ˇretˇezec v komponentˇe jiˇz sloˇzen z termin´ al˚ u, pak ˇza´dn´e pravidlo nen´ı aplikov´ano. Pokud takovou synchronizaci nevyˇzadujeme, pak mluv´ıme o nesynchronizovan´em syst´emu. Oznaˇc´ıme Lu,r (Γ) a Lu,nr (Γ) jazyky generovan´e PC gramatick´ ymi syst´emy Γ v nesynchronizovan´em n´ avratn´em a nesynchronizovan´em nen´avratn´em m´odu. U Yn X oznaˇc´ıme rodinu jazyk˚ u generovanou nesynchronizovan´ ymi gramatick´ ymi ˇ syst´emy. Uvedme si nˇekolik teor´em˚ u, kter´e m˚ uˇzeme naj´ıt v t´eto literatuˇre. [3] (i)U CP C∞ X = X, pro x ∈ {REG, LIN }. (ii)U P C2 REG−REG 6= ∅, U P C∞ REG ⊆ CF, U P C2 LIN −CF 6= ∅, U CP C2 CF − CF 6= ∅.

12

(iii)U CP C2 REG obsahuje nesemiline´arn´ı jazyky U N CP C2 CF obsahuje jednop´ısmenn´e a neregul´arn´ı jazyky. (iv)(CP C∞ REG ∩ N CP C∞ REG) − U CP C∞ CF 6= ∅. Body (i) a (iv) ukazuj´ı, ˇze pokud rozsynchronizujeme gramatick´ y syst´em, sn´ıˇz´ıme podstatnˇe generativn´ı s´ılu, zat´ımco nesynchronizovan´e PC gramatick´e syst´emy jsou st´ ale velmi siln´e, jak ukazuj´ı body (ii) a (iii). Γ1 = ({S1 , S2 , A, B, }, K, {a, b}, {S1, P1 }, {S2 , P2 }), P1 = {S1 −→ bQ2 , B −→ bQ2 , B −→ b}, P2 = {S2 −→ aS2 , S2 −→ aA, A −→ aB}, Γ2 = ({S1 , S2 , A, B, }, K, {a, b}, {S1, P1 }, {S2 , P2 }), P1 = {S1 −→ aQ2 , S1 −→ aA, B −→ bA}, P2 = {S2 −→ aQ1 , A −→ bB, A −→ b}. Jazyky, kter´e z takov´ ychto gramatick´ ych syst´em˚ u dostaneme, jsou n´ asleduj´ıc´ı: Lu,nr (Γ1 ) = {(ban )m b|m ≥ 1, n ≥ 2}, nesemiline´arn´ı jazyk, Lu,r (Γ2 ) = {a2m a2s+1 b2t+1 |m, s, t ≥ 1, s ≥ t}, neregul´arn´ı jazyk.

3.4

Gramatick´ e syst´ emy s komunikac´ı na pˇ r´ıkaz

Ve vˇsech pˇredchoz´ıch PC gramatick´ ych syst´emech jsme uvaˇzovali pˇr´ıpad, kdy byla komunikace vyˇza´d´ ana komponentou, kter´ a vygenerovala dotazovac´ı symbol pˇr´ıpadnˇe symboly. Tomuto zp˚ usobu iniciace komunikace proto ˇr´ık´ ame na ˇza´dost. To ovˇsem nen´ı jedin´ a moˇznost, jak komunikovat. Z praktick´eho hlediska je vˇsak stejnˇe d˚ uleˇzit´ y i jin´ y pˇr´ıstup naz´ yvan´ y komunikace na pˇr´ıkaz. Tento pˇr´ıstup je iniciov´an komponentou, kter´ a pos´ıl´ a zpr´ avy. PC gramatick´e syst´emy komunikuj´ıc´ı na pˇr´ıkaz modeluj´ıc´ı WAVE diagram byly uvedeny E. Tsuhaj-Varjuem v tomto d´ıle [2]. Z´ akladn´ı myˇslenkou je syst´em sest´avaj´ıc´ı z nˇekolika gramatik tak, jak je to bˇeˇzn´e u vˇsech PC gramatick´ ych syst´em˚ u pracuj´ıc´ıch oddˇelenˇe, kaˇzd´ a na sv´e vlastn´ı vˇetn´e formˇe. Kaˇzd´ a z tˇechto gramatik m´a na sv´em vstupu regul´ arn´ı nebo jin´ y jazyk, kter´ y pracuje jako vstupn´ı filtr. V urˇcit´ ych pˇr´ıpadech je pˇrepisov´an´ı pˇreruˇseno a kaˇzd´ a komponenta poˇsle svou aktu´aln´ı vˇetnou formu ostatn´ım komponent´ am. Zejm´ena tˇem, jejichˇz vstupn´ı filtr obsahuje danou vˇetnou formu. Stejnˇe jako u ostatn´ıch PC gramatick´ ych syst´em˚ u, tak i u tˇechto je jazyk generov´an master komponentou jazykem, kter´ y generuje cel´ y syst´em. 13

Mus´ı vˇsak b´ yt vyˇreˇseno jeˇstˇe nˇekolik ot´azek, neˇz bude moˇzn´e formulovat form´aln´ı model: 1. Kdy m´a b´ yt ovˇeˇreno, zda mohou b´ yt vˇetn´e formy komunikov´any? Lze to dˇelat po kaˇzd´em kroku, pokud jsme v synchronizovan´em m´odu, nebo m˚ uˇzeme nechat vˇsechny komponenty pracovat tak dlouho, dokud mohou, a pot´e prov´est komunikaci. 2. Co by mˇelo b´ yt komunikov´ano? Cel´a vˇetn´a forma, nebo pouze jej´ı ˇca´st? 3. Jak´a bude dalˇs´ı vˇetnou formou komponenty, kter´ a komunikovala sv˚ uj ˇretˇezec? Tedy jde o syst´em, kter´ y se navrac´ı, ˇci nikoli. 4. Uvaˇzujme, ˇze je nˇekolik zpr´ av zasl´ano jedn´e komponentˇe? Zde je moˇzn´e ˇ ze vˇsech naj´ıt nˇekolik ˇreˇsen´ı. Nejpˇrirozenˇejˇs´ı se jev´ı dvˇe varianty. Bud ˇ zpr´ av, kter´e byly zasl´ any dan´e komponentˇe, vybereme jednu, a to bud nedeterministicky, nebo s pˇrihl´ednut´ım k priorit´ am komponent, nebo provedeme konkatenaci vˇsech zpr´ av podle poˇrad´ı komponent. Jin´e pˇr´ıstupy, kter´e se inspiruj´ı podobn´ ymi praktick´ ymi probl´emy, lze nal´ezt zde [5].

3.5

Aplikace v praxi

Na rozd´ıl od CD gramatick´ ych syst´em˚ u je aplikace PC gramatick´ ych syst´em˚ u moˇzn´e tam, kde je zapotˇreb´ı paralelismu. I zde lze uvaˇzovat o aplikaci v multiagentn´ıch syst´emech. Pokud napˇr´ıklad nelze nebo nem˚ uˇze libovoln´ y agent prov´est zadanou operaci, vygeneruje symbol, pomoc´ı kter´eho poˇza´d´ a o proveden´ı operace jin´eho agenta nebo budou na dan´e operaci spolupracovat. Nejd˚ uleˇzitˇejˇs´ı aplikac´ı PC gramatick´ ych syst´em˚ u vˇsak nad´ale z˚ ust´ av´ a pˇreklad jazyk˚ u. M˚ uˇzeme si snadno pˇredstavit, ˇze pouˇz´ıv´ ame v naˇsem souboru se zdrojov´ ym k´odem nˇekolik programovac´ıch jazyk˚ u. Uvaˇzujme pro zaˇca´tek situaci, ˇze jsou programovac´ı jazyky od sebe navz´ ajem oddˇeleny napˇr´ıklad takto:

****************Jazyk C********************* double a,b,c; scanf(”%f”, a); printf(”soucet je:%f”,a+b+c);

*****************Assembler*******************

ohrkone: push bp ; stav zasobniku (shora dolu): 14

mov bp,sp ; x1:2,y1:2,x2:2,y2:2,cs:2,ip:2,bp:2 mov al,0 ; false (kone se neohrozuji) mov bl,[bp+12] ; x1 do bl sub bl,[bp+8] ; (x1-x2) do bl jz konec1 ; kone ve stejnem radku se neohrozuji jns pokr1 ; neg bl ; -(x1-x2) do bl V takov´em pˇr´ıpadˇe nen´ı potˇreba generovat ˇza´dn´e dotazovac´ı symboly. Je moˇzn´e zpracovat cel´ y zdrojov´ y soubor paralelnˇe. Kaˇzd´ a komponenta zpracuje svoji ˇca´st zdrojov´eho k´odu n´ asleduj´ıc´ım zp˚ usobem. Najde si sv˚ uj startuj´ıc´ı netermin´ aln´ı symbol a pak aplikuje pˇrepisovac´ı pravidla ve vhodn´em poˇrad´ı. Pokud je u takov´ehoto typu pˇrekladu vygenerov´an dotazovac´ı symbol, lze to povaˇzovat za chybu. Nyn´ı uvaˇzujme situace, ˇze jednotliv´e programovac´ı jazyky jsou sm´ıch´ any dohromady: ohrkone: push bp ; stav zasobniku (shora dolu): mov bp,sp ; x1:2,y1:2,x2:2,y2:2,cs:2,ip:2,bp:2 mov al,0 ; false (kone se neohrozuji) mov bl,[bp+12] ; x1 do bl sub bl,[bp+8] ; (x1-x2) do bl jz konec1 ; kone ve stejnem radku se neohrozuji jns pokr1 ; neg bl ; -(x1-x2) do bl var x1,x2,y1,y2,i,j:Byte; ch:Char; Function ohrkone(x1,y1,x2,y2:Byte):Boolean;External; begin Randomize; ClrScr; repeat GoToXY(2,1); Write(’Zadejte pozadovanou cinnost (O..Ohrozuje, K..Konec): ’); repeat ch:=UpCase(ReadKey); until ch in [’O’,’K’]; ClrScr; case ch of ’O’:begin x1:=Random(8)+1; y1:=Random(8)+1; repeat x2:=Random(8)+1;

15

y2:=Random(8)+1; until not ((x1=x2) and (y1=y2)); for i:=1 to 8 do begin for j:=1 to 8 do begin GoToXY(20+2*j,3+i); if ((i=x1) and (j=y1)) or ((i=x2) and (j=y2)) then Write(’X’) else Write(’.’); end; end; GoToXY(22,15); WriteLn(’Kone se ohrozuji: ’,ohrkone(x1,y1,x2,y2),’ ’); end; end; until ch=’K’; end. Zde lze pˇri kontrole zdrojov´eho k´odu uplatnit naplno PC gramatick´e syst´emy. Kaˇzd´ a komponenta bude pˇrekl´ adat svou ˇca´st k´odu a v momentˇe kdy naraz´ıme na assemblerovsk´ y k´od uvnitˇr jazyka pascal se dot´aˇzeme t´eto komponenty, zda je assemblerovsk´ a ˇca´st v poˇra´dku. D´ a se uvaˇzovat i o aplikaci tohoto postupu v kryptografii. Pˇri l´ am´ an´ı ˇsifry bude kaˇzd´emu procesoru, poˇc´ıtaˇci nebo jin´e v´ ypoˇcetn´ı jednotce pˇridˇelena urˇcit´ a ˇca´st v´ ypoˇctu. Jednotky pak mohou pracovat nez´avisle na sobˇe a v pˇr´ıpadˇe potˇreby budou spolu komunikovat pˇres dotazovac´ı symboly. Tato kapitola diskutovala gramatick´e syst´emy typu PC. Nejdˇr´ıve byla provedena definice tohoto typu gramatick´eho syst´emu a n´ aslednˇe na pˇr´ıkladech uk´az´ano, jak v praxi funguj´ı. Bylo provedeno rozdˇelen´ı syst´em˚ u podle r˚ uzn´ ych hledisek. D´ ale se kapitola zab´ yvala nˇekolika specifick´ ymi typy gramatick´ ych syst´em˚ u, jako jsou nesynchronizovan´e gramatick´e syst´emy nebo syst´emy komunikuj´ıc´ı na pˇr´ıkaz. Z´ avˇerem jsem se pokusil osvˇetlit kde se daj´ı takov´ yto model pouˇz´ıt v praxi.

4

Pˇ r´ıbuzn´ e modely

Nyn´ı se jeˇstˇe ve zkratce pod´ıvejme na nˇekter´e modely, kter´e jsou pˇr´ıbuzn´e gramatick´ ym syst´em˚ um. Bude se jednat eco gramatiky, a pak tak´e o test tube syst´emy.

4.1

Eco gramatiky

V pˇr´ıpadˇe EG[6] se jedn´a o relativnˇe ned´avno uveden´ y gramatick´ y model, kter´ y je zamˇeˇren na vztah mezi prostˇred´ım a agenty, kteˇr´ı v nˇem p˚ usob´ı. Takov´ yto syst´em se naz´ yv´ a ekosyst´em. EG lze interpretovat jako zobecnˇen´ı jak CD, tak i PC gramatick´ ych syst´em˚ u. Hlavn´ı myˇslenkou pˇri definici tohoto mod-

16

elu bylo zachycen´ı popisu r˚ uzn´ ych forem ˇzivota tak, aby bylo moˇzn´e tuto notaci pouˇz´ıt pˇri modelov´an´ı multiagentn´ıch syst´em˚ u, nebo jin´ ych umˇel´ ych forem ˇzivota. Z´ akladn´ım pˇredpokladem tohoto modelu je fakt, ˇze komponenty tohoto syst´emu mohou b´ yt pops´ any ˇretˇezci nad dan´ ymi abecedami. Sch´ema gramatick´eho syst´emu je zachyceno na obr´ azku 2.1.

Cel´ y syst´em je ve sv´e podstatˇe rozdˇelen na dvˇe ˇca´sti. Rozliˇsujeme prostˇred´ı, kter´e je pops´ ano ˇretˇezci wE nad abecedou VE . Prostˇred´ı se vyv´ıj´ı podle mnoˇziny pravidel PE , kter´ a jsou typu 0. Na druhou stranu agenti, kter´ ych m˚ uˇze b´ yt obecnˇe n, jsou jsou pops´ ani ˇretˇezci wi nad abecedou Vi a vyv´ıj´ı se podle pravidel Pi , kter´ a jsou rovnˇeˇz typu 0. Form´alnˇe je tedy EG syst´em pops´ an n´ asledovnˇe: Σ = (E, A1 , A2 , ..., An ), kde E = (VE , PE ) je prostˇred´ı, Ai = (Vi , Pi , Ri , ϕi , ψi ), 1 ≤ i ≤ n, jsou jednotliv´ı agenti. Konvence pro popis je n´ asleduj´ıc´ı: VE , Vi jsou abecedy (VE ∩ Vi = ∅), 1 ≤ i ≤ n, PE koneˇcn´ a mnoˇzina pravidel typu 0 nad VE , Pi koneˇcn´ a mnoˇzina pravidel typu 0 nad Vi , 1 ≤ S i ≤ n, Ri koneˇcn´ a mnoˇzina pˇrepisovac´ıch pravidel nad VE nebo j6=i Vj , 1 ≤ i ≤ n, ϕi : VE∗ −→ 2Pi , 1 ≤ i ≤ n, ψi : Vi∗ −→ 2Ri , 1 ≤ i ≤ n. Aplikace v praxi Tyto gramatiky jsou vhodn´e zejm´ena pro popis agentn´ıch a multiagentn´ıch syst´em˚ u. Bohuˇzel se mi nepodaˇrilo naj´ıt ˇza´dn´e informace o pˇreveden´ı tohoto modelu do praxe.

17

4.2

Test tube syst´ emy

Posledn´ım modelem, kter´ y bude nast´ınˇen jsou test tube syst´emy[4]. Jedn´ a se o mechanismus zpracov´an´ı symbol˚ u, kter´ y m´a architekturu PC gramatick´eho syst´emu komunikuj´ıc´ıho na pˇr´ıkaz. Komunikace v r´ amci syst´emu je prov´adˇena pomoc´ı redistribuce obsahu jednotliv´ ych rour(tubes). Takov´eto syst´emy se uk´ azaly v´ ypoˇcetnˇe u ´ pln´e. Maj´ı tedy s´ılu vyj´ adˇrit rekurzivnˇe vyˇc´ısliteln´e jazyky. Tato kr´ atk´ a kapitolka mˇela za u ´ kol pˇredstavit nˇekter´e dalˇs´ı modely, kter´e jsou pˇr´ıbuzn´e gramatick´ ym syst´em˚ um. Byly prezentov´any EG syst´emy a test tube syst´emy.

5

Z´ avˇ er

C´ılem t´eto pr´ace bylo obezn´amit se s gramatick´ ymi syst´emy jak z teoretick´eho tak i z praktick´eho hlediska. Bylo provedeno rozdˇelen´ı gramatick´ ych syst´em˚ u na tˇri kategorie. CD gramatick´e syst´emy, PC gramatick´e syst´emy a pˇr´ıbuzn´e modely. CD gramatick´e syst´emy pracuj´ı sekvenˇcnˇe. Nicm´enˇe i tak maj´ı velkou s´ılu, neboˇt i s bezkontextov´ ymi pravidly lze generovat jazyky typu 0. Obvykle pracuj´ı vˇsechny komponenty ve stejn´em m´odu coˇz vˇsak neplat´ı o hybridn´ıch CD gramatick´ ych syst´emech, kde je kaˇzd´e komponentˇe pˇriˇrazen libovoln´ y m´od. Zmˇeny derivaˇcn´ıho m´odu nijak neovlivn´ı jejich s´ılu. Hlavn´ı uplatnˇen´ı tˇechto syst´em˚ u je v pˇrekladu a interpretaci jazyk˚ u. Dalˇs´ı probranou kategori´ı jsou PC gramatick´e syst´emy. Jejich nejvˇetˇs´ı v´ yhodou je fakt, ˇze jsou paraleln´ı. Kaˇzd´ a komponenta tedy m˚ uˇze pracovat samostatnˇe, dokud nen´ı tˇreba kooperace s ostatn´ımi pomoc´ı dotazovac´ıch symbol˚ u. PC gramatick´e syst´emy dˇel´ıme na returning a non-returning podle toho, zda se vracej´ı po komunikaˇcn´ım kroku zpˇet do poˇca´teˇcn´ıho stavu. Existuj´ı i speci´ aln´ı verze PC gramatick´ ych syst´em˚ u jako napˇr´ıklad nesynchronizovan´e PC gramatick´e syst´emy a jin´e. Jejich aplikace je vhodn´ a a moˇzn´ a pro popis jak´ ychkoli paraleln´ıch syst´em˚ u napˇr. v kryptografii a podobnˇe. Z´ avˇerem byly zm´ınˇeny i pˇr´ıbuzn´e modely. Jmenovitˇe celkem zaj´ımav´ y koncept ekogramatik, za jejichˇz vznikem stoj´ı snaha o stvoen´ı formalismu pro popis ˇziv´ ych struktur a tak´e test tube syst´emy.

18

References [1] Csuhaj-Varju, E. a. k.: Grammar systems: a grammatical approach to distribution and cooperation. OPA (Amsterdam) B.V., 1994. [2] Csuhaj-Varju, E. a. k.: Grammar systems with WAVE-like communication. Computers and AI, 1996. [3] Csuhaj-Varju, E. a. k.: Grammar Systems. A gramatical approach to distribution and cooperation. Gordon and Breach, London, 2004. [4] Freund, R. a. k.: Test tube systems with cutting/recombination operations. [Online;accessed 16-May-2009]. URL http://helix-web.stanford.edu/psb97/freund.pdf [5] Hillis, W.: The connection machine. The MIT press, Cambridge, Mass., 1985. [6] Rozenberg, G.; Salomaa, A. (editoˇri): Handbook of formal languages Vol. 2 Linear Modeling: Background and application. Springer, Berlin, ISBN 3540-60648-3, str. 528.

19

Seznam zkratek a symbol˚ u PC - parallel communicating CD - cooperating distributed EG - eco gramatiky

20