8.8. Növekvő környezetfüggő nyelvek

E fejezetben végezetül a környezetfüggő nyelvek egy speciális osztályát mutatjuk be.

Növekvő környezetfüggő (GCS: Growing Context-Sensitive) egy G=(N, T, S, H) nyelvtan, ha S nem szerepelhet egyetlen szabály jobb oldalán sem, és ha minden (nem S → p alakú, ahol p∈(NT)* ) szabályára teljesül, hogy ha p → qH, akkor |p|<|q|.

8.13. példa - Egy növekvő környezetfüggő nyelv

Legyen G=({S, A, B, F, H, I, L}, {a}, S, {S  → a, Sa a, Sa a a a, SF H A L, F HF B H, B H AB B B H, B H LB B I L, I LI A L, B I AI A A A, F B IF H A A, F Ha a H, a H Aa a a H, a H La a a a, I LI a a, B I aI a a a, F B aa a a a}). Ez a nyelvtan növekvő környezetfüggő és pontosan azokat a szavakat generálja az {a} egybetűs ábécé felett, amelyek hossza a 2- nek valamilyen egész kitevős hatványa. Ez a nyelv köztudottan nem tesz eleget a konstansnövekmény tulajdonságnak. ★


A növekvő környezetfüggő nyelvek osztálya szigorúan részhalmaza a környezetfüggő nyelvek osztályának, ezekre a nyelvekre a szóprobléma determinisztikus polinomiális időben eldönthető. A növekvő környezetfüggő nyelvek osztálya halmazelméleti szempontból nem összemérhető a permutációs nyelvekkel a tartalmazási (részhalmaz) relációra nézve.