10.2. Nyelvtanok párhuzamos kommunikáló rendszerei – PC nyelvtanrendszerek

(Parallel Communicating Grammar Systems – PC grammar systems)

Ebben az alfejezetben generatív nyelvtanok PC rendszereibe nyújtunk rövid betekintést.

28. Definíció. Egy PC nyelvtanrendszer egy n rendű (n ≥ 1) rendszer P C=(N, K, T, (S 1, H 1), …, (S n , H n )), ahol N és T a nemterminális és a terminális ábécék, K={Q 1, …, Q n } kérdőszimbólumok, az i- edik komponenshez Q i , ( N, T és K páronként diszjunkt halmazok), a H i halmazok levezetési szabályok véges halmazai (NTK) ábécé felett úgy, hogy K-beli elem nem állhat szabály bal oldalán. Valamint a komponensek mondatszimbólumai S i N (minden 1 ≤ i ≤ n esetében). ★

29. Definíció. Adott egy PC nyelvtanrendszer P C=(N, K, T, (S 1, H 1), …, (S n , H n )). A (p 1, …, p n ) és (q 1, …, q n ) két elem n-esre, ahol p i , q i ∈(NTK)* minden 1 ≤ i ≤ n- re és p 1T *- ra, a közvetlen levezethetőség fennáll, ezt (p 1, …, p n )⇒(q 1, …, q n ) alakba írjuk, ha a következő két eset egyike fennáll:

  1. Minden i értékre (1 ≤ i ≤ n) p i ∈(NT)*, továbbá p i q i a H i egy levezetési szabálya segítségével, vagy p i =q i ha p i T *.

  2. Amennyiben van olyan i, amelyre p i tartalmaz K- beli elemet, akkor minden ilyen i- re járjunk el a következőképpen: legyen p i =r i, 1 Q i, 1 r i, 2 Q i, 2r i, k Q i, k r i, k+1 (valamilyen k ≥ 1 mellett), ahol r i, j ∈(NT)* minden j- re ( 1 ≤ j ≤ k+1 ). Ha p i, j ∈(NT)* minden j értékre ( 1 ≤ j ≤ k+1 ), akkor legyen q i =r i, 1 p i, 1 r i, 2 p i, 2r i, k p i, k r i, k+1, és legyen q i, j =S j minden j értékre ( 1 ≤ j ≤ k+1 ).

Minden egyéb esetben legyen q i =p i .★

A ( p 1, …, p n ) elem n- est a PC rendszer konfigurációjának hívjuk. Tehát a ( p 1, …, p n ) konfigurációból közvetlenül levezethető a ( q 1, …, q n ) a következő két esetben:

Az első eset, amikor egyik aktuális mondatforma sem tartalmaz K- beli szimbólumot, a levezetés komponensenként zajlik, kivéve azokat a p i mondatformákat, amik csak terminálisokat tartalmaznak, ugyanis azok változatlanul maradnak.

A második eset, amikor kérdőszimbólum fordul elő valamely mondatformában. Ekkor a következő kommunikációs lépés zajlik le: a Q i minden előfordulásának helyére p i kerül (feltéve hogy p i nem tartalmaz kérdőszimbólumot). Pontosabban egy kérdőszimbólumot tartalmazó mondatforma csak akkor módosul, ha benne minden kérdőszimbólum olyan mondatformára utal, amely nem tartalmaz kérdőszimbólumot. Egy kommunikációs lépésben p j - vel helyettesítjük a Q j szimbólumot (a Q j kérdést megválaszoltuk), és a j- edik komponens elölről kezdi a számítást az S j axiómájából (vagyis a kezdőszimbólumából). A kommunikációs lépésben nem zajlik komponensenkénti levezetés, levezetési szabályokat nem alkalmazhatunk, ha valamely mondatforma tartalmaz kérdőszimbólumot. Ha egy kérdőszimbólumot nem tudunk megválaszolni egy adott lépésben, előfordulhat, hogy a következő lépésben meg tudjuk válaszolni.

Fontos, hogy a rendszerben nem lehet olyan szabály, aminek a baloldalán kérdőszimbólum fordul elő, így a kérdések csak kommunikációs lépéssel válaszolhatóak meg, a levezetés csak így folytatódhat. Ugyancsak fontos, hogy nincs definiálva a közvetlen levezetés arra az estre, ha p 1T *. A ⇒ közvetlen levezetés tranzitív és reflexív lezártját ⇒*- al jelöljük és, szokásos módon, levezetésnek nevezzük.

Egy PC rendszer működése során a következő holtponti szituációk jöhetnek létre:

  1. Nincs kérdőszimbólum, de valamely p i T * mondatformára nincs alkalmazható levezetési szabály.

  2. Körbe-kérdezés jön létre, vagyis p i, 1- ben szerepel Q i, 2, p i, 2- ben viszont Q i, 3, és így tovább, amíg valamely p i, k a Q i, 1- et tartalmazza. Ilyenkor sem kommunikációs lépés, sem komponensenkénti levezetés nem alkalmazható.

30. Definíció. Adott egy PC nyelvtanrendszer P C=(N, K, T, (S 1, H 1), …, (S n , H n )). Ekkor az általa generált nyelv L(P C)={wT * | (S 1, S 2, …, S n )⇒*(w, p 2, …, p n ) valamely p i ∈(NTK)* mondatformákra ( 2 ≤ i ≤ n ) }. ★

Tehát kiindulunk a mondatszimbólumokból és komponensenkénti levezetési, illetve kommunikációs lépésekkel haladunk, amíg az első komponens nem terminál (vagy holtpontra nem jut a rendszer). Az első komponens tehát megkülönböztetett szereppel bír, mesternek nevezzük.

31. Definíció. Ha egy P C=(N, K, T, (S 1, H 1), …, (S n , H n )) PC nyelvtanrendszerben csak az első (mester) komponens vezethet be kérdőszimbólumot, akkor központosított PC rendszerről beszélünk, egyébként a PC rendszer nem központosított. ★

Központosított rendszer esetén az általunk fentebb ismertetett második típusú holtpont nem állhat elő.

Egy PC rendszert akkor nevezünk lineárisnak, környezetfüggetlennek, stb., ha minden komponense lineáris, környezetfüggetlen, stb.

Visszatérve az iskolai táblához, a PC rendszert a következő típusú problémamegoldásnak tekinthetjük: adott a csoportvezető (a tanár), aki a táblánál dolgozik, és a többiek (csapattagok), akik részszámításokat végeznek (pl. a saját füzetükben). A CD-rendszerek "egyenlő" tagjaival ellentétben, itt hierarchikus a felépítés, ami centralizált rendszer esetén még szembetűnőbb: csak a tanárnak van joga kérdezni, ekkor a részszámítások eredményeit behelyettesíti a saját maga által készített (központi) számításba.

10.4. példa - PC nyelvtanrendszer

Legyen P C=({S 1, S 2}, {Q 1, Q 2}, {a, b}, (S 1, {S 1S 1, S 1Q 2 Q 2}), (S 2, {S 2a S 2, S 2b S 2, S 2λ})). Könnyen belátható, hogy L(P C)={w w | w∈{a, b}*}. ★


Láthatjuk, hogy egy PC rendszernek a generáló ereje meghaladhatja a komponensek generáló erejét: az előző példában környezetfüggetlen szabályokkal generáltunk nem környezetfüggetlen nyelvet.

10.5. példa - PC nyelvtanrendszer gyakorló feladat

Készítsünk olyan környezetfüggetlen PC rendszert, amely az {a n b m a n b m |n, m ≥ 1} nem környezetfüggetlen nyelvet generálja. ★


A CD és PC rendszereket nem csak generatív nyelvtanokra, de egyéb formális számítási modellekre, mint pl. automatákra, is definiálhatjuk (az automataelméletnél ismertetett átlátszóbetűs automaták (lásd Átlátszóbetűs felismerő automata) pl., mint nagyon speciális újrainduló automaták CD-rendszere volt eredetileg definiálva, később készült el az átlátszóbetűs átfogalmazás). Itt jegyezzük meg ismét, hogy vannak olyan nyelvtan-, illetve automatarendszerek, ahol egy aktív komponens után valamilyen további adatszerkezet, pl. verem, sor segít a következő aktív komponens kiválasztásában (akár determinisztikus módon).