8.3. Permutációs nyelvek

Nézzük tehát az A → a, A  → B, AB C, A BB A alakú szabályokkal rendelkező nyelvtanokat: segítségükkel nem generálható minden környezetfüggő nyelv, de generálhatóak nem környezetfüggetlen nyelvek is, tehát az ilyen típusú szabályokkal generálható Permutációs nyelvek halmaza a Chomsky hierarchiában szigorúan a környezetfüggetlen és a környezetfüggő nyelvcsaládok közt helyezkedik el.

8.8. példa - Permutációs nyelvtan

Legyen G=({S, A, B, C}, {a, b, c}, S, {SS A B C, SA B C, A BB A, B AA B, A CC A, C AA C, B CC B, C BB C, Aa, Bb, Cc}), ekkor L(G)= {w | a w szóban az a, b és c betűk száma megegyezik (és nem 0) }. Belátható, hogy L(G) nem környezetfüggetlen. ★


Mivel a permutációs szabályok ( A BB A ) alkalmazása esetén a mondatformában nem változik meg a szereplő (terminális és nemterminális) betűk száma, a többi szabály pedig környeztfüggetlen, minden levezetésnek van olyan megfelelője, amiben a permutációs szabályokat nem alkalmazzuk, a többi szabályt pedig az eredeti levezetésben található sorrendben alkalmazzuk. Az ilyen levezetés végén kapott szó betűekvivalens az eredetileg levezetett szóval. (Betűekvivalens két szó, ha minden betűből pont ugyanannyit tartalmaznak; két nyelv pedig akkor ha bármelyik nyelv bármely szavához van vele betűekvivalens szó a másik nyelvben.) Viszont a permutációs szabályok (használata) nélküli nyelvtan környezetfüggetlen nyelvet generál: tehát a permutációs nyelvtan által generált nyelvben mindig van egy az eredeti nyelvvel betűekvivalens környezetfüggetlen résznyelv. Az a n b n c n nyelvben minden szó csak saját magával betűvekvivalens, így nem teljesül rá az előzőekben ismertetett feltétel, tahát nem permutációs nyelv.

Ide tartozó nyitott probléma: vajon az A → B alakú láncszabályok kiküszöbölhetőek-e, vagyis generálható-e minden permutációs nyelv láncszabályok nélkül?

A szóprobléma megoldására hatékony algoritmus létezésének kérdése is nyitott kérdés, vagyis jelenleg nem tudjuk, hogy melyik bonyolultsági osztályhoz tartozik ez a probléma.

A permutációs nyelvtanok generáló ereje növekszik, ha kettő hosszúságú permutációs szabályok helyett három hosszúságúakat is megengedünk (pl. A B CC B A ), vagyis az így kapott P e r m 3 nyelvosztály szigorúan a Perm=P e r m 2 és a környezetfüggő nyelvek osztálya között helyezkedik el a hierarchiában.

A permutációs nyelvek nem zártak a reguláris nyelvekkel való metszetképzésre (a példaként bemutatott ugyanannyi a, b és c betűt tartalmazó szavakból álló nyelv metszete a reguláris a * b * c * nyelvvel éppen a n b n c n , a környezetfüggetlen nyelvek pedig zártak a reguláris nyelvekkel vett metszetképzésre). Egy permutációs és egy reguláris nyelv metszeteként előálló nyelvek osztálya a Perm-reg nyelvosztály szigorúan a Perm és a környezetfüggő nyelvek osztálya között helyezkedik el a hierarchiában.