Tudom, hogy már van egy 'számítástechnikai nyelvészet' topik, de ott jobbára a természetes nyelvek algoritmikus feldolgozásáról (és ennek kapcsán gyakran a mestreséges intelligenciáról) van szó. Ez a topik tisztán csak a formális nyelvészetnek lenne szentelve. (Korábban az ilyen jellegű témákat a MATEMATIKA-EGYÉB-be írtuk, de ott már túl sok minden van.)
Sziasztok! Egy kis segítség kellene a CYK algoritmushoz!
Adott a következő nyelvtan:
A->a|BA
B->b|BB
Elem-e a nyelvtan által generált nyelvnek a bba jelsorozat? Válaszod CYK algoritmussal bizonyítsd!
Ha valaki tudna ezzel kapcsolatban segíteni ("szájbarágósan" elmagyarázni), azt nagyon megköszönném. Már csak a formális nyelvek szigorlat áll köztem és a záróvizsga között és sehogysem akar menni...:( Már két vizsgalehetőséget el is lőttem, rengeteg feladattípust begyakoroltam, de még csak egy sem volt köztük, véletlenül sem...
Segítség kéne formális nyelvhez (főiskolai anyag). Át gugliztam a netet de értelmes leírást nem találtam amiből megérteném. generatív grammatikákról lenne szó.
pl:
L=a*b* (* felső index akar lenni)
S>aS
S>B
B>bB
B>lambda (üres szó)
órai példa volt 0 magyarázattal.
Igazából a logikáját szeretném megérteni ezeknek
van olyan is hogy:
L=(a b c)*
vagy
L=a+b+c+ (+ felső index akar lenni)
meg egy rakat másik
Segítene vkia magyarázatban v adna eg ylinket ami értelmesen elmondja hogy oldhatóak meg?
Csak azt sajnálom, hogy az a distinkció, amit már évek óta próbálok magyarázni neked, most sem ment át.
buki, én érteni vélem, hogy mit mondasz: Téged, programozóként, más érdekel, mint engem. Respektálom. Szóval átment a dolog.(Különben engem az is érdekel, mint Téged.)
Évek óta??? Egyetlen hozzászólásodra sem emlékszem, ami ezt feszegette vona, és nekem szólt. Régen beszélgettünk sokat, de akkor mindkettőnket érdeklő dolgokról.
Abba meg végképp nem szertnék belemenni, hogy mit értünk formális nyelvészet alatt.
?? Hát, az elég nagy pech, ugyanis a topik címe "Formális nyelvek", én nyilván releváns, azaz ontopik arról beszélgetni, hogy mit is értünk formális nyelvek alatt. És milyen általános tételek vonatkoznak rájuk (Bar-Hillel-puffasztás, Myhill-Nerode, eldönthetetlenségi eredmények, és eldönthetőségiek).
Érdekes és lehetőleg minél általánosabb feladatosztályokra keresek konkrét algoritmusokat.
Te meg érdekes és minél általánosabb állításokra hozol konkrét bizonyításokat.
Ez a topik - ne haragudj, de - nem a tiéd. A fórum szabályzata nem ismeri azt a kitételt, hogy az alapító határozza meg a hozzászólások témáját, mert a témát a cím határozza meg; miért nem választottál más címet?
A topik éveken keresztül inaktív volt.
Másképp: ne haragudj, de abszurd, hogy ebben a topikban nem lehet beszélgetni a "Formális nyelvek" elméletéről, hanem csakis algoritmusokat beírni!
Még az sem tetszett Neked, hogy a CS-nyelvek PSPACE-teljességéről tájékoztattalak, mert az túl általános, pedig mi ontopik, ha nem ez, ráadásul az összes lehetséges algoritmusok szerkezetéről szól?
Továbbá a konkrét algoritmusok cikkek témái, nem fórumos hozzászólásoké, mivel ha adsz egy algoritmust, mindig kell bizonyítanod, hogy például lineáris idejű, logaritmikus tárigényű, tehát van értelme, stb., ami nagyon nehéz szinte mindig. Nem is nagyon írtak be ide algoritmusokat (ha jól emlékszem), legfeljebb linkeket tudok elképzelni publikációkhoz.
Érdekes és lehetőleg minél általánosabb feladatosztályokra keresek konkrét algoritmusokat.
Te meg érdekes és minél általánosabb állításokra hozol konkrét bizonyításokat.
Ez két teljesen különböző hozzáállás. Még akkor ha a vizsgált területben vannak is fogalmi átfedések.
Az algoritmusokról szóló tételek sem játszanak. A komplexitáselmélet hasznos ugyan, de kb. csak annyira, mint számelméletben az alternatív logikai rendszerek.
(Megjegyzem, hogy az algoritmusok keresése kb. olyan viszonyban van a programozással, mint a matematika a számolással. Csak persze jóval fejletlenebb terület.)
Abba meg végképp nem szertnék belemenni, hogy mit értünk formális nyelvészet alatt. A tételeidet meg a bizonyításaidat nyolvancanhat másik topikba írhatod; ide algoritmusokat please.
(1.) az érdekes lenne, ha 0-ás nyelvtanokhoz találsz olyan algoritmust, amely a mondatok nagy részére, elfogadható idő alatt talál levezetést.
(Mondjuk a 'mondatok nagy része' kifejezést te nem fogod érteni, mert azt mondod, hogy végtelen mondat van, ha ebből végesről nem dönti el, akkor ..., egyébként meg végtelen/végtelen. )
(2.) az is érdekes lenne, ha tudnál mondani a 0-ás nyelvtanokhoz egy olyan normálformát, amiről egyszerű eldönteni, hogy készíthető-e hozzájuk hatékony algoritmus a tartalmazás probléma eldöntésére.
Ha jól értem, Te komplexitáselméleti problémákat kötsz össze formális nyelvelméleti problémákkal.
A megközelítésed alkalmazás-jellegű, ez nem baj, csak nem legyen kizárólagos. Túl biztos vagy magadban.
Persze, nagyon érdekes, ha igazoljuk (ZFC-ben:)), hogy P-ben van mondjuk egy kanonikusan PSPACE-beli eldöntési algoritmust használó nyelv. Ez erős eredmény. Vagy lineáris idejű algoritmussal oldható meg egy 0-adrendű grammatikával generált, de rekurzív nyelv szóproblémája.
Ugyanígy ez a témakör az approximáció, közelítő algoritmusok kérdése. Ez nem klasszikus formális nyelvelmélet.
Én nagyon szeretem a komplexitáselméletet, a P?=NP-problémát, és hasonlókat. Ezekre külön van topik.
Valójában MINDEN komplexitáselméleti probléma átfogalmazható nyelvészetivé, hiszen automaták különböző tárral, és időben döntenek el (ha eldöntenek) nyelveket.
Ez azonban már két matematikai ág, az algoritmikus komplexitáselmélet, és a formális nyelvészet összekapcsolódása.
A formális nyelvészet azonban ennél több.
Az, hogy létezik-e algoritmus az ABC problémára, nem érdekes
Ha tudod, hogy nem létezik algoritmus, keresel lineáris idejűt?:)
Az egzisztenciális bizonyítások alapvetően nem érdekesek
Jó, hogy ezt Te így tudod. Jó konstruktivista matematikus lennél: ott ugyanis egy egzisztencia-bizonyításhoz mindig van konstruktív is.:)
Igen, erre mondtam, hogy ebben a fogalmi rendszerben ilyet nem lehet.
Szerintem:
(1.) az érdekes lenne, ha 0-ás nyelvtanokhoz találsz olyan algoritmust, amely a mondatok nagy részére, elfogadható idő alatt talál levezetést.
(Mondjuk a 'mondatok nagy része' kifejezést te nem fogod érteni, mert azt mondod, hogy végtelen mondat van, ha ebből végesről nem dönti el, akkor ..., egyébként meg végtelen/végtelen. )
(2.) az is érdekes lenne, ha tudnál mondani a 0-ás nyelvtanokhoz egy olyan normálformát, amiről egyszerű eldönteni, hogy készíthető-e hozzájuk hatékony algoritmus a tartalmazás probléma eldöntésére.
Az, hogy létezik-e algoritmus az ABC problémára, nem érdekes. Az hogy minél hatékonyabb (idő,tár,pontosság) algoritmust találj minél általánosabb feladatosztályra az érdekes.
Az egzisztenciális bizonyítások alapvetően nem érdekesek, azok csak határokat jelölik ki.
Nem az a baj, hogy nincs igazad [nem tudom, lehet, igen, lehet, hogy nem], hanem az, hogy a téma szempontjából nem érdekes, amit mondasz.
Nem hiszem, hogy matematikai szempontból éredekes lenne egy olyan program, ami nagyon sok tétel bizonyítását rövid idő alatt megtalálja.
Az első mondatot értem, a másodikat nem értem, hogyan kapcsolódik ide.
Amúgy abban sincs igazad: fontos egy program, amely rövid idő alatt sok tétel bizonyítását megtalálja (gyorsabban, mint más programok).
Ami az első mondatodat illeti.
- Még egyszer: legyen L 0-adrendű nyelv, sok ilyen van, programnyelvek is lehetnek akár. Legyen L nem-rekurzív.
Legyen most "xywwwxywx" egy szó, amelyről nem tudjuk, hogy benne van-e L-ben?
Ha nem, akkor ezt nem is lehet általánosan, algoritmusasal megoldani, HISZEN L komplementere nem generálható grammatikával.
Ezt a tételt nyilván Te is ismered: vannak nem-felsorolható, grammatikával generálhatatlan nyelvek (amelyek komplementere grammatikával generálható).
((Mondok egy ilyen nyelvet, jó? Vegyük azon CF grammatika-párokat, mint szavakat, amelyek ugyanazt a nyelvet generálják. Ez a nyelv sem generálható generatív grammatikával.
Vagy: azokat a CS grammatikákat, mint szavakat, amelyek CF nyelvet generálnak. Ez a nyelv sem 0-adrendű.))
Folytatva:
úgy szeretnénk valami választ kapni, xywwwxywx L-beliségére! Ha benne van, elég L-et generálni, de aha nincs benne:
van bizonyos lehetőség, bár nem egyszerű (ezért lázadozol az igazolásom bonyolultsága miatt).
Ez az állításom. A tétel különben még nem teljes, de mint mondtam, a Metamatematika topkba írom a végét.
Ez nem fontos nyelvelméletileg??
Persze a linked is fontos problémákat említ, azokat is tisztelem. Csakhogy én most nem azokkal foglalkoztam.
A modell és a következvény semmilyen iskola szerint sem fér bele a formális nyelvészetbe. Épp ez a lényeg, hogy az egy másik játék, másik topikkal.
Kedves buki, egyáltalán nincs igazad: ez matematika.
A formális nyelvészet a matematika egyik ága. Mármost ha igazolsz egy tételt róla, az axiómarendszerben van (következmény). Legáltalánosabb esetben a ZFC halmazelméletben.
A konkrét esetet véve: vegyünk egy 0-adrendű nyelvet, amely nem rekurzív!
Akkor van-e lehetőség az adott formális nyelv komplementer nyelve szavainak meghatározására?
Én egy olyan tételt igazoltam (majdnem), hogy nagyon korlátozottan, de lehet.
Ne tévesszen meg, hogy felhasználtam a logika más területeit is. A nyelvet számokká írtam át (ez nem változtat semmit és ez szokás néha), és grammatika helyett rekurzív függvényeket használtam (ez is szokás néha).
Ne tévesszen meg, hogy más a szóhasználat, ugyanis így sokkal egyszerűbb érvelni.
De mivel Te nyitottad a topikot, bár ontopik voltam, a további hozzászólást (egy volt még) a Metamatematika topikba írom.
Következmény. Ha Gamma eldönti f értékkészletének komplementerét, akkor, mivel minden igazolás véges, Gamma egy véges részéből is eldönthetjük a rekurzív f értékkészletének véges sok elemét.
helyett inkább:
Következmény. Ha Gamma eldönti f értékkészletének komplementerét, akkor, mivel minden igazolás véges, Gamma egy véges részéből is eldönthetjük a rekurzív f értékkészlete komplementerének véges sok elemét (szavát).
--------------------------------------
Néhány javítás, de a tétel jó volt.
Az alábbiak továbbra is formális nyelvelmélet; generatív grammatika helyett azonban mindenhol a generáló rekurzív függvényt, szavak helyett számokat veszünk.
Az igazság definiálhatatlansági tételből következik, hogy a Gammában, nemrekurzívan, a P{Ax}-okkal megadott M-igazsághalmaz, függvény, (Gödel-számok halmaza) nem definiálható egyetlen formulával, ha maradunk az adott nyelvben. Ami azt illeti, ha van egy konzisztens elméletünk, amelyből a Q rendszer levezethető, az elmélet típusának egyetlen modelljének igazsághalmaza sem definiálható az adott típusban (itt: az epsilon nyelvben).
(RfC viszont igen.)
Még akkor sem, ha ez úgysem lenne effektív, hiszen egy Truth(Gödel(fi)) formula ekvivalenciája fi-vel mindig Gamma más és más axiómáiból, összességében nemrekurzív elméletből lenne levezetve.
Másrészt létezik F(x,y) rekurzív függvény, melynek első változójának helyettesítjük Gödel(fi)-t, ahol fi igaz, a második változó (az értékkészlet eleme) pedig csakis RfC egy eleme lehet.
Gamma sajnos képtelen igazolni, hogy F tényleg jó: ez ugyanis azt jelentené, hogy ha F(a,b) igazolható Gammában, akkor "a" egy igaz fi Gödel-száma, ami definiálná az M modell igazságát.
Ezért folyamodhatunk egy olyan elmélethez, amely TruthM-et definiálni már képes. Ez lehet egy kifejezőképesebb halmazelmélet, például a Morse-Kelley, amelyben tetszőleges ZFC-modell igazsága definiálható. MK egy tetszőleges modelljének elméletében már a rekurzív F(x,y) meghatározható, és reprezentálható (egyébként, F persze Gammában is reprezentálható - ha benne F rekurzív!). Ekkor "tudni" fogjuk (persze az MK-orákulum ismeretében), hogy melyik rekurzív átszámolási függvény lesz jó F-nek. Van ugyanis olyan formula az MK-modell elméletében, amely F-ről azt mondja, hogy "én TruthM Gödel-számait számolom át f értékkészletének komplementerébe".
DF persze nem felsorolható az MK-modell elméletében sem!
Ekkortól tehát F-et nyugodtan használhatjuk Gammában is, RfC elemeinek meghatározására, ha F rekurzív (ezt elérhetjük megfelelő MK-elmélettel): a Morse-Kelley garantálja, hogy az F értékkészletének elemei éppen a nem-felsorolható halmaz elemei lesznek.
----------------------------------
Feltehető a kérdés, hogy erre a hosszas igazolásra miért van szükség, például arra, hogy a Morse-Kelley-modell elmélete és Gamma f értékkészletének komplementere feletti degree-n van?
Azért, mert ha nem így lenne, akkor azok az akár paramétermentes másodrendű számelméleti formulák a HYP hiperaritmetikai hierarchiában, és az Analitikus Hierarchiában, amelyek számhalmazokat definiálnak, átírva halmazelméletre, olyan paramétereket tartalmaznának, amelyek "transzcendensek", matematikai módon megfogalmazva: nem-effektívek.
És az az F, amely a degree "felettre" számol, nemcsak hogy nem lesz rekurzív, hanem a definiáló halmazelméleti formulájának paraméterei szintén nem-effektívek, vagyis semmilyen módon nem számíthatók ki -
máshogyan fogalmazva: sem halmazelméleti, sem másmilyen (pl. aritmetikai) formulával nem írható le a Church-tézisen belül.
------------------------------
Végül megjegyzem, hogy Shoenfield egy tétele (1959.) szerint, MINDEN Ax axiómarendszernek van teljes kiterjesztése 0"-n, vagy alatta (élesebben kimondva: alatta).
Gondoljuk meg: a sztenderd számelmélet igazsághalmaza 0{omega}! Óriási tehát a bonyolultságbeli különbség.
Hogyan lehet ez?
Úgy, hogy Ax, ha lényegesen nemteljes is, független formuláinak halmaza 0", vagy alatti degree-n van, hiszen Sigma_1-halmaz komplementere. Vegyük ezt a halmazt, és adjuk minden formulájának igazságértéket, úgy, hogy a bonyolultságot nem növeljük, hiszen rekurzív átalakítás.
A következő módon. Ha már adtunk egy Fi formulának igazságértéket, vegyük hozzá Ax-hoz, és a következő Fi* formula, ha ellentmondásos Ax+Fi-vel, akkor legyen hamis (~Fi*), ha igaz, akkor ez persze bizonyíthatatlan.
Csakhogy használjuk 0' orákulumát, és azzal a konzisztencia-probléma eldöntjető. Ekkor Fi legyen igaz. Mivel legfeljebb 0' orákulumát használtuk, maradtunk legfeljebb 0"-nél. Q.E.D.
Felhívom a figyelmet, hogy elképesztően bonyolult Ax-teljes elméletek is vannak, még 0{omega_1CK} felett is!
Kissé felületes voltam, mert az írásom hibákat tartalmaz, de lehet javítani.
Elnézést, de amit írtam viszonylag bonyolult.
Másrészt igazolni szeretnék egy alapvető tételt.
--------------------------
Pontosítás: természetesen, a nyelv szavai rekurzív nyelv (Kleene's *)
Ezt úgy kell érteni, hogy adott véges abc-ből képzett nyelv szavai természetesen rekurzív nyelvet alkotnak. Ez a Kleene's star. (Ez a nyelv is szétesik persze eldönthetetlenekre, gondoljunk a Peano-ban eldönthető, és eldönthetetlen aritmetikai formulákra).
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.
Ez egy hibás állítás, át kell fogalmazni.
W* nem lehet non-computable W-ből, hiszen véges sok szó van közöttük. Csak végtelen ág lehet az.
ZFC valamely rekurzív, konzisztens, bővített axiómarendszerében biztosan el lehet dönteni, ha egy adott nyelv L, akkor egy W szó benne van-e, HA nincs benne? W* feltétel szerint benne van L-ben, W-hez pedig rekurzív ágak végtelen(!) sokasága vezet a gráfban. Ugyanakkor az L nyelvet is egy f rekurzív függvény generálja.
Mármost azt kellene igazolni, hogy nincs olyan véges ág, amely f szerinti szavakon keresztül W-t generálja W*-ből. (Ha van ilyen f, akkor f értékkészletének "dummy" generálása választ ad. Gond akkor van, ha nincs.)
f értékkészletének komplementere nem-felsorolható, nem generálja grammatika, így a feladat nagyon nehéz - másrészt csak egyetlen szóról van szó.
Azt kellene tudnunk, hogy a W*|-W ágak végtelen sokaságából egy benne van-e az L nyelvben, azaz f értékkészletében (ha egyébként nincs benne).
A válasz: igen, azaz (sajnos, nem biztos, hogy igaz) választ kaphatunk a kérdésre.
Bizonyítás. Azok a rekurzív függvények, amelyek értékkészletének komplementere nem felsorolható, reprezentálhatók ZFC-ben. Vegyük ZFC egy konzisztens, teljes bővítését: ilyen a Lindenbaum-tétel értelmében (AC-vel, tehát nemkonstruktívan, de) lehetséges.
Legyen ez a Gamma elmélet! Vizsgáljuk meg, hogy Gamma milyen függvényeket képes reprezentálni! Világos, hogy nemcsak rekurzívakat, hiszen önmaga nem az. Például tudja reprezentálni egy ZFC-modellen igaz formulák Gödel számainak halmazát (ami persze nem-felsorolható), ugyanis ha Ax egy ZFC-t tartalmazó, rekurzív része Gammának, akkor van P{Ax} bizonyíthatóság-predikátuma, amely generálja a tételeket. Vehetjük ezeknek a predikátumoknak egy egyre erősebb sorozatát, így definiálva, reprezentált nem-rekurzív függvényt.
Ha most f tetszőleges rekurzív (Gamma szerint), RfC nem-felsorolható, utóbbit Gamma tudni fogja reprezentálni, mert az a degree, amelyen az előbbi, ZFC-modellben igaz tételek Gödel-számai vannak, magasabban degree-n van, mint a Gamma szerint rekurzív függvények értékkészletének komplementerei közöl bármelyik.
Ez azért van így, mert a mondott M ZFC-modellbeli igaz állítások komplementer-nyelve szintén nem felsorolható, és ezért M igazsághalmaza bonyolultabb, mint tetszőleges olyan nyelv, amely komplementere felsorolható (ez Post tétele alapján könnyen belátható).
Vagyis az összes többi RfC pedig vagy ott, vagy alatta lévő degree-n lesz - vagyis "effektíven" kiszámítható az M modell igazsághalmazának (orákulum!) ismeretében, ahogyan ezt a degree-hierarchiából tudjuk.
Mivel Gamma teljes, adott RfC esetén "tudni" is fogjuk, hogy mi a jó rekurzív átszámolás, mert ha F ilyen (tehát M elméletét átszámolja RfC-vé), akkor az erről szóló formulát a teljes Gamma definíció szerint eldönti.
Következmény. Ha Gamma eldönti f értékkészletének komplementerét, akkor, mivel minden igazolás véges, Gamma egy véges részéből is eldönthetjük a rekurzív f értékkészletének véges sok elemét.
Felhívom a figyelmet, hogy a tétel Chaitin tételének nagymértékű élesítése.
Q.E.D.
---------------------------------------------
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
Csak egy kis javítás:
"Ha a nyelv komplementere non-computable ág-részhalmaz a szó-fában, hosszú W* szavakkal, akkor a nyelv nem lehet rekurzív"
Nyilván, nemrekurzív ág-részhalmaz lehet része rekurzívnak, ahogyan nemrekurzív nyelv rekurzívnak.
A gondolatmenetet úgy kell érteni, hogy W* előbb van (a grammatikából való levezetésben), mint W. A rövidülés éppen itt játszik szerepet: hosszú szóból kiindulva, bármikor jöhet egy rövid, 0-adrendű esetben. Más, CS esetben viszont nem: W*-ből csak hosszabb szó jöhet.
A Chomsky-hierarchia CS osztálya nyelveinek rekurzivitása éppen ezen múlik: ott ugyanis W* után NEM jöhet rövidebb szó.
Ezért aztán például a klasszikus logikát nem is tudjuk CS-nyelvvel modellezni.
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.
BME-n és ELTE-n (de szerinten minden kicsit is normális informatikus képzésben) kötelező tantárgy a formális nyelvészet, úgyhogy a meta-elmélet iránti igényed kipipálva. Az elméleti anyag gyakorlati hasznosításának oktatásában valóban van mit javítani, de ez általános betegsége az egyetemeknek.
Tipikusan az a könyv, amit egyszer át kell olvasni, hogy tudd, milyen feladat osztályokra vannak elegáns, kész megoldások, és amikor a munkád során találkozol egy konkrét feladattal, akkor csak előveszed a könyvet, és bemásolod az algoritmust.
