Keresés

Részletes keresés

Nautilus_ Creative Commons License 2007.01.07 0 0 15
Nem tudom, mi az a vwxyz-tétel. Tudnál jegyzetet vagy más forrást adni hozzá?
Előzmény: buki92 (13)
Nautilus_ Creative Commons License 2007.01.07 0 0 14
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.
Előzmény: buki92 (12)
buki92 Creative Commons License 2007.01.07 0 0 13

akbkcl környezetfüggetlen (tudok CF nyelvtant mutatni hozzá)

akblcl környezetfüggetlen (tudok CF nyelvtant mutatni hozzá)

Ezek metszete az

akbkck nyelv. (Ez pedig nem környezetfüggetlen, mert nem felel meg a vwxyz tételnek. Ez kb. ua. mint a reguláris nyelveknél a pumpálási tétel.)

 

Előzmény: Nautilus_ (11)
buki92 Creative Commons License 2007.01.07 0 0 12
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.

Előzmény: Nautilus_ (10)
Nautilus_ Creative Commons License 2007.01.07 0 0 11
Én is kérdezek egyet: le tudnád írni annak bizonyítását, hogy CF nem zárt a metszetre?
Előzmény: buki92 (-)
Nautilus_ Creative Commons License 2007.01.07 0 0 10
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.
Előzmény: Nautilus_ (5)
Nautilus_ Creative Commons License 2007.01.07 0 0 9
(A-B)^c = B nem akkor igaz, ha A az alaphalmaz, hanem akkor, ha A U B.
Előzmény: buki92 (8)
buki92 Creative Commons License 2007.01.07 0 0 8
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.)
Előzmény: Nautilus_ (5)
Nautilus_ Creative Commons License 2007.01.07 0 0 7
Tehát az 1. kérdésre szvsz a válasz: vannak NRE nyelvek, amelyek nincsenek a keresett osztályban.
Előzmény: Nautilus_ (5)
Nautilus_ Creative Commons License 2007.01.07 0 0 6
Van u. akkor az az eset, amikor az L nyelv nem áll elő A U B alakban, hanem bővebb annál. Akkor a lenti bizonyítás nem műxik!
Előzmény: Nautilus_ (5)
Nautilus_ Creative Commons License 2007.01.07 0 0 5
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.
Előzmény: Nautilus_ (4)
Nautilus_ Creative Commons License 2007.01.06 0 0 4
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.
Előzmény: Nautilus_ (3)
Nautilus_ Creative Commons License 2007.01.06 0 0 3
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.
Előzmény: Nautilus_ (1)
Nautilus_ Creative Commons License 2007.01.06 0 0 2
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.
Előzmény: Nautilus_ (1)
Nautilus_ Creative Commons License 2007.01.06 0 0 1
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.
Előzmény: buki92 (-)
horst_fuchs Creative Commons License 2007.01.06 0 0 0
0 ilyet ismerek
Előzmény: buki92 (-)
buki92 Creative Commons License 2007.01.06 0 0 topiknyitó

Szisztok!

 

Lenne egy (pontosabban kettő) kérdésem:

 

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?

[A CF nem zárt a metszetre]

 

 

RE: rekurzívan felsorolható nyelv (Chomsky 0)

CF: környezetfükketlen nyelv (Chomsky 2)

 

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