23
C = (V,T,R), kde V je abeceda kolonie, T je množina terminálních symbolů, T V, R je množina komponent (Si, Fi), Si V, Fi ={fm (V-{Si})*, 1mni}.
Axiom kolonie w0 je libovolný řetězec nad množinou V.
NapříkladC = ({M, N, P, a, b}, {a, b}, R),R = { (M, {PPPN, PPNP, PNPP, NPPP, }), (N, {M}), (P, {a}), (P, {b}) },w0 = MM
KolonieKolonie
Každá komponenta je použita nejvýše jednou, pokud je možné komponentu použít, musí být použita, může existovat více komponent se stejným startovacím symbolem. wp (weakly competitive parallel derivation step): = slabý paralelismus; když je počet výskytů symbolu menší než počet komponent s tímto startovacím symbolem, vybereme tolik komponent, kolik budeme potřebovat.
sp (strongly competitive parallel derivation step): = silný paralelismus; pokud je počet výskytů symbolu menší než počet komponent s tímto startovacím symbolem, výpočet je zablokován.
Paralelní odvozováníParalelní přepisování
R = { (M, {PPPN, PPNP, PNPP, NPPP, }), (N, {M}), (P, {a}), (P, {b}) }w0 = MM
MM wp PPNPM wp PaMb wp bab
MM sp PPNPM sp PaMb sp BLOKOVÁNO
MM sp PPNPM sp PaMbPNPP sp babPMaP sp sp babaab
L1wp = {w {a,b}*; |w|=3n, n0, | |w|a-|w|b | 1}L1sp = {w {a,b}*; |w|=6n, n0, |w|a = |w|b}
Příklad:
COLwp ? COLsp
CF COLsp, CF COLwp
L2 = {aibjaibj; i, j 1} COLsp - CFR = {(A, {aA', a}), (A, {aA', a}), (A', {A}), (A', {A}), (B, {bB', b}), (B, {bB', b}), (B', {B}), (B', {B}) }, w0 = ABABL3 = {aibjck; i, j, k 1, ij, j k, ik} COLwp - CF R = { (A, {aA', aX}), (A', {A}), (B, {bB', bX}), (B', {B}), (C, {cC', cX}), (C', {C}), (Y, {Z}), (Z, {Y}), (X, {}), (X, {Y}), (X, {Y}) }, w0 = ABC
Dosavadní výsledkyDosavadní výsledky
Demonstrační příklady
Krok 1 algoritmu popíšeme na této kolonii:C4wp = ({A, B, C, a, b, c}, {a, b, c}, R), w0 = AAC, R = { (A, {aB, }), (A, {bB, }), (B, {A}), (B, {A}), (C, {a,b,c}) }
Demonstrační příklady
L4 = {w {a,b}*; w = ' nebo w = ', kde ' je inverzí (záměna symbolů a, b)} ° {a,b,c}
Kroky 2 a 3 ukážeme na koloniiC5wp = ({A, B, C, a, b}, {a, b}, R), w0 = BBC, R = { (A, {a, aBC, BCa}), (A, {b}), (B, {AA}), (C, {AAA}) }
L5 = {w {a,b}*; |w| = 5n+2, n1, | |w|a-|w|b | 1}
Použité značení:
SS ... množina symbolů množiny V, které jsou startovacími symboly ve více než jedné komponentě, počet prvků této množiny budeme označovat s,
Sj ... obecně j-tý symbol množiny SS (tj. SS = {S1, S2, ..., Ss}),
k ... počet komponent s tím startovacím symbolem, který je právě zpracováván, obecně můžeme psát k1, k2, ..., ks pro různé prvky množiny SS, pokud není přímo vymezeno, s kterým symbolem právě pracujeme.
Použité značení
Pro každý symbol A SS přidáme nové symboly:
Ve větné formě jevýskytů symbolu A:
1 A(1), A(1,1), A(1,2), …, A(1,k)
2 A(2), A(2,1), A(2,2), …, A(2,počet_dvojic)
3 A(3), A(3,1), A(3,2), …, A(3,počet_trojic)
k A(k), A(k,1)
...
Nové symboly:
a další - pomocné - symboly.
Krok 1Krok 1
Kolonie C4wp: w0 = AAC, R = { (A, {aB, }), (A, {bB, }), (B, {A}), (B, {A}), (C, {a,b,c}) } SS = {A, B}, k1 = k2 = 2.Kolonie C4sp: sudé kroky odvození jsou obrazy kroků v původní kolonii, liché kroky odvození jsou pomocné.
AAC wp aAbAa wp abbBa wp abbAa wp abba
S0 sp A(2)[A,2]A(2)[A,2]CXAXAXBXB
sp A(2,1)[A,2]'A(2,1)[A,2]'C'[A,2]'YA([B,0]')3YB sp ...
wp aBbBa
Ukázka derivace:
sp aB(2)[B,2]bB(2)[B,2]aXAXAXBXB
sp aB(2,1)[B,2]'bB(2,1)[B,2]'a([A,0]')3YA[B,2]'YB
sp aA(2)[A,2]bA(2)[A,2]aXAXAXBXB sp aA(2,1)[A,2]'bA(2,1)[A,2]'a[A,2]'YA([B,0]')3YB
sp abbB(1)[B,1]aXAXAXBXB
sp abbB(1,1)[B,1]'a([A,0]')3YA([B,1]')2YB
sp abbA(1)[A,1]aXAXAXBXB sp abbA(1,2)[A,1]'a([A,1]')2YA([B,0]')3YB
sp abbaXAXAXBXB sp abba
Celá derivaceCelá derivace v kolonii C4sp:
S0 sp A(2)[A,2]A(2)[A,2]CXAXAXBXB
sp A(2,1)[A,2]'A(2,1)[A,2]'C'[A,2]'YA([B,0]')3YB
sp aB(2)[B,2]bB(2)[B,2]aXAXAXBXB
sp aB(2,1)[B,2]'bB(2,1)[B,2]'a([A,0]')3YA[B,2]'YB
sp aA(2)[A,2]bA(2)[A,2]aXAXAXBXB sp aA(2,1)[A,2]'bA(2,1)[A,2]'a[A,2]'YA([B,0]')3YB
sp abbB(1)[B,1]aXAXAXBXB
sp abbB(1,1)[B,1]'a([A,0]')3YA([B,1]')2YB
sp abbA(1)[A,1]aXAXAXBXB sp abbA(1,2)[A,1]'a([A,1]')2YA([B,0]')3YB
sp abbaXAXAXBXB sp abba
Celá derivace v kolonii C4wp:
AAC wp aBbBa wp aAbAa wp abbBa wp abbAa wp abba
Komponenty:
R = {(A, {aB,}), (A, {bB,}), (B, {A}), (B, {A}), (C, {a,b,c})}, w0 = AAC, S S = {A, B}, k1= k2=2.
(C, {C'}), (C', {a,b,c}), (A(1), {A(1,1), A(1,2)}) ,(A(2), {A(2,1)}) ,(A(2), {A(2,1)}) ,
([A,1], {[A,1]'}),([A,2], {[A,2]'}),([A,2], {[A,2]'}),
(B(1), {B(1,1), B(1,2)}),(B(2), {B(2,1)}),(B(2), {B(2,1)})
([B,1], {[B,1]'}),([B,2], {[B,2]'}),([B,2], {[B,2]'}),
([A,0]',{}), ([A,0]',{}), ([A,0]', {XA}), ([A,1]',{}), ([A,1]',{}), ([A,1]', {XA}), ([A,2]',{}), ([A,2]',{}), ([A,2]', {XA}),
(A(1,1), {aB(1)[B,1], aB(2)[B,2], }), (A(1,2), {bB(1)[B,1], bB(2)[B,2], }),(A(2,1), {aB(1)[B,1], aB(2)[B,2], }),(A(2,1), {bB(1)[B,1], bB(2)[B,2], }),
(B(1,1), {A(1)[A,1], A(2)[A,2]}),(B(1,2), {A(1)[A,1], A(2)[A,2]}),(B(2,1), {A(1)[A,1], A(2)[A,2]}),(B(2,1), {A(1)[A,1], A(2)[A,2]}),
([B,0]',{}), ([B,0]',{}), ([B,0]', {XB}), ([B,1]',{}), ([B,1]',{}), ([B,1]', {XB}), ([B,2]',{}), ([B,2]',{}), ([B,2]', {XB}),
(XA, {([A,0]')3YA, ([A,1]')2YA, [A,2]'YA, }),
(XA, {}), (YA, {XA}),
(XB, {([B,0]')3YB, ([B,1]')2YB, [B,2]'YB, }),
(XB, {}), (YB, {XB}),
(S0, {A(2)A(2)CXAXAXBXB})
Použitelnost algoritmu po kroku 1:
Algoritmus můžeme aplikovat na kolonie, kde všechny výskyty symbolů v přepisovaném slově, které lze přepsat, jsou v každém kroku odvození přepsány.
Algoritmus stále ještě není použitelný na kolonie, kde v některých krocích odvození zůstávají nepřepsané (čekající) symboly.
Použitelnost algoritmu po kroku 1
KROK 3
Některý výskyt symbolu Sj SS má zůstat nepřepsán:
Krok 2
[Sj,t,v] t je počet kroků (dvojkroků vytvářené kolonie), po které bude symbol čekat, v je počet symbolů [Sj,t,v] pro určité Sj a t, při změně t se v může zvýšit.
[Sj,-,-]pro symboly, které budou čekat déle, než chceme zachytit číslem t (zde použijeme tyto symboly pro t > k).
Například [A,1,2], [A,3,1]
Pro symboly Si SS vytvoříme navíc symboly [Si,-,-] pro případ, že je ve větné formě více výskytů tohoto symbolu.
Ukázka derivace:
Kolonie C5wp: w0 = BBC,R = {(A, {a, aBC, BCa}), (A, {b}), (B, {AA}), (C, {AAA}) },SS = {A}, k = 2.
BBC
S0 sp [B,-,-]BCXX sp [B,-,-]'B'C'([A,0]')3Y
wp BAAAAA wp AAaAbAA wp bAaAbAa
wp baaAbba wp baabbba
sp ...
sp BA(2)[A,2][A,-,-]A(2)[A,2][A,2,1][A,1,1]XXsp B'A(2,1)[A,2]'[A,-,-]'A(2,1)[A,2]'[A,2,1]'[A,1,1]'[A,2]'Ysp A(2)[A,2][A,1,2]a[A,2,1]b[A,1,2]A(2)[A,2]XX sp A(2,1)[A,2]'[A,1,2]'a[A,2,1]'b[A,1,2]'A(2,1)[A,2]'[A,2]'Ysp bA(2)[A,2]a [A,1,1]bA(2)[A,2]aXX
sp bA(2,1)[A,2]'a [A,1,1]'bA(2,1)[A,2]'a[A,2]')Ysp baaA(1)[A,1]bbaXX sp baaA(1,2)[A,1]'bba([A,1]')2Ysp baabbbaXX sp baabbba
Celá derivace
Celá derivace v kolonii C5sp:
S0 sp [B,-,-]BCXX sp [B,-,-] 'B'C'([A,0]')3Ysp BA(2)[A,2][A,-,-]A(2)[A,2][A,2,1][A,1,1]XX sp B'A(2,1)[A,2]'[A,-,-]'A(2,1)[A,2]'[A,2,1]'[A,1,1]'[A,2]'Y
sp A(2)[A,2][A,1,2]a[A,2,1]b[A,1,2]A(2)[A,2]XX sp A(2,1)[A,2]'[A,1,2]'a[A,2,1]'b[A,1,2]'A(2,1)[A,2]'[A,2]'Y sp bA(2)[A,2]a[A,1,1]bA(2)[A,2]aXX
sp bA(2,1)[A,2]'a[A,1,1]'bA(2,1)[A,2]'a[A,2]')Y
sp baaA(1)[A,1]bbaXX sp baaA(1,2)[A,1]'bba([A,1]')2Y sp baabbbaXX sp baabbba
Celá derivace v kolonii C5wp:
BBC wp BAAAAA wp AAaAbAA wp bAaAbAa wp baaAbba wp baabbba
Komponenty:
R = { (A, {a, aBC, BCa}), (A, {b}), (B, {AA}), (C, {AAA}) },w0 = BBC, SS = {A}, k = 2
(A(1,1), {a, aBC, a[B,-,-]C, aB[C,-,-], a[B,-,-][C,-,-], (A(1,2), {b}), BCa, [B,-,-]Ca, B[C,-,-]a, [B,-,-][C,-,-]a}),
(A(2,1), {a, aBC, a[B,-,-]C, aB[C,-,-], a[B,-,-][C,-,-], (A(2,1), {b}), BCa, [B,-,-]Ca, B[C,-,-]a, [B,-,-][C,-,-]a}),
([A,1]', {}) 2x, ([A,1]', {X}),
([A,1,1], {[A,1,1]'}),([A,1,2], {[A,1,2]'}) 2x,
([A,1], {[A,1]'}), ([A,1,1]', {A(1)[A,1], A(2)[A,2]}),([A,1,2]', {A(1)[A,1], A(2)[A,2]}) 2x,
([A,-,-], {[A,-,-]'}),([A,-,-]', {[A,-,-],[A,2,1],[A,1,2]}),
(A(1), {A(1,1),A(1,2)}),(A(2), {A(2,1)}) 2x,
([A,2], {[A,2]'}) 2x,
([A,2]', {}) 2x, ([A,2]', {X}),([A,0]', {}) 2x, ([A,0]', {X}),
([A,2,1], {[A,2,1]'}),([A,2,2], {[A,2,2]'}) 2x, (X, {([A,0]')3Y, ([A,1]')2Y, [A,2]'Y,}),
(X, {}), (Y, {}),
([A,2,1]', {[A,1,1],[A,1,2]}),([A,2,2]', {[A,1,2]}) 2x,
další komponenty(B', {A(2)[A,2]A(2)[A,2], [A,-,-][A,-,-], A(2)[A,2][A,1,1], A(2)[A,2][A,1,2], ..., A(2)[A,2][A,-,-], [A,1,1]A(2)[A,2], [A,1,2]A(2)[A,2], ..., [A,-,-]A(2)[A,2], [A,1,1][A,2,1], [A,1,1][A,2,2], [A,1,2][A,1,2], [A,1,2][A,2,1], [A,1,2][A,2,2], [A,2,1][A,1,1], [A,2,1][A,1,2], [A,2,2][A,1,1], [A,2,2][A,1,2], [A,2,2][A,2,2], [A,-,-][A,1,1], [A,-,-][A,1,2], [A,-,-][A,2,1], [A,-,-][A,2,2], [A,1,1][A,-,-], [A,1,2][A,-,-], [A,2,1][A,-,-], [A,2,2][A,-,-]}),
(B, {B'}), ([B,-,-], {[B,-,-]'}), ([B,-,-]', {B}),
(S0, {[B,-,-]BCXX, B[B,-,-]CXX})
(C, {C'}), ([C,-,-], {[C,-,-]'}), ([C,-,-]', {C}),
(C', {obdobně, všechny použitelné variace s opakováním délky 3})
Použitelnost algoritmu po kroku 2:
Kolonie po aplikaci algoritmu po krok 2 včetně generuje již všechna slova patřící do jazyka původní kolonie a blokuje generování slov do tohoto jazyka nepatřících, s výjimkou:
pokud pro nějaký symbol Sj SS použijeme v přepisovaném slově pouze symboly [Sj,t,v], resp. [Sj,-,-] (čekající), ale žádný symbol Sj
(k).
Například:R = { (B, {AAB', }), (B', {AAB}), (A, {a}), (A, {b}) }, w0 = B,L = {ab, ba}*
Možnost derivace v původní kolonii nepřípustné:B AAB' AAAAB aAAbAAB' aabbAAAAB …
Použitelnost algoritmu po kroku 2
Řešení:
Čekající symboly nebudou zablokovány, pokud se ve slověnacházejí symboly [Sj,k]'.
Krok 3
Upravíme existující komponenty:
([Sj,k]', {}) ([Sj,k]', {}) ..., ([Sj,k]', {})([Sj,k]', {XSj})([Sj,1,v]', {Sj
(v)[Sj,v], …, Sj(k)[Sj,k]})
([Sj,t,v]', {[Sj,t-1,v], [Sj,t-1,v+1], …, [Sj,t-1,k]})- pro všechna t > 1
([Sj,1,v]', {Sj(v)[Sj,v][Sj,1,-], …, Sj
(k)[Sj,k][Sj,1,-]})([Sj,t,v]', {[Sj,t-1,v][Sj,t,-], [Sj,t-1,v+1][Sj,t,-],…,[Sj,t-1,k][Sj,t,-]})
- pro všechna t > 1, vždy jen jediná komponenta
([Sj,k]', {,[Sj,1,-]}) ([Sj,k]', {,[Sj,2,-]}) ..., ([Sj,k]', {,[Sj,k,-]})([Sj,k]', {XSj, [Sj,-]XSj})
Pro každé Sj SS přidáme nové komponenty:
([Sj,t,-], {}) 2x pro každé t: 1 t k([Sj,-], {}) 2x
Pro každé Si SS přidáme nové komponenty
([Si,-], {}) 2x
Upravíme existující komponenty:
([Si,-,-], {[Si,-,-]'})(Si, {Si'})
([Si,-,-], {[Si,-,-]'[Si,-]})(Si, {Si', Si'[Si,-]})
Tedy v předchozím příkladu přidáme
([B,-], {}) 2x ([C,-], {}) 2x
Upravíme
([B,-,-], {[B,-,-]'[B,-]}) ([C,-,-], {[C,-,-]'[C,-]})(B, {B', B'[B,-]}) (C, {C', C'[B,-]})
L = {anbncn; n1} COLsp – COLwp
Csp = ({A, B, C, A', B', C', D, a, b, c}, {a, b, c}, R)
w0 = ABC,
R = { (A, {aA', aD}), (B, {bB', bD}), (C, {cC', cD}), (A', {A}), (B', {B}), (C', {C}), (D, {}), (D, {}), (D, {}) }.
Doplnění vztahuDoplnění vztahu
ZávěremZávěrem
Důsledkem práce je vztah
COLwp COLsp
Závěrem
Děkuji za pozornost.
