7.3. Multihalmazok és számítások: Parikh nyelvek

Egy rendezett ábécé felett adott szó Parikh vektorát definiáljuk a következőképpen: egy -dimenziós vektor, ahol és az ábécé . betűjét pontosan -szer tartalmazza. Egymás kommutatív képeinek, vagy betűekvivalensnek nevezünk két szót, ha a betűik sorrendjének átrendezésével az egyikből a másikat előállíthatjuk. A betűekvivalens szavak Parikh vektora megegyezik. Tulajdonképpen a szó kommutatív képeinek halmaza jellemezhető a Parikh vektorral, mintha a sztringekben a betűk sorrendje nem számítana: így multihalmaz adatszerkezettel írhatjuk le őket. Éppen ezt jelentik a Parikh vektorok. Például az rendezett ábécé feletti szó Parikh vektora: , mivel a szó 4 , 3 és 1 betűt tartalmaz. Tehát egy Parikh vektor bijektív módon ad meg egy multihalmazt (rendezett ábécé fölött).

Adott nyelv, az nyelv Parikh halmazát a következőképpen definiáljuk: . Egy nyelv Parikh halmaza tehát a nyelv szavainak Parikh vektorait tartalmazó halmaz.

Két ugyanazon rendezett ábécé felett értelmezett nyelvet betűekvivalensnek nevezünk, ha Parikh halmazaik megegyeznek. Ekkor a két nyelv bármelyikében találunk a másik minden egyes szavához olyan szót, hogy és legfeljebb a betűk sorrendjében tér el.

Legyen az ábécénk számossága . Egy nyelvet (Parikh értelemben) lineárisnak nevezünk, ha Parikh halmaza lineáris, vagyis teljesül rá a következő feltétel: van darab olyan -dimenziós vektor ( ), hogy .

Egy nyelv szemilineáris, ha Parikh halmaza lineáris halmazok véges uniója.

Közismert Parikh tétele, hogy minden környezetfüggetlen nyelv szemilineáris. Továbbá ismert, hogy minden szemilineáris nyelvhez van vele betűekvivalens reguláris nyelv. Ennek következtében, az egybetűs ábécé felett minden környezetfüggetlen nyelv egyben reguláris nyelv is. Továbbá, ha egy nyelv nem-szemilineáris (ilyen pl. a nyelv) akkor az nem lehet környezetfüggetlen.

Mivel a membránok a bennük levő vegyületek multihalmazát tartalmazzák, a membránszámításokat tulajdonképpen multihalmaz-számításoknak is nevezhetjük. Tehát tulajdonképpen nyelvek helyett azok Parikh halmazaival dolgoz(hat)unk. Tehát a reguláris és környezetfüggetlen nyelvek halmazainak (mindkettőnek) a szemilineáris (vektor)halmazok felelnek meg. A rekurzívan felsorolható nyelvek Parikh képei alkotják a kiszámítható (vektor)halmazokat, vagyis a kiszámítható multihalmazok osztályát.

Most térjünk vissza a membrán modellhez, és nézzük milyen lépésekből áll a számítás.