Keresés

Részletes keresés

nadamhu Creative Commons License 2011.01.16 0 0 53

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

Nautilus_ Creative Commons License 2011.01.14 0 0 50

 

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

 

Előzmény: Nautilus_ (49)
Nautilus_ Creative Commons License 2011.01.14 0 0 49

 

Mr. Analytic,

 

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.

 

Előzmény: Törölt nick (46)
dr.Akula úr Creative Commons License 2011.01.14 0 0 48

Kedves Mr. Analytic!

 

Köszi, hogy felhívtad rá a figyelmemet, ezentúl ideírom az ilyen témájú hsz-aimat.

Igazság szerint úgy érzem, inkább kérdésekkel, mint tételekkel fogok tudni jönni, ugyanis a ez nem egy dumáljuk meg! területe a matematikának.

dr.Akula úr Creative Commons License 2011.01.14 0 0 47

Kedves Nautilus!

 

Köszi a választ.

 

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

nadamhu Creative Commons License 2011.01.14 0 0 44

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

 

 

Előzmény: nadamhu (43)
nadamhu Creative Commons License 2011.01.14 0 0 43

Na újra elolvastam, dereng, hogy miről beszélsz.

 

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

Előzmény: Törölt nick (33)
nadamhu Creative Commons License 2011.01.14 0 0 42

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.

Előzmény: Törölt nick (40)
buki92 Creative Commons License 2011.01.14 0 0 41

Hol van itt formális nyelv?

 

 

:)

Előzmény: Törölt nick (39)
nadamhu Creative Commons License 2011.01.13 0 0 38

"és ki van 'lazítva"

Ez azt jelenti, hogy convention over configuration és 'forgiving syntax' orrba szájba.

Előzmény: nadamhu (36)
nadamhu Creative Commons License 2011.01.13 0 0 37

"hogy az SQL fel van turbózva és ki van 'lazítva',"

De persze részhalmazként tartalmazza az SQL-t, szóval mindenki annyit használ a kényelmi funkciókból amennyit akar.

Előzmény: nadamhu (36)
nadamhu Creative Commons License 2011.01.13 0 0 36

Régi egyik kedvenc témám.

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.

 

http://www.antlr.org/

 

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.

buki92 Creative Commons License 2011.01.13 0 0 35

"..., hiszen nem ezért nyitottam a témát."

 

Bocsi, ezt a témát nem te nyitottad, hanem én. És tényleg nem ezért :)

Előzmény: Törölt nick (33)
buki92 Creative Commons License 2007.06.06 0 0 32
és a futási idő lineárisan (!!!) függ a mondatok számától.



(ez egy fontos dolog volt )
Előzmény: buki92 (31)
buki92 Creative Commons License 2007.03.27 0 0 31

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.

 

Jelenleg ezt találtam a legérdekesebbnek: String Alignment in Grammatical Inference

Az itt leírt algoritmus CF nyelvtant keres, és a futási idő lineárisan (!) függ a mondatok számától.

Előzmény: U.N. Owen (30)
U.N. Owen Creative Commons License 2007.03.27 0 0 30

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.

 

Nézd meg pl. itt (24-29. és 49-50. oldal):

 

www.thi.informatik.uni-frankfurt.de/~gramlich/Publications/learningDCFS05Pres.pdf

Előzmény: buki92 (25)
U.N. Owen Creative Commons License 2007.03.27 0 0 29

1. Adott egy CF nyelvtan. Hogyan tudjuk (algoritmikusan) előállítani a komplementer nyelv egy CF nyelvtanát?

 

A CF nyelvek osztálya nem zárt a  komplemens képzésre, úgyhogy a komplementer nyelv CF nyelvtanát biztosan nem lehet mindig előállítani.

Előzmény: buki92 (26)
buki92 Creative Commons License 2007.03.25 0 0 28
Megvan a keresőszó! ( "grammar inference", "grammar induction" )
Előzmény: buki92 (25)
buki92 Creative Commons License 2007.03.23 0 0 27

Közben a 2.-ra megtaláltam a választ:

 

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

Előzmény: buki92 (26)
buki92 Creative Commons License 2007.03.23 0 0 26

Két konkrétabb kérdés:

 

1. Adott egy CF nyelvtan. Hogyan tudjuk (algoritmikusan) előállítani a komplementer nyelv egy CF nyelvtanát?

 

2. Adott egy CF nyelvtan. Hogyan tudjuk (algoritmikusan) eldönteni, hogy a generált nyelv azonos-e (a.) az üres nyelvvel, (b.) a teljes nyelvvel?

buki92 Creative Commons License 2007.03.23 0 0 25

Sziasztok!

 

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

hosszu Creative Commons License 2007.01.24 0 0 24
Sziasztok!

Egy ismerősöm kért meg az alábbi kérések megválaszolására.
Hogy stilszerű legyek: "Formális nyelvekről informálisan..." :|

Tudtok segíteni?

Kérdések
hosszu Creative Commons License 2007.01.24 0 0 23
Sziasztok!

Egy ismerősöm kért meg az alábbi kérések megválaszolására.
Hogy stilszerű legyek: "Formális nyelvekről informálisan..." :|

Tudtok segíteni?
Dubois Creative Commons License 2007.01.07 0 0 22
Előzmény: buki92 (16)
U.N. Owen Creative Commons License 2007.01.07 0 0 21

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

Előzmény: buki92 (-)
Nautilus_ Creative Commons License 2007.01.07 0 0 20
Köszönöm. Estére el is olvasom a CF nyelvekről szóló részt.
Előzmény: buki92 (19)
buki92 Creative Commons License 2007.01.07 0 0 19

Nézd csak, mit találtam!

http://www.typotex.hu/download/formalisnyelvek.pdf

(Ebben a 126. oldalon van a vwxyz tétel.)

 

Ez majdnem teljesen ua., mint a nyomtatott változat.

Előzmény: Nautilus_ (17)
buki92 Creative Commons License 2007.01.07 0 0 18

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.

 

[A 14-esen még gondolkozom.]

Előzmény: Nautilus_ (17)
Nautilus_ Creative Commons License 2007.01.07 0 0 17
köszi. Sajnos a Bach-könyvet megspóroltam, csak a Demetrovics-Denev-Pavlov van meg.
Előzmény: buki92 (16)
buki92 Creative Commons License 2007.01.07 0 0 16

Bach Iván: Számítástechnikai nyelvészet

3.7 fejezet: Műveletek környezetfüggetlen nyelvekkel

 

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

Előzmény: Nautilus_ (15)

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