8. fejezet - Környezetfüggő nyelvek

A környezetfüggetlen nyelvekkel kapcsolatosan sok elméleti eredmény ismert, és a gyakorlatban is jól alkalmazhatóak, ez köszönhető főleg annak, hogy a levezetési fa fogalma jól illeszkedik ezekhez a nyelvtanokhoz, illetve, amint láttuk a szóprobléma is hatékonyan megoldható. A világ viszont nem környezetfüggetlen, nagyon sok olyan jelenséget ismerünk, ami nem írható le környezetfüggetlen nyelvtanokkal, pl. a természetes nyelvek, az igaz ítéletlogikai formulák nyelve, a prímszámok halmaza stb.

8.1. Szóhossznemcsökkentő (monoton) nyelvtanok

Először az 1. típusú nyelvtanok és nyelvek általánosabb definícióját (lásd monoton nyelvtan) vesszük elő emlékeztetőül.

16. Definíció. Egy G generatív nyelvtant hosszúságot nem csökkentőnek (vagy röviden monotonnak) nevezünk, ha minden p → qH szabályára |p| ≤ |q| teljesül, kivétel csak az S → λ alakú szabály lehet, de ekkor az S szimbólum nem szerepelhet egyik szabály jobboldalán sem. ★

9. Megjegyzés. Az S → λ alakú szabály csak az üresszó generálására használható, és pontosan akkor szerepel egy nyelvtan szabályai közt, ha a generált nyelv L(G) tartalmazza az üresszót.

8.1. példa - Monoton nyelvtan

Legyen a G=({S, A, B, C}, {a, b, c}, S, {Sλ, Sa b c, Sa A B C, Aa A B C, Aa B C, C BB C, a Ba b, b Bb b, b Cb c, c Cc c}). Egyszerűen bizonyítható, hogy G az L(G)={a n b n c n |n ≥ 0} nyelvet generálja. ★


Egyrészt, az előző fejezetben megmutattuk a Bar-Hillel lemma segítségével, hogy L(G) nem környezetfüggetlen. Másrészt, az üresszó-lemma segítségével azt is láttuk, hogy minden környezetfüggetlen nyelv egyben környezetfüggő is; így a környezetfüggő és környezetfüggetlen nyelvek esetére a Chomsky hierarchia élességét bizonyítottuk. Már csak azt kell belátnunk, hogy a monoton nyelvtanok pontosan a környezetfüggő nyelvosztályt generálják.

Figyeljük meg, hogy egy monoton nyelvtanban pl. a b c AB a a megengedett szabály, vagyis a terminális betűket is átírhatjuk, ha a közelükben nemterminális szimbólum áll, ez kicsit ellentmond a "terminális" elnevezésnek. Azt hogy a helyzet mégsem ennyire súlyos a következő alfejezetben fogjuk belátni: minden környezetfüggő nyelvet generálhatunk olyan monoton nyelvtannal is, amiben nem történhet terminális átírás.