|
|
 |
Nautilus_
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
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_
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!
|