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.)
Ez igaz. Másrészt az első lépésben bizonyosan nem kapunk olyan C-t, amely NRE, és a komplemenetere is NRE. A komplemeneter tehát RE. A második lépésben D-C vagy C-D alakjaink lesznek, ahol C,D legfeljebb olyan NRE nyelvek, amelyek komplementere RE, vagy maguk is RE-k. Tfh C és D NRE, melyek komplementerei RE-k. Ha újra feltesszük, hogy C U D az összes szó, akkor (C-D)^c=D, ami már lehet NRE, de a komp. - C-D - újra csak RE. Nem kapunk tehát több lépésben sem olyan nyelvet, amely NRE, és a komp-a is NRE.
Indirekten tfh C benne van, ekkor A-B alakban előállítható (Gondolom, A és B RE)
Ez így nem következik egymásból. Ui. nem biztos, hogy C egy művelettel előállítható RE halmazokból. Lehet, hogy C így áll elő: (D-(A-B)) , esetleg még hosszabb kifejezés.
Az volt a kérdés, hogy a nyelvosztályban van-e minden "létező" nyelv. Ezt cáfolni lehet azzal, ha megmutatjuk, hogy egy C nemRE nyelv nincs benne. Indirekten tfh C benne van, ekkor A-B alakban előállítható. Ha még igaz az is, hogy A U B az összes szót tartalmazza, akkor A-B komplementere B, amely feltevés szerint RE. Azonban C tetszőleges nemRE, tehát komplementere lehet szintén nemRE. Ez azonban B, amiről tudjuk, hogy RE. Ellentmondás.
A gondolatmenet gyenge pontja: feltettük, hogy A U B az összes szót tartalmazza, ami szvsz nem biztos.
Szia! Ezt nem teljesen értem: A-B komplemenetere B Ez ugye akkor igaz, ha A az alaphalmaz.
Le tudnád írni még egyszer, kicsit didaktikusabban?
--- Lejebb hiányoltad a komplementer műveletet. Azért nem vettem bele, mert nem kell: a 'komplementer' azonos az 'alaphalmazból való kivonással' Esetünkben az alaphalmaz az ábécéből képezhető összes jelsorozat (=teljes nyelv), ez pedig RE. (Sőt, CF is egyben.)
Remélem, megvan. A-B komplemenetere B, azaz ha C NRE nyelv, és A-B alakban előáll, akkor a komplemenetere B "alakban" áll elő, hiszen (A-B)^c = B. B RE, márpedig C lehet olyan, hogy komplementere is NRE.
Az RE és nemRE halmazoknak egy elég komoly hierarchiája van, ezért szinte biztos vagyok benne, hogy van nem RE halmaz, amely nem áll elő A-B, A, B RE alakban. Még gondolkodnom kell ezen.
Nem jó, nem jó. Ha igaz lenne, amit írtam, akkor L RE nyelv komplemenetere is RE lenne, mert adott nyelven adott l hosszúságra csak véges sok szó van, és amikor L felsorolása ezek végére ér, minden más l hosszú L komplemeneterében lenne (véges sok ilyen van, tehát van megtalálásukra algoritmus). Ahogyan nem tudhatjuk, h pl. a Riemann-hipotézis legrövidebb bizonyítása milyen hosszú - lehet csillagászati méretű is -, úgy azt sem tudjuk, hogy mikor értünk az l hosszú szavak végére. Eszerint bonyolultság szerint nem is tudjuk a szavakat felsorolni (hiszen akkor tudnánk, hogy hol fogynak el az l hosszú szavak). A-B tehát nincs feltétlenül RE-ben, mert akkor minden RE nyelv komplementere is az volna.
Lemaradt az utolsó mondat: ez egy biz. arra, hogy nem RE nyelv nincs az osztályban. Más lenne a helyzet, ha komplementerre zártságot is feltennénk, hiszen RE, de nem R nyelv komplementere nem RE.
Ami az első kérdést illeti, ugye az a probléma, hogy nem RE nyelv van-e az osztályban. Legyenek A és B RE nyelvek, nézzük A-B-t. Elkezdjük felsorolni A-t és B-t. Nyilván, adott l hosszúságra kiderül, hogy mely szavak vannak A-ban, és melyek nincsenek, mert A és B szavait bonyolultság szerint képezzük, és csak véges sok max. l hosszúságú szó van. Tehát egy idő után végére érünk az l hosszú szavaknak, és némelyek nem lesznek B-ben. Metszetre: ugyanígy járunk el, az unió triviális.
Vegyünk egy véges ábécét, és tekintsük azt a nyelvosztályt amelynek:
- eleme minden RE nyelv
és
- zárt a nyelvek között értelmezett metszet, unió és kivonás műveletekre.
Kérdés: igaz-e, hogy ez a nyelvosztály azonos az ábécéből képezhető összes nyelvet magában foglaló nyelvosztállyal? (Ha igen, hogy kell bizonyítani, he nem, hogy kell ellenpéldát konstruálni?)
[Az RE nem zárt a kivonásra]
Második:
Vegyünk egy véges ábécét, és tekintsük azt a nyelvosztályt amelynek:
- eleme minden CF nyelv
és
- zárt a nyelvek között értelmezett metszet, unió és kivonás műveletekre.
Kérdés: igaz-e, hogy ez a nyelvosztály azonos az ábécéből képezhető összes nyelvet magában foglaló nyelvosztállyal?