6.3. A szóprobléma megoldása

A szóprobléma megoldása (annak eldöntése, hogy egy adott szó szerepel-e az adott lineáris nyelvben) egyben a szó egy lehetséges levezetését is magában foglalja, így szóelemző algoritmusnak is hívhatjuk. Az algoritmus alapja egy felismerési mátrix.

Algoritmus (szóelemzés lineáris nyelvtan esetén)

Input:

Legyen adott egy lineáris nyelvtan (N, T, S, H) erős normálformában és egy inputszó wT *, (jelöljük a szó betűit: a 1, a 2, …a n –nel ahol n=|w| ).

1. a mátrix megrajzolása: legyen a háromszögmátrixban a sorok és oszlopok száma n+1, vagyis az input szó hosszánál eggyel több (az oszlopok fölé (eredeti sorrendben) és a sorok elé (visszafelé, vagyis fordított sorrendben) pedig írjuk be az input betűit a következőképpen:

Mint látni fogjuk, valójában az utolsó sorra nem lesz szükség.

2. a mátrix kitöltése (sorfolytonosan):

A kitöltést az M(0,0) cellával kezdjük, az első sort az M(0,n) cellával fejezzük be ezután kezdjük a második sort, végül az utolsó előtti sorban az M(n-1,1) mezővel fejezzük be. A cellák tartalmai a nemterminálisok részhalmazai lesznek, kivéve az átlóbeli cellák, ahol + vagy – fog szerepelni.

2a. az M(0,0) cella kitöltése: írjuk be az S mondatszimbólumot ebbe a cellába.

2b. egy belső (nem átlóbeli) M(k,m) cella kitöltése, (k + m < n esetén) a cella kitöltése a cella baloldali szomszédja és a cella feletti cella alapján (ha vannak ilyenek) történik:

- ha k > 0, (azaz nem a 0. sorban vagyunk) akkor legyen AM(k, m), ha van olyan BM(k-1, m), amelyre teljesül, hogy BA a (n+1-k)H.

- ha m > 0, (vagyis nem a 0. oszlopban vagyunk) akkor legyen AM(k, m), ha van olyan BM(k, m-1), amelyre teljesül, hogy Ba m AH.

2c. Átlóbeli elemek kitöltése: M(n-i,i) cella kitöltése: az M(n-i,i-1) cellában (balszomszéd cella) szereplő nemterminálisok és az A → a alakú szabályok alapján: pontosan akkor írunk + jelet a cellába, ha az M(n-i,i-1) cellában van olyan nemterminális szimbólum B, amire van Ba i szabály a nyelvtanban. Ellenkező esetben a – jelet írjuk a cellába.

3. az eredmény leolvasása: Ha az átlóban van + elem, akkor a szó benne van a nyelvtan által generált nyelvben, különben nincs.

8. Megjegyzés. ha a főátló valamely már kitöltött eleme (+) alapján el tudjuk dönteni a választ, vagyis sikeres levezetés van a táblában, akkor a többi mező kitöltése nem szükséges.

Az algoritmus az erős normálforma alapján készített 2-fejű automata működését szimulálja, vízszintes lépésnél az első fej, függőleges lépésnél pedig a második fej lépésével, a főátlóban levő mezők jelzik a két fej lehetséges találkozási pontjait. Amennyiben a szó benne van a generált nyelvben, a kezdő S szimbólumtól a tábla valamely + szimbólumáig vezető út (ahogy a kitöltés során a szomszédos cellákat figyelembe vettük) megadja a szó egy lehetséges levezetését is. Az algoritmus a mátrix kitöltéséből, és a megoldás leolvasásából áll, időben és térben is (determinisztikusan) négyzetes bonyolultságú (a táblázat mérete miatt).

6.11. példa - A szóprobléma megoldása lineáris nyelvekre 1.feladat


Adott a G=({S,A}, {x,y}, S, H), ahol H szabályai:
{ S → yA, A → yS, S → Sx, S → y }.
Benne van-e a nyelvtan által generált nyelvben az yyyxx szó?

Megoldás:



Mivel az átlóban szerepel +-jel, ezért a szó előállítható az adott nyelvtan segítségével. ★
 

6.12. példa - A szóprobléma megoldása lineáris nyelvekre 2.feladat


Adott a G=({S,A}, {x,y}, S, H), ahol H szabályai: 
{S → xX, X → Sx, A → yY, S → yY, Y → Ay, A → z, S → z}.
Benne van-e a nyelvtan által generált nyelvben az xyzyx szó?

Megoldás:



Mivel az átlóban szerepel +-jel, ezért a szó előállítható az adott nyelvtan segítségével. ★