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