Igen ez igaz: csak a rekurzív nyelvek eldönthetők algoritmussal.
Ez tulajdonképpen egy jó hír lenne, hiszen a rekurzív nyelvek nagyon széles kategória: ugye ennek valódi részhalmaza a környezetfüggő nyelvek, annak is a valódi részhalmaza a környezetfüggetlen nyelvek és még annak a részhalmaza a reguláris nyelvek.
Valójában ahogy írtam azonban az eldöntő algoritmus csak akkor hasznos a gyakorlatban, ha elég gyors. És sajnos itt már csak a reguláris nyelvek azok a fenti osztályok közül, amelyek triviálisan nagyon gyorsan eldönthetőek (véges automatákkal), és már a környezetfüggetlen nyelvek között is vannak olyan nyelvek, amelyek ilyen szempontból borsot törnek az orrunk alá.
Emiatt a környezetfüggetlen nyelveken belül is megkülönböztetnek al nyelvosztályokat aszerint, hogy bizonyos típusú elemző algoritmusok tudják-e gyorsan eldönteni a nyelvet.
Pl. Az LL(1), LL(2), LL(n) stb... nyelveket az LL típusú elemzők elég gyorsan tudják elemezni; minél kisebb 'n' annál gyorsabban.
Vannak ennél bővebb nyelvosztályok, amik még gyorsan elmezhetők, és itt már egész új eredmények is vannak. Pl. az ANTLR LL(*) elemzőt használ, tehát az LL(*) nyelveket gyorsan tudja elemezni.
A gyakorlatban klaszzikus formális nyelvtant max környezetfüggetlent használnak, környezetfüggő nyelvtant már úgy adnak meg, hogy a környezetfüggetlen nyelvtant augmentálják kis a nyelvtanba be pluginolt szubrutinokkal, kódrészletekkel.
Továbbá érdekességként megjegyzem, hogy kényelmi okokból nyelvtanmegadásra nem is a klasszikus chomsky féle jelölést használják, hanem a gykorlatban intuitívabb jelölést, amelyet kifejezetten környezetfüggetlen nyelvekre tenyésztettek; a legimsertebb az EBNF:
http://en.wikipedia.org/wiki/Extended_Backus%E2%80%93Naur_Form
|