Keresés

Részletes keresés

Nautilus_ Creative Commons License 2011-01-17 17:40:28 57

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.

 

 

Ehhez két megjegyzés. Egyrészt, a Chomsky-hierarchiában a rekurzív nyelvek nincsenek benne. Nem találtak olyan grammatikai szerkezet-kritériumot, amely definiálná a rekurzív nyelveket.

 

A másik, hogy általában nem egy legalább rekurzív, sőt, CS nyelv szóproblémájának eldöntése a feladat a matematikában, hanem olyan szavaké, amelyek e rekurzív nyelvekről szólnak. Például véges (és ezáltal reguláris-e)? Üres-e? Ezek a problémák szintén szavak, de sajnos általában nulladrendű, nemrekurzív nyelv szavai, például a ZFC-tételeké, vagy ZFC-független (grammatikával nem is generálható) formulák nyelvéé.

 

Ha egy probléma általánosságban ezekről a nyelvekről eldönthetetlen, az azt is jelenti, hogy grammatikával nem generálható nyelv szavai (mint formulák, mondjuk).

Ha jól emlékszem, a CS nyelvekről ilyen az a kérdés, hogy ha L1, L2 CS nyelvek, akkor az uniójuk is az-e? Végtlen-e egy rekurzív nyelv?

 

A hozzászólás:
nadamhu Creative Commons License 2011-01-16 21:44:33 55

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

 

Előzmény:
Nautilus_ Creative Commons License 2011-01-16 16:21:53 54

"Elvileg egy mestreséges nyelvet, pl egy programozási nyelvet lehetne definiálni tisztán a Chomsky féle formalizmussal megadott nyelvtanával. Elvileg készíthető olyan általános program, amely fog egy mondatot meg egy nyelvtant és eldönti, hogy az adott mondat a nyelv része-e."

 

 

Általános esetben ez nem igaz, hiszen egy nyelv lehet csak felsorolható, de nem rekurzív.

De akkor is van grammatikája, amely őt generálja.

 

Pl. a Chomsky-féle reguláris nyelvek rekurzívak, azokra igaz az állításod.

 

Ha kedveled azért, ha nem azért nyomj egy lájkot a Fórumért!