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.)
"Már csak az nem világos, hogy miért kell imperatív kód a gyakorlati használathoz, és micsoda egyáltalán."
Erre a kérdésedre nem válaszoltam.
Igazából ez nem biztos, hogy érdekes szerintem számodra, hiszen ez elsősorban programozóknak érdekes.
A következőről van szó:
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.
Így pl. egyszerűen el lehetne dönteni, hogy egy program szintaktikailag helyes-e.
Az általam leírt okokból (ezeket mélyen sok programozási tapasztalattal lehet érteni) a dolog komplikáltabb. A gyakorlatban olyan nyelvtanmegadásokat használunk, amelyek első ránézésre Chomsky féle nyelvtanok, de meg vannak bolondítva kis részletekkel, amelyek kicsi programtöredékek, algoritmusok, amelyekre néha ráfut az elemző. Ha téged a filozófia érdekel, akkor ez neked érdektelen technikai részlet és egyébként ha nem programozol, nem nem is ilyesmivel kell kezdeni, hanem alapvetőbb dolgokkal.
És felhívom a figyelmedet, hogy ez a Formális nyelvek topik, teljesen más témájú, mint az írásod. A formális nyelvek elmélete az informatika egyik ága, nincs köze a neopozitivistákhoz.
nekem az az érzésem, hogy magadtól rájöttél a logikai empirizmus harmincas évek elején vallott nézeteinek egy töredékére, és ezt most leírtad. A különbség legfeljebb annyi, hogy a logikai empiristák az "álproblémák" álprobléma-votát hosszasan indokolták, míg Te nem.
Javaslom az intézeti könyvtárból A bécsi kör filozófiája című szöveggyűjtemény olvasását, szerk. Altrichter Ferenc, 1972.
"Az egyértelműséggel kapcsolatos kérdésnél, az elmefilozófiára való utalás nem világos. Mi az egyértelműség az elmefilozófiában?"
Jó kérdés, intuitív definícióval kismillióval lehet találkozni, de hogy melyik érdemli meg az elmefilozófiai minősítést, az elég ködös. Én itt arra gondoltam: hogy episztemológiai értelemben nem fenyeget semmilyen kudarc (tehát a neurális hálózatunk által adott válaszok megbízhatóak a megfelelőséget illetően).
"Egy A axiómarendszer és V verifikálható állításhalmaz viszonyában egy 'b' állítás szükségtelen, ha sem 'b' sem 'not b' nem következik A-ból (b független A-tól) és minden A+b -ből levezethető verifikálható állítás levezethető simán A-ból is."
Magyarul egy b axiómát szükségtelen hozzávenni egy A axiómarendszerhez, ha az ilymódon újonnan levezethető állítások egyike sem verifikálható.
"Egy gondolatmenetben álprobléma valami akkor, ha a gondolatmenetből következő összes kijelentő mondat verifikálására nem lehetséges semmilyen mód."
Sejtem, hogy mit akarsz mondani, de ez kicsit zavaros.
Ha formálisan fogjuk fel, én inkább ilyen modellben gondolkodnék:
Van egy levezető gépünk.
Ez feltesz bizonyos axiómákat és azokból levezetet mindenféle állításokat. Egyes állításokat verifikálni lehet.
Itt megkísérelhetnénk definiálni aszükségtelen álításokat. (amiket álproblémának hívsz?).
Naív definíciós kísérlet 1:
"Szükségtelen állítás az, amiből nem lehet levezetni verifikálható állítást."
Ez sajnos nem jó. Ugyanis technikailag minden igaz állítás felhasználható akármelyik levezetésben.
Definíciós kísérlet 1:
"Szükségtelen állítás az, amely nem szükséges lépés egyetlen verifikálható állítás levezetéséhez sem."
Sajnos ez sem túl jó, mert sokmindent kerülőúton le lehet vezetni nyögvenyelősen, így szükségtelenné teszünk hasznos állításokat...
Végül ebben a modellben én a következő szűk dolgot tudom kijelenteni:
"Egy A axiómarendszer és V verifikálható állításhalmaz viszonyában egy 'b' állítás szükségtelen, ha sem 'b' sem 'not b' nem következik A-ból (b független A-tól) és minden A+b -ből levezethető verifikálható állítás levezethető simán A-ból is."
Nem tudok reagálni az eredeti felvetésedre, mert nem nagyon értek a filozófiához. Szvsz. offtopic a felvetésed. A formális nyelvek egy matematikai azonbelül is computer science téma, nálunk az egyetemen pl. volt ilyen féléves bevezető tárgyunk.
Ha engem kérdezel, olyan hú de jó definíciót nem tudnék adni az 'álprobléma' fogalmára. Mondjuk úgy definiálnám, hogy akkor mondjuk, hogy valaki álproblémával foglalkozik, ha azt várjuk (esetleg szerintünk várható el) tőle, hogy általunk fontosnak tartott problémával foglalkozzon, de mégis általunk nem fontos problémával foglalkozik.
Részben visszatértem a formális nyelvek témájához, csak kicsit más irányból mint eddig.
Érdekes, hogy a régi projektötleteim, projektkezdeményeim fokozatosan evolválnak és egymásba konvergálódnak. Régen sokat foglalkoztam a gépi fordítással és így az angol nyelv parseolásával, volt tipikus adatbáziskezelő alkalmazás-rapid prototyping ötletem, ötletelgettem adatvizualizációval kapcsolatban, stb... Ami érdekes, hogy ezek a patternek eltűnnek, majd újra előjönnek és kezdenek konvergálni. Amin most dolgozok az egy addat asszisztens, egy intuitív adatelérő cucc, amivel tetszőleges relációs adatbázist lehet böngészni. Ennek fontos része egy SNQL (Semi Natural Query LAnguage) -> SQL transzlátor. Igazából ennek az SNQL-nek az a lényelege, hogy az SQL fel van turbózva és ki van 'lazítva', tehát sokkal intuitívebben és rövidebben lehet kveriket megírni benne mint SQL-ben.
Namost ezt a nyelvet, ami alapvetően mesterséges nyelv még ha részben természetesnyelvinek tűnő alternatív lehetőségek vannak is benne parseolni kell. Mivel nem teljesen triviális nyelvről van szó, nagyon fontos volt, hogy jó parsolási technológiát válasszak.
A parser generátornak, amit használok a neve ANTLR.
Azt hiszem az ANTLR eléggé state-of-the-art-nak tekinthető parseolási témákban.
A következő rövid mondatok olyan benyomások, amelyek mostanában értek ebben a témában:
Szép dolog meg jó dolog, hogy a nyelveket deklaratívan adjuk meg, pl. a Chomsky féle notációval, de a valóságban a nyelv megadása mindig bonyolultabb és imperatív elemeket is tartalmaz. Az okok:
Egyrészt soha nem csak az érdekel minket, hogy egy mondat eleme-e egy nyelvnek. Még egy helyesírásellenőrzőnél- ahol látszólag ez a cél - sem igaz ez, mert az is érdekel, hogy ha nem eleme, akkor miért nem eleme, mi a 'hiba'.
Másrészt ezenfelül legtöbbször azért olvasunk be egy nyelvi mondatot, hogy azt valamilyen adatstruktúrává transzformáljuk. Itt megint imperatív elemek jönnek be.
Harmadrészt további probléma, hogy a nyelvek tervezésénél nem hagyhatjuk figyelmen kívül, hogy mennyi ideig fog futni a parseolás. Exponenciális ideig futó parsert írni könnyű, amely bármely CFG-t kezelni tud, de ez a gyakorlatban nem használható. Tehát a nyelvtervező megintcsak imperatívan is kell gondolkodjon emiatt.
Negyedrészt amúgysem elegendőek a CFG-k. A legtöbb gyakorlatban alkalmazott nemtriviális nyelvtan tartalmaz context sensitive elemeket. Namost mivel úgyis valamiféle deklaratív nyelvtan - imperatív kód mixture-t adunk meg, egyúttal ezt is kezeljük a gyakorlatban.
Szóval egy gyakorlati életbeli nyelvtan (pl. egy ANTLR grammar file) félig deklaratívan van megadva félig tele van tűzdelve imperatív, a parseolás során használt kóddal. Olyan luxus tehát ninc, hogy van egy deklaratív nyelvtan és abból tök automatikusan tudna a számítógép generálni és parseolni is.
Ennél is továbbmegyek: a nagyon sebességigényes nyeltanok parserei (legismertebb programozási nyelvek fordítói) teljesen kézzel vannak írva, nem használnak parser generátort.
Egy tanárom régen azt mondta, hogy deriválni a hülye is tud, de integrálni művészet. Azt hiszem lehet azt mondani, hogy egy nyelvtan mondatait generálni a hülye is tud, de effektíven parseolni művészet.
Ami még érdekes volt nekem, hogy vannak ú.n. nyelvtan design patternek. Szóval vannak tipikus szabályalkotási patternek, amiket a mesterséges nyelvek tervezői használnak (pl. operátorprecedenciák kezelésére, operátorok bal illetve jobbkötésűvé tétele, stb...)
Mindenesetre ez a formális nyelvesdi szép, mély és nehéz téma.
Nagyon köszönöm a segítséget! (Meg persze a 21-et is.)
Időközben sikerült némileg képbe kerülnöm a témát illetően a #28 beli keresőszavak segítségével. Valóban jórészt a reguláris nyelvekre vonatkozóan vannak eredmények, de azért akad környezet-függetlenten nyelvtanokra is.
b./ némely gyakorlati alkalmazásnál fel lehet tételezni, hogy két példa mondat halmazt
kapunk; az egyik halmazban levők biztosan benne vannak a keresett nyelvben, míg a
másik halmazban levők biztosan nem. Ez így oké, azzal a kiegészítéssel, hogy a nyelvtan
méretét korlátozni kell, hogy kiszűrjük a minden mondatot felsoroló "flat" nyelvtant.
Ez a gépi tanulás egyik alapproblémája (konzisztens hipotézis keresése). Főleg determinisztikus véges automaták esetében vizsgálták (az állapotok számát igyekeztek minimalizálni). Kiderült, hogy ez nehéz feladat, még approximációs algoritmust se nagyon sikerült találni.
"... CFGs do have interesting undecidable problems. One of the simplest and most cited is the problem of deciding whether a CFG accepts the language of all strings. "
...
On the other hand, the problem of determining whether a CFG accepts at least one string is decidable."
( Gyanítom, hogy az 1. -re sem lesz pozitív megoldás.)
Formális nyelvészetben (szerintem) két alapprobléma van:
1./ adott egy nyelvtan, és egy jelsorozatról el akarjuk dönteni, hogy benne van-e a nyelvtan által generált nyelvben.
2./ adott egy nyelv "néhány" mondata, és keresünk hozzá egy nyelvtant.
Az első téma világos, kiterjedt irodalma van, szépen fel van dolgozva. Viszont a másodikról semmit sem találok. Még a probléma formális megfogalmazását sem.
Példa:
Tekintsük az alábbi mondatatokat:
(a+b), a, b, ((a+b)+a), ((b+(a+a))+a), ...
Ha "józan ésszel" akarunk válaszoni arra kérdésre, hogy mi lesz a nyelvtan, valami ilyesmit kellene mondanunk:
S->T
T->a
T->b
T->(T+T)
A következő problémák merülnek fel:
1./ Véges számú mondatot adunk meg, de általában egy végtelen számú mondatot tartalmazó nyelvet keresünk. (Erre utalunk a ... jellel.)
Véges számú mondat álatal "megadott" nyelvhez mindig van egy triviális nyelvtan. A példánál maradva: S->(a+b); S->a; S->b; S->((a+b)+a); S->((b+(a+a))+a)
Ezt a problémát mondjuk kivédhetem azza, hogy korlátozom az elfogadható nyelvtan méretét.
2./ Az nyilvánvaló elvárás, hogy a nyelvtannak generálnia kell az összes mondatot, amit megadtunk. De mi legyen azokkal a mondatokkal, amiket nem adtunk meg?
a./ amit nem adtunk, az benne lehet a nyelvben. Sajnos ezen feltétel mellett van egy triviális, és egyben rossz, megoldás: megadjuk a teljes nyelv nyelvtanát. Abban tutira benne van minden példa mondat, elég tömör is, csakhát nem ezt keressük.
b./ némely gyakorlati alkalmazásnál fel lehet tételezni, hogy két példa mondat halmazt kapunk; az egyik halmazban levők biztosan benne vannak a keresett nyelvben, míg a másik halmazban levők biztosan nem. Ez így oké, azzal a kiegészítéssel, hogy a nyelvtan méretét korlátozni kell, hogy kiszűrjük a minden mondatot felsoroló "flat" nyelvtant. (ld. 1. eset)
Ez persze csak akkor működik, ha kapunk ellenpéldákat is.
Nem tudom, hogy mennyire voltam zavaros, ezért mégegyszer leírom a kérdést:
"adott egy nyelv "néhány" mondata, és keresünk hozzá egy nyelvtant."
Mi ennek a kérdésnek a precíz megfogalmazása?
Igazából nem konkrét válasz várok, hanem inkább keresőszavakat, linkeket; pl: "Markov-láncok"; "Turing-complexity"; stb..
(A "data mining" nem számít használható keresőszónak :)
Az első kérdésre (és így persze a másodikra is) a válasz: nem.
Ezt pusztán a számosságok alapján be lehet látni.
Egy véges ábécé feletti összes nyelv nyelvosztálya kontinuum számosságú.
Az RE nyelvek nyelvosztálya megszámlálhatóan végtelen számosságú. Minket azok a nyelvek érdekelnek, amelyeket az RE nyelvekből a három1 művelet véges sok alkalmazásával kapunk. Minden ilyen nyelv reprezentálható véges hosszúságú jelsorozatként egy megszámlálhatóan végtelen számosságú jelhalmaz (az RE nyelvek sorszámai, a három művelet jele, zárójelek) felett. Mivel egy megszámlálhatóan végtelen számosságú jelhalmaz feletti véges hosszúságú jelsorozatok halmaza megszámlálhatóan végtelen számosságú, a mi nyelvosztályunk is csak megszámlálhatóan végtelen számosságú lesz (nem pedig kontinuum számosságú).
(1.ugyanez érvényes minden véges művelethalmazra, függetlenül attól, milyen műveleteket tartalmaz)
A második kérdés esetében többet is lehet mondani. Mivel minden CF nyelv rekurzív, és a rekurzív nyelvek osztálya zárt a három említett műveletre (más műveletekre is, lásd itt), a mi nyelvosztályunk csak rekurzív nyelveket fog tartalmazni, vagyis a rekurzív nyelvek osztályának részhalmaza lesz (még csak minden RE nyelvet sem fog tartalmazni).
Abban nincs. Az nem sokat foglalkozik a CF nyelvekkel, inkább csak a Turing gépekre koncentrál. A Bach Iván féle szerintem alapmű. Egyrészt nagyon alapos és jól felépített, mésrészt elbűvölő humora (!) van. Valljuk be, a formális nyelvészet nem az a téma, amit könnyű lenne szórakoztató stílusban elővezetni, de neki sikerült. Ha jól tudom kapott is valami nívódíj szerűséget ezért a könyvért.
Egyébként az aibici nyelv a szokásos iskolapélda a nem CF nyelvre. Próbálj hozzá CF nyelvtant konstruáni, és magadtól is rájössz, hogy miért nem lehet.
Interneten elég nehéz megtalálni, mert hülye neve van, de maga a tétel itt szerepel. (A lap utolsó harmadában "Pumping Lemma for Context-Free Language" címszó alatt.)