9.2. Az input értelmezése és a számítás menete P-automatában

A P-automata tulajdonképpen egy szimport-antiport rendszer. Az inputot úgy értelmezzük, mint a rendszerbe belépő objektumokból írható szavakat, az automata pedig általában egyes inputokat elfogad, másokat pedig nem. Az elfogadás megadott elfogadási konfigurációkkal történhet. A multihalmazok membránszámítások során szokásos sztring reprezentációját használva, bármelyik olyan szót használhatjuk, aminek Parikh képe a reprezentálandó multihalmaz (hasonlóan ahhoz, mint amikor hagyományos formális nyelvet generáltunk a környezetbe küldött szimbólumok segítségével).

Egy membránból álló P-automata egy rendezett -es, ahol

A P-automata konfigurációi multihalmaz -esek, hasonlóan a többi membránrendszerhez. Azt mondjuk, hogy a konfigurációból közvetlenül elérhető a konfiguráció (jelben: ), ha minden régióra teljesül az, hogy maximális számú szabályt hajtunk benne végbe (azaz a konfigurációban nem marad ki annyi objektum egyik régióban sem, amikre nem alkalmazunk szabályt, hogy még egy szabályalkalmazás lehetséges legyen a rendszerben a megadottakkal egyszerre). Ezt a működést maximális párhuzamos működésnek nevezzük. Egy ilyen lépés során a legkülső membránon beáramló multihalmazt (illetve az ennek megfelelő valamely sztringet) tekintjük az adott lépésben feldolgozott inputnak. Általában megadunk egy függvényt, ami minden lehetséges egy lépésben beszívott -beli sztringekkel reprezentált multihalmazhoz megmondja, hogy az milyen -beli input(ok)nak felel meg, így még általánosabbá téve a modellt (megengedve például, hogy az elfogadott nyelv ábécéje diszjunkt legyen a membránrendszer ábécéjétől). Az inputként feldolgozott objektumok a környezetből, ami feltételezésünk szerint mindenféle objektumból elegendőt tartalmaz, lettek beszívva. Ha az automata olyan konfigurációba jutott, ami eleme az előre definiált elfogadó-konfiguráció halmaznak, akkor az eddig a pontig feldolgozott inputot, vagyis a lépésenként feldolgozott inputrészek konkatenációját elfogadja az adott futással. Azon inputok halmaza, amire van elfogadó futása -nek, alkotják az , az automata által függvénnyel elfogadott nyelvet. A P-automaták esetén nem adott előre az input, amin az automata dolgozik, hanem az automata a megadott szabályrendszer alapján szívja be a környezetből az inputbetűket reprezentáló objektumokat, ily módon a rendszer valahol az elfogadó és a generáló rendszerek közt foglal helyet.

9.2.1. Példák P-automatára

Lássunk most egy példát P-automatára.

Legyen . A rendszert a 9.1. ábra szemlélteti.

9.1. ábra - P-automata, ami az input P-automata, ami az input -k és -k számát méri. -k és P-automata, ami az input -k és -k számát méri. -k számát méri.

P-automata, ami az input -k és -k számát méri.

A kezdő konfigurációból az első membrán két szabálya közül az egyik egyszeri a lkalmazásával jutunk a következő konfigurációba: egy vagy egy is bekerült a mellé az első régióba. Továbbra is csak egyetlen van, tehát továbbra is csak egyetlen szabály használható, eközben ha már és is van az első régióban, akkor a második régió szabályával a második régióba is kerülnek objektumok, de mindig csak egyszerre lép be egy és egy . A második régió szabályával a is bevihető a második régióba. Ekkor, ha az első régióból minden és is bekerült ide, és csak ekkor, a rendszer elfogadó konfigurációba kerül. (Itt jegyezzük meg, hogy valójában az elfogadó konfiguráció ellenőrzéséhez elegendő az első membrán ürességét megvizsgálni, valójában a második membránra nem adtunk feltételt.) Mivel nincs további alkalmazható szabály a rendszer meg is áll ebben a konfigurációban. Ekkor tehát pont annyi van a második régióban, mint , illetve az egyetlen is ott van. Ha az függvény olyan, hogy az egy lépésben beszívott (multi)halmaz elemeit bármilyen sorrendbe írhatjuk le sztringként, akkor a következőképpen adhatjuk meg a generált nyelvet (itt jegyezzük, meg, hogy ez az függvény nemdeterminisztikusnak tekinthető, vagyis pl. a -val leírt multihalmazhoz a sztringek halmazát rendeli). Mivel az és beolvasások tetszőleges sorrendben történhettek, csak az a fontos, hogy azonos számban, így az elfogadott nyelv: . Amennyiben az input értelmezésekor az függvény segítségével értelmezzük az elfogadott nyelvet, ami egyszerűen törli (figyelmen kívül hagyja) a beolvasott -ket, vagyis , (az determinisztikus, egyelemű halmazokat rendel a különböző lehetséges multihalmazokhoz, így a halmaz-zárójelet a szokások szerint elhagyhatjuk), akkor (ekkor az elfogadott nyelv a ábécé feletti. -t tartalmaz).

A P-automatákat szekvenciális módon is használhatjuk, ekkor minden egyes régióban pontosan egy szabályt kell végrehajtani egyszerre (kivéve azokat a régiókat, ahol nincs alkalmazható szabály). Az előző példa speciális, abban az értelemben, hogy esetében a szekvenciális működés is ugyanazokat az elfogadott nyelveket jelenti, akár az , akár az függvény segítségével definiáljuk az elfogadott nyelvet, mint a maximálisan párhuzamos működés.

Az előző automatával elfogadott nyelv nem reguláris környezetfüggetlen nyelv.

9.2. ábra - P-automata a zárójelek nyelvéhez.

P-automata a zárójelek nyelvéhez.

Tekintsük most a 9.2. ábrán látható P-automatát, ahol az elfogadó konfigurációkban az első membrán üres, a második membrán tartalma pedig -beli. Továbbá legyen , vagyis a zárójel szimbólumok, azaz feletti nyelvet fogadunk el. Tekintsük a rendszer szekvenciális működését. Kezdetben a rendszerbe a kifele történő mozgása (illetve ki-be ingázása) közben -k ( multihalmaz beszívásával) áramolhatnak be, illetve ha van a rendszerben, akkor beszívása is történhet egy eltávolítása közben. Elfogadni akkor tud a rendszer, ha nincs benne, illetve az első szabállyal a -től is megszabadultunk. Minden elfogadó futásra teljesül tehát, hogy nincs további alkalmazható szabály, illetve pont annyi beszívása történt a rendszerbe, mint ahány beszívása, illetve soha nem fordulhatott elő az, hogy addig az időpontig a -kből többet szívott be a rendszer, mint az -kból. Ez a P-automata tehát az függvény segítségével a korrekt zárójel-kifejezések nyelvét fogadja el, ahol a nyitó és a záró párja.

Most példát adunk egy nem környezetfüggetlen nyelv elfogadására kihasználva a maximális párhuzamosságot.

Legyen . A rendszer felépítése a lehető legegyszerűbb, determinisztikusan először két jön be. Ezután minden lépésben az előző lépésben bejövő -k kétszerese lép be. Minden konfiguráció elfogadó konfiguráció is egyben, így elfogad minden lehetséges inputot. Tehát az elfogadott nyelv: , ha az „identikus” leképezés, vagyis az sztringet jelenti, ha darab -t szívott be a rendszer az adott lépésben.

Figyeljük meg, hogy az elfogadás, illetve az ennek megfelelő konfiguráció(k) nem feltétlenül esik/nek egybe a megálló, beragadó, nem folytatható, vagyis halott konfigurációkkal. Ennek megfelelően általában egy adott rendszerhez teljesen más nyelv definiálható, ha pl. elfogadó számításoknak azokat a számításokat fogadjuk el, mint ahogy azt a korábbi membránrendszerek és membránszámítások esetén is tettük, amelyek nem folytathatóak. Tehát a meghalt konfigurációk segítségével is lehet és szokás elfogadott nyelveket definiálni.

Itt jegyezzük meg, hogy amennyiben a számítás olyan, hogy nincs korlátozva az egy lépésben beolvasható input multihalmazok száma (pl. ilyen az előző példa), akkor pl. függvény használatával akár végtelen ábécé feletti inputot is feldolgozhatunk/értelmezhetünk.

9.2.2. P-automaták gátló és segítő multihalmazokkal

A P-automaták általános változataiban, tovább növelve alkalmazhatóságukat, a szabályok mellé gátló vagy segítő multihalmazokat adhatunk meg. Gátló multihalmaz esetén az adott szabály csak akkor alkalmazható, ha a multihalmazt nem tartalmazza az adott régió. Segítő multihalmaz esetén a szabály csak akkor alkalmazható, ha az adott membrán tartalmazza az adott multihalmazt (vagyis annak minden elemét legalább a megfelelő példányszámban).

Formálisan a szabályokhoz adott feltételek a következőképpen néznek ki:

  • , ahol a segítő multihalmaz, ekkor az adott régióban a szabály csak akkor alkalmazható, ha a multihalmaz részhalmaza a jelenlegi konfigurációban az adott membránban levő objektumok multihalmazának;

  • , ahol a gátló multihalmaz, ekkor az adott régióban a szabály nem alkalmazható, ha a multihalmaz részhalmaza a jelenlegi konfigurációban az adott membránban levő objektumok multihalmazának.

Értelemszerűen, ha a üres multihalmazt jelent, vagyis, , akkor az adott szabályra nincs sem gátló, sem segítő feltétel.

Lássunk most egy példát ilyen segítő-, illetve gátló multihalmazok használatára.

9.3. ábra - P-automata segítő és gátló multihalmazokkal.

P-automata segítő és gátló multihalmazokkal.

Legyen , ahol elfogadó konfigurációt nem adunk meg, a rendszer azzal a konfigurációval fogad el, amire nincs alkalmazható szabály. A 9.3. ábrán is látható a rendszer, aminek a maximálisan párhuzamos működése a következő:

  • Először a szabályt kell alkalmazni, miáltal lesz a membrán tartalma (így maga a konfiguráció is, mivel csak egyetlen membrán van a rendszerben).

  • Ezután a és a szabályok bármelyike alkalmazható, az első -szeri, majd a második egyszeri alkalmazásával előbb az , majd az konfigurációhoz jutunk.

  • Ekkor az első két szabály már nem alkalmazható, a negyedik pedig még nem ( esetén, mivel vannak -k a membránban, ha , akkor már itt a következőként leírt lépés jön), tehát a harmadik szabályt lehet és kell alkalmazni ( esetben): mivel van a membránban, minden -t kiküldünk, és helyükre -ket szív be a rendszer, így egy lépésben a konfiguráció áll elő.

  • Ha a konfiguráció csak -ket tartalmaz, akkor csak az utolsó szabály alkalmazható, ami az összes -t -re cseréli, ezzel egy lépésben előállítva a halott konfigurációt, ugyanis erre nincs a rendszerben alkalmazható szabály.

Legyen az függvény a következőképpen definiálva: és (minden esetén), így a számítási lépésekben beszívott szimbólumok alapján könnyen látható, hogy az automata által elfogadott nyelv: . Ez a nyelv egy köztudottan nem környezetfüggetlen nyelv.

Egyes változatokban lehetőségünk van a gátló és segítő feltételek kombinált alkalmazására is. Ugyancsak használhatóak aktív membránok a P-automatáknál is, melyek segítségével a számítás során maga a membránstruktúra is megváltozhat.