Keresés

Részletes keresés

Nautilus_ Creative Commons License 2011-01-21 23:56:24 62

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?

 

 

De rosszul emlékeztem: a CS nyelvek zártak az unióra, metszetre, komplementerre(!) is.

 

Helyette egy eldönthetetlen probléma CF-nyelvekről: ha van két CF-grammatika, akkor ugyanazt a nyelvet generálják-e?

 

 

Példa bonyolult rekurzív nyelvre, a prímszámok nyelve. Gondoljunk bele, hány nyitott probléma merült fel: Goldbach-sejtés, Mersenne-prímek például.

 

-----------------------

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).

 

 

Pontosítás: természetesen, a nyelv szavai rekurzív nyelv (Kleene's *): minden adott nyelvre egy szó, amely azt mondja például: "ez az L rekurzív nyelv üres/véges" (v.ö. Mersenne-prímek nyelve).

A rekurzív, CS, CF, reguláris nyelvek megadhatók mondjuk grammatikájukkal.

 

Ha azonban csak az igaz állításokat kívánjuk a nyelvbe venni, akkor az már felsorolhatatlan nyelvet eredményez.

 

Másik értelmezésben, a nyelv két komponenesre esik szét: egy L1 résznyelvre, amelyet ZFC felsorol (amit felsorol, egyúttal el is dönt, mint formulát), és egy másikra, amely nem feltétlenül igaz állításokból áll, mégis felsorolhatatlan.

 

Érdekes tény, hogy a két interpretáció különböző bonyolultságú. Az igaz állítások nyelve bonyolultabb formulával definiálható, mint a második, felsorolhatatlan résznyelvé.

 

--------------------------

 

A Context Sensitive nyelvek pontosan a nem-rövidülő nyelvek! Ez talán a legfontosabb állítások egyike az egész formális nyelvelméletben.

 

Ha egy nyelv rövidülő ugyanakkor, lehet rekurzív.

 

Mi ennek az oka? Ha van egy W véges szavunk, a {0,1} abc-ből (ez az általánosságot nem szorítja meg), akkor olyan W* szóhóz is van véges ág, amely sokkal hosszabb, mint W, de W* non-computable W-ből.

Nyilván, ez egy végtelen fa, amelyen a szavak ülnek (végtelen hosszú ággal, König-lemma).

 

Ha a nyelv komplementerében van non-computable ág-részhalmaz a szó-fában, hosszú W* szavakkal, akkor a nyelv nem lehet rekurzív, hiszen W* nyelvbe-tartozásának eldöntésére algoritmus nem lehet.

Gondoljunk arra, hogy a szavak fáját sokféleképpen lehet particionálni, ahogyan a formulákat is: úgy is, hogy kér rekurzív, úgy is, hogy egy felsorolható, és egy felsorolhatatlan, és úgy is, hogy két felsorolhatatlan részhalmazt kapjunk.

 

Nota Bene: W* hosszabb, mint W.

Ha a nyelvtan egyre csak hosszabb szavakat generál, akkor nincs gond: adott >length hosszúságú szóhoz úgyis eljutunk véges időben.

 

 

Véleményem szerint az egy nagyon bonyolult kérdés, hogy a rövidülő (tehát nem CS) grammatikáknak milyen strukturális kritériumát kell adnunk, hogy rekurzív nyelvet kapjunk. A problémakör egyik legfontosabb kérdése.

 

A hozzászólá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?

 

Előzmény:
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

 

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