Procesy paralelně komunikujících gramatických systé mů
Pokroč ilá témata z teoretickéinformatiky Zá věrečný projekt
Autor: Ivan Schwarz
Abstrakt: Tato prá ce se zabý vá paralelně komunikujícími gramatický mi systé my (PCGS) a to zejmé na popisem paralelního chová ní a komunikace těchto gramatický ch systé mů . Procesy PCGS jsou definová ny pomocí vý skytový ch sítí s konflikty, které zachycují paralelní chová ní PCGS. V druhé čá sti je uká zá no, že procesy bezkonfliktních PCGS se dají generovat pomocí Petriho sítí a byl popsá n algoritmus, jak takovou síť pro daný PCGS vytvořit.
1 Ú vod V klasické teorii formá lních jazyků a automatů jsou prostředky pro modelová ní vý početních systé mů (gramatiky a automaty) centralizovan é ho charakteru, vý počet je prová děn jedním centrá lním mechanismem. V dnešní době je však největší dů raz kladen na paralelní a distribuované systé my, proto i v teorii formá lních jazyků vznikají prostředky pro popis pojmů jako je komunikace, synchronizace, paralelní běh, atd. Jedním z nich jsou i paralelně komunikující gramatické systémy [2] (PCGS). PCGS stupně n si mů žeme představit jako skupinu n klasický ch gramatik pracujících paralelně. Každá gramatika začíná ze své ho startovacího symbolu a v určitý ch, přesně definovaný ch okamžicích mohou gramatiky vzá jemně komunikovat pomocí speciá lních komunikačních symbolů . V našem případě se nezajímá me o klasické vlastnosti PCGS jako je vý početní síla, protože tyto vlastnosti spíše popisují sekvenční vlastnosti těchto systé mů . Ná s spíše zajímá popis paralelních vlastností, jako je komunikace a synchronizace, než jaký jazyk nakonec gramatický systé m generuje. V té to prá ci jsou představeny procesy PCGS [1] jako prostředek pro popis paralelního chová ní PCGS. Obecně řečeno, proces PCGS získá me tak, že nechá me gramatický systé m běžet a zaznamená vá me jednotlivé okamžiky přepisová ní a komunikace. Z tohoto úhlu pohledu mů žeme vidět podobnost s procesy Petriho sítí, které jsou získá vá ny podobný m způ sobem. V první čá sti prá ce jsou představeny grafy dosažitelnosti a komunikace PCGS, dá le jsou definová ny procesy PCGS a na zá věr je uveden jejich vztah k Petriho sítím.
2 Paralelně komunikujícígramatické systé my V té to prá ci za PCGS považujeme pouze gramatické systé my s regulá rními komponentami. Proto všechny zde uvedené definice se vztahují k prá vě tomuto druhu PCSG. Paralelně komunikující gramatický systém stupně n je systé m n regulá rních gramatik G = (G1 ,Κ , Gn ) , kde: • Gi = ( N i , Ti , S i , Pi ) , 1 ≤ i ≤ n jsou regulá rní gramatiky •
existuje
množina
K = (Q1 , Κ , Qn )
speciá lních
symbolů
zvaný ch
komunikač ní symboly, pro něž platí K ⊆ Υ N i . Žá dný z těchto symbolů nesmí bý t přepsaný a navíc v gramatice Gi nesmí bý t pravidlo obsahující na pravé straně symbol Qi pro všechna i, tj. gramatika nesmí žá dat komunikaci sama od sebe. n i =1
Konfigurace G je n-tice x = ( x1 ,Κ , xn ) , kde xi ∈ T ∗ ( N i ∪ {λ}) pro všechny i, 1 ≤ i ≤ n . Konfigurace ( S1 , Κ , S n ) je nazý vá na poč áteč ní. Ř íká me, že konfigurace ( x1 ,Κ , xn ) přímo derivuje konfiguraci ( y1 ,Κ , yn ) , značíme ( x1 ,Κ , xn ) ⇒ ( y1 ,Κ , y n ) , pokud platí jedna z ná sledujících podmínek: i.
xi
K
= 0 pro všechna i, 1 ≤ i ≤ n a pokud xi obsahuje nonterminá l
a xi ⇒ yi v Gi nebo pokud xi ∈T ∗ a xi = yi ii.
xi
K
> 0 pro některé i, 1 ≤ i ≤ n . Potom pro každé takové i mů žeme
psá t xi = z i Q j , kde z i ∈T ∗ a: •
jestliže x j
K
= 0 , pak yi = z i x j a y j = S j
•
jestliže x j
K
> 0 , pak yi = xi
Pro všechny l, 1 ≤ l ≤ n , pro které není yl definová no vý še, poklá dá me yl = xl Symbolem w K označujeme počet vý skytů symbolů z množiny K v řetězci w. Každý krok derivace se sklá dá buď z přepisovacího kroku (bod i.) nebo z komunikač ního kroku (bod ii.), přičemž komunikační krok má prioritu před krokem přepisovacím. Relace derivace ⇒ ∗ je pak tranzitivní a reflexivní uzá věr relace ⇒ . Tato definice popisuje synchronizovanou navracející PCGS. Gramatický systé m se nazý vá navracející, pokud se po komunikaci navrací gramatika, která poskytla řetězec, k počá tečnímu symbolu. Pokud po komunikaci pokračuje ve větné formě, kterou poskytla, nazý vá se nenavracející. Synchronizovaná PCGS musí v každé m přepisovacím kroku prové st přepsá ní větné formy všemi gramatikami, které mají ve větné formě nonterminá l. Pokud dovolíme při přepisová ní některé gramatice čekat, pak mluvíme o nesynchronizovaném PCGS. Jazyk generovaný PCGS G je L(G) = {w ∈ T ∗ | ( S1 ,Κ , S n ) ⇒∗ ( w, w2 ,Κ , wn )} .
3 Graf dosaž itelnosti a graf komunikace PCGS Dříve než uvedeme definici grafu dosažitelnosti a grafu komunikace PCGS, definujeme si pá r pomocný ch pojmů , které ná m usnadní manipulaci s PCGS. Pro každou konfiguraci x = ( x1 ,Κ , xn ) PCGS definujeme nonterminální řez (n-řez) jako NC ( x) = ( A1 , Κ , An ) , kde xi = xi′ Ai , xi′ ∈ T * a Ai ∈ N i ∪ λ pro 1 ≤ i ≤ n . Pokud n-řez obsahuje komunikační symbol, nazý vá se komunikač ní řez (c-řez). N-řez je dosaž itelný v PCGS, pokud při derivaci z počá teční konfigurace dostaneme konfiguraci obsahující daný řez. Pro dva řezy v1 , v2 píšeme v1 → v2 ,
pokud existují dvě konfigurace x a y takové , že x ⇒ y , NC ( x) = v1 a NC ( y ) = v2 . Nechť v je n-řez. Potom komunikač ní sekvence řezu v je sekvence indexů i1 ,Κ , ik , k ≥ 2 , taková , že v(i1 ) = Qi2 ,Κ , v(ik −1 ) = Qik . Komunikační sekvence se nazý vá ukonč ující, pokud v(ik ) není komunikační symbol, maximální, pokud je ukončující a nelze ji rozšířit doleva a cyklická, pokud v(ik ) = Qi1 . PCGS, která obsahuje alespoň jednu cyklickou komunikační sekvenci se také nazý vá cyklická . Necyklická PCGS, které obsahuje komunikační sekvenci o maximá lní dé lce m, 0 ≤ m ≤ stupeň PCGS , se nazý vá m-komunikující. Konflikt n-řezu v je posloupnost rů zný ch indexů i1 , i2 , i3 taková , že v(i1 ) = Qi2 a v(i3 ) = Qi2 . Pokud žá dný dosažitelný n-řez gramatické ho systé mu neobsahuje konflikt, pak mluvíme o bezkonfliktním PCGS. Nechť G je PCGS. Pak graf dosaž itelnosti G popisuje jaké n-řezy jsou dosažitelné z počá teční konfigurace a přechody mezi nimi a značíme ho Reach(G). Algoritmus vytvoření grafu dosažitelnosti: • vezmi všechny n-řezy a nakresli hranu z řezu v1 do řezu v2 , pokud platí v1 → v2 • odstraň všechny n-řezy v, pro které neexistuje cesta z počá tečního řezu do řezu v. Odstraň také všechny korespondující hrany. V případě nenavracejících se PCGS není tato definice grafu dosažitelnosti zcela adekvá tní, protože graf obsahuje "nepoužitelné " uzly, protože po dosažení řetězce terminá lů první gramatiky už derivace PCGS nepokračuje. V navracející PCGS si mů že některá z dalších gramatik požá dat o řetězec první gramatiky a první gramatika pak pokračuje ze své ho startovacího symbolu. Abychom sjednotili definici grafu pro oba dva typy PCGS, použili jsme obecnější variantu definice. Z grafu dosažitelnosti mů žeme získat několik informací o PCGS. Nechť G je PCGS. Pak n-řez v je dosažitelný v G, pokud je obsažen v Reach(G). Dá le jsou rozhodnutelné problé my, zda PCGS je: i. cyklická ii. bezkonfliktní iii. m-komunikující iv. centralizovaná v. obsahuje omezený počet komunikací během derivace Tyto problé my lze rozhodnout prozkoumá ním každé ho uzlu grafu dosažitelnosti, který je konečný (vyplý vá to z konečnosti množiny nonterminá lů ). Z grafu dosažitelnosti lze odvodit graf komunikace. Tento graf zaznamená vá v derivační posloupnosti pouze komunikační kroky. Z grafu dosažitelnosti ho získá me tak, že ponechá me pouze uzly, obsahující komunikační symboly a počá teční uzel. Pak pro dva takové uzly v1 , v2 nakreslíme hranu z v1
do v2 , pokud mezi nimi v pů vodním grafu existuje cesta, která neobsahuje komunikační řezy. Komunikační graf PCGS G značíme Comm(G). Př íklad 1 Nechť G je ná sledující PCGS: G1 : S1 → Q2 G2 : S 2 → Z 2 Z2 → Z3 Z 2 → Q3 Z3 → Z4 Z4 → Z2 Z 4 → Q2 Z4 → a
G3 : S 3 → aQ2 Z2 → Z3 Z3 → Z4
Graf dosažitelnosti gramatické ho systé mu G je pak:
S1 S2 S 3
λ Z2 Q 2
Q2 Z2 Q 2
Z2 S2 Z 2
λ S2 Z 2
Z3 Z2 Z 3
λ Z2 Z 3
Z4 Q3 Z 4
Z4 Z4 S 3
λ Q3 Z 4
λ Z4 S 3
λ Z2 Q 2
λ Q3 Z 4
a odpovídající graf komunikace má pak tvar:
S1 S2 S 3
Q2 Z2 Q 2
Z4 Q3 Z 4
4 Procesy PCGS Procesy PCGS slouží k zachycení paralelního chová ní a komunikace gramatický ch systé mů . Procesy jsou stejně jako procesy Petriho sítí definová ny pomocí vý skytový ch sítí. Síť je trojice N = ( B, E , R) , kde B a E jsou dvě konečné , neprá zdné a disjunktní množiny míst a přechodů a R ⊆ ( B × E ) ∪ ( E × B) je toková relace. Pro všechny x ∈ B ∪ E značíme • x = { y | ( y, x) ∈ F } a x • = { y | ( x, y ) ∈ F } . Vý skytová síť je síť, která navíc splňuje podmínky: • |• b |≤ 1 a | b • |≤ 1 pro všechna b ∈ B • relace R + je acyklická Slovně mů žeme tyto podmínky vyjá dřit tak, že každé místo má nejvý še jednu vstupní a vý stupní hranu a síť neobsahuje cykly. U vý skytové sítě místa označujeme jako podmínky a přechody jako události. Pokud je N je vý skytová síť, pak definujeme koncový řez té to sítě jako množinu N ο = {b ∈ B || b • |= 0} . Vý skytové sítě slouží pro popis procesů Petriho sítí. Konflikty v PCGS se řeší jiný m způ sobem než v Petriho sítích. Zatímco v Petriho sítích se konflikt řeší tak, že se ná hodně vybere jeden přechod, který se provede, v PCGS je konflikt řešen rovnocenně pro všechny gramatiky zapojené v konfliktu a komunikace proběhne paralelně. Proto pro popis procesů PCGS používá me vý skytovésítě s konfliktem (značíme cfON), což jsou sítě, pro něž platí pouze podmínka acykličnosti. Jako pomocný pojem si pro PCGS G zavedeme množinu Var(G,i) = {v(i ) | v je uzel grafu Reach(G) a v(i ) ≠ λ} . Tato množina obsahuje všechny nonterminá ly, které se mohou vyskytnou ve větné formě gramatiky Gi . Poté si mů žeme definovat značenou vý skytovou síť s konfliktem, kterou pak použijeme k popisu procesu PCGS. Značená cfON je síť π = ( N , p ) , kde p je značící funkce, která zobrazuje podmínky do množiny {i A | 1 ≤ i ≤ n, A ∈ Var(G,i) ∪ {⊥}} a udá losti do množiny T ∪ {λ} ∪ {C i , j | ∃v uzel grafu Reach(G) : v(i ) = Q j } ; levý horní index i označuje gramatiku, znak ⊥ označuje řetězec terminá lů a znak Ci , j značí, že gramatika Gi žá dá gramatiku G j o komunikaci. Udá lost označenou Ci , j potom nazý vá me jako komunikač ní událost a podmínku označenou Qi jako komunikač ní podmínku. Samotné procesy PCGS pak definujeme induktivním způ sobem: Nechť G = (G1 ,Κ , Gn ) je navracející synchronizovaná PCGS stupně n, n ≥ 1 . Potom definujeme posloupnost množin značený ch cfON Π 0 (G), Π 1 (G), Κ ná sledujícím způ sobem: 1. Π 0 (G) sestrojíme tak, že do ní vložíme značenou cfON π = ( N , p ) s těmito vlastnostmi:
a)
B = n, E = 0, R = 0
b) pro každé i, 1 ≤ i ≤ n, existuje b ∈ B takové , že p(b) ∈ S i 2. předpoklá dejme, že množina Π i (G), i > 0 už byla úspěšně zkonstruová na. Potom pro každou π = ( N , p) ∈ Π i (G ), N = (B, E, R) dělej: a) pokud π ο neobsahuje žá dnou komunikační podmínku a existuje b ∈ π ο takové , že p(b) = i X pro nějaké i a X ≠⊥ a neexistuje řá dné pravidlo v gramatice Gi , které má X na levé straně, pak nelze z π vygenerovat žá dný nový proces; b) pokud π ο neobsahuje žá dnou komunikační podmínku a není splněna podmínka uvedená v odstavci a), pak pro každé b ∈ π ο takové , že p(b) ∉{i ⊥| 1 ≤ i ≤ n} a p(b) = i X vezmi libovolné pravidlo tvaru X → uY ∈ Gi a vytvoř novou udá lost e označenou u se vstupní podmínkou b a vý stupní podmínkou b′ označenou iY , pokud Y ∈ N i nebo značenou i ⊥ pokud Y = λ ; c) pokud π ο obsahuje komunikační podmínky, pak pro každou ukončující komunikační sekvenci dé lky dvě i1 , i2 vytvoř novou udá lost e značenou Ci1 ,i2 se vstupními podmínkami sítě π ο značený mi
i1
Qi2 a
i2
X pro nějaké X a se dvěmi vý stupními
podmínkami značený mi i1 X a S i2 , tak jak je naznačeno na obrá zku 1. Nechť π ′ je takto získaná značená cfON, pak Π i +1 (G) je množina všech π ′ získaný ch popsaný m postupem. Procesy gramatiky G je pak množina Π (G) = Υ i≥0 Π i (G). i1
Qi2
i1
X
Ci1 ,i2
i2
Si2
X Obrázek 1
Ve vý še uvedené m algoritmu bod 2. a) ošetřuje situaci, kdy se derivační sekvence gramatiky zablokuje z nedostatku patřičné ho pravidla. Avšak procesy vzniklé před zabloková ním gramatické ho systé mu považujeme za řá dné procesy, i když nevedou k vygenerová ní řetězce nonterminá lů . Bod 2. b) rozšiřuje už existující procesy o jeden přepisovací krok a bod 2. c) o jeden komunikační krok. Př íklad 2 Nechť G je PCGS stupně 3 s ná sledujícími komponentami: G1 : S1 → aX G2 : S 2 → Q1 G3 : S 3 → Q1 S1 → Q2 X → Q3 X → X1 X1 → X X1 → λ Jeden z procesů gramatické ho systé mu G je pak vyobrazen na obrá zku 2. a
S1
1
X
S1
λ
1
λ
2
2
Q1
X
λ
2
λ
3
Q1
2
Q3
C3,1 S3
λ
1
S2
λ
2
λ
3
⊥
C1,2
C2,1 S2
X
1
Q2
X1
Q1
C2,3 3
X
λ
3
X1
S3
Q1
Obrázek 2 Koneč ný proces gramatické ho systé mu G je takový proces π , který má vlastnost 1 ⊥∈ π ο . Třídu konečný ch procesů pak značíme Π f (G). Vý še uvedenou definici procesu lze lehce modifikovat i pro nenavracej ící a nesynchronizované PCGS: • pro nenavracející PCGS musíme nahradit symbol S i2 v bodě 2. c) •
symbolem i2 X pro nesynchronizované PCGS musíme odstranit celý bod 2. a) a v bodě 2. b) nahradit větu "a není splněna podmínka uvedená v odstavci a), pak
pro každé b ∈ π ο takové , že p(b) ∉{i ⊥| 1 ≤ i ≤ n} " větou "vezmi nějaké b ∈ π ο takové , že p(b) ∉{i ⊥| 1 ≤ i ≤ n} a pro toto b"
5 Vztah PCGS a Petriho sítí V té to kapitole si uká žeme, jak vytvořit Petriho síť, jejíž proces je stejný jako daný PCGS. Abychom mohli Petriho sítí simulovat prioritu komunikačního kroku nad přepisovacím, zavedeme Petriho síť s prioritami. Síť s prioritami je taková síť N = (Σ, p ) , kde Σ je klasická Petriho síť a p je čá stečné uspořá dá ní nad přechody Σ . Odpalovací pravidlo je pak modifiková no tak, že mů žeme prové st pouze ty přechody t, pro které platí ¬(t1 pt ) pro všechna t1 ∈ T . Pro simulaci synchronizované PCGS musíme zavé st Petriho síť s maximální odpalovací strategií, což je klasická Petriho síť s odpalovacím pravidlem pozměněný m tímto způ sobem: při dané m značení vyber maximá lní množinu současně proveditelný ch přechodů a ty proveď v jednom kroku. Poté mů žeme zkombinovat priority s maximá lní odpalovací strategií tímto způ sobem. Nechť M je značení, pak vyber množinu přechodů T ′ ⊆ T takový ch: a) T ′ je maximá lní množina neporovnatelný ch přechodů vzhledem k uspořá dá ní p proveditelný ch při značení M b) jestliže T ′′ je množina splňující podmínku a), T ′′ ≠ T ′ , pak t ′pt ′′ pro všechna t ′ ∈ T ′ a t ′′ ∈ T ′′ . Potom proveď množinu značení T ′ v jednom kroku . Síť s takto vytvořený m odpalovacím pravidlem se pak nazý vá Petriho síť s prioritami a s maximální odpalovací strategií. Algoritmus převodu neblokující bezkonfliktní synchronizované ho PCGS G na Petriho síť s prioritami a s maximá lní odpalovací strategiíN takovou, že G i N mají stejné procesy. Nechť G = (G1 ,Κ , Gn ) , n ≥ 1 je takový PCGS, pak mů žeme zkonstruovat síť N = (Σ, p, M 0 , l ) ná sledujícím způ sobem: • •
pro každé i, 1 ≤ i ≤ n a X ∈ Var(G,i) ∪ {⊥} vytvoříme místo i X (v případě, že X = S i pak toto místo značíme S i ) pro každé i, 1 ≤ i ≤ n a každé pravidlo r : X → uY ∈ Pi , (u ∈T ∪ {λ})
•
vytvoříme přechod t ri značený symbolem u; a vytvoříme hrany takové : • i t r ={i X } a (t ri ) • ={i Y } . V případě pravidla X → u vytvoříme hranu (t ri ) • ={i ⊥} pro každé i, 1 ≤ i ≤ n a Q j ∈ N i (pokud takové Q j existuje) a každé X ∈ Var(G,i) ∪ {⊥} vytvoříme přechod t iX, j značený symbolem C i , j ; a vytvoříme příslušné hrany • t iX, j ={i Q j , j X } a přechody pak nazý vá me komunikač ní přechody
(t iX, j ) ={i X , S j } . Tyto
• •
vá ha všech hran je 1 počá teční značení M 0 má ná sledující tvar:
1, pokud s ∈ {S i | 1 ≤ i ≤ n} M 0 ( s) = 0, v ostatních případech pro všechna místa s • všechny komunikační přechody mají prioritu nad ostatními přechody, čá stečné uspořá dá ní p je definová no takto: tpt ′ , prá vě když t je komunikační přechod a t ′ není Př íklad 3 : Petriho síť odpovídající navracejícímu PCSG z příkladu 2 je zobrazena na obrá zku 3. S1
S3
C2,1
a 1
λ
C3,1
X
3
λ
Q1
C3,1 1
Q2
3
C1,2
X
C2,3 λ
λ 1
X1
3 2
S2 λ
1
⊥
Q1
2
2
X
λ
λ
Obrázek 3
Q3
X1
6 Závěr V té to prá ci jsme uká zali způ sob, jaký m lze popsat paralelní chová ní a komunikaci paralelně komunikujících gramatický ch systé mů pomocí procesů . Proces PCGS je reprezentová n vý skytovou sítí s konflikty, která je vytvořena zaznamená ním evoluce PCGS. Definovali jsme procesy pro více variant PCGS (synchronizované , nesynchronizované , navracející a nenavracející). V druhé čá sti jsme uká zali vztah mezi PCGS a Petriho sítěmi. Uká zali jsme, ke každé bezkonfliktní PCGS lze vytvořit Petriho síť, která má stejný proces, tj. z hlediska paralelního chová ní reprezentuje stejný systé m.
Literatura [1] Tiplea F.L., Katsura M., Ito M.: Processes and Vectorial Characterizations of Parallel Communicating Grammar Systems, Journal of Automata, Languages and Combinatorics 1, 1997, 47-73 [2] Dassow J., Paun G., Rozenberg G.: Grammar Systems
