Kerro jotain mielenkiintoista!

Liittynyt
24.1.2004
Viestit
10131
Sijainti
Oslo
Evoluutio on tuottanut paljon imitaatiota. Yksi näistä jutuista on kasvi, jonka siemenet muistuttavat eläimen p****a niin paljon niin ulkomuodoltaan kuin hajultaankin, että pillerinpyörittäjät erehtyvät.*
 

Fagerholm

Oman elämänsä Sutil
Liittynyt
19.12.2004
Viestit
39266
Sijainti
Semminki
Meni vähän ohi kyseisen ongelman mielenkiintoisuus.
No saatana. Siellähän se lukee!

Mielenkiintoista kilpailijan valinnan kannalta on, että todennäköisyyksien valossa ja useimpien ongelman ratkaisua yrittävien arvion vastaisesti[1] vaihto kannattaa: vaihtamalla ovea voiton todennäköisyys nousee. Ilman vaihtoa voittomahdollisuus on 1⁄3, vaihdon jälkeen 2⁄3.
 

tmoi

No niin
Liittynyt
28.2.2004
Viestit
19017
Sijainti
turkus
Evoluutio on tuottanut paljon imitaatiota. Yksi näistä jutuista on kasvi, jonka siemenet muistuttavat eläimen p****a niin paljon niin ulkomuodoltaan kuin hajultaankin, että pillerinpyörittäjät erehtyvät.*
Voi vittu. Vuohi nähty.:eek!:

No ymmärrän toki kiinnostuksen....
 

Albert Oil

Hippi ja juntti
Liittynyt
14.2.2000
Viestit
55371
Sijainti
Korviesi välissä
Pumppauslemmalla voidaan todistaa, että kieli ei kuulu johonkin kieliluokkaan. Useimmiten käytetään säännöllisten ja yhteydettömien kielten pumppauslemmoja, mutta muitakin on olemassa. Pumppauslemma esittää ehdon, jonka jokainen luokkaan kuuluva kieli täyttää. Mikäli voidaan osoittaa, että kieli ei toteuta tätä ehtoa, niin se ei kuulu luokkaan. Eli: joten L on säännöllinen L toteuttaa säännöllisten kielten pumppauslemman, L ei toteuta säännöllisten kielten pumppauslemmaa L ei ole säännöllinen. Tässä on käytetty hyväksi logiikan modus tollens sääntöä, jonka mukaan lauseesta P Q seuraa Q P (jos Q on välttämättä tosi aina kun P on tosi ja jos tiedetään, että Q on epätosi, niin myöskään P ei voi olla tosi). Sitä vastoin siitä, että kieli toteuttaa pumppauslemman ehdot ei voida päätellä vielä mitään. Tästä esitetään myöhemmin (sivulla 10) esimerkki, jossa kieli ei ole säännöllinen, mutta kaikkia sen pitkiä sanoja voidaan kuitenkin pumpata. Näin ollen pumppauslemmoja voidaan käyttää aina vain yhteen suuntaan: osoittamaan, että kieli ei kuulu annettuun luokkaan. Jos kieli kuuluu luokkaan, niin Tiivistelmä Halutaan todistaa kieli L ei-säännölliseksi. 1. Oletetaan L säännölliseksi. Tällöin p 1 siten, että pumppauslemman ehdot toteutuvat. 2. Valitaan x L siten, että x p. 3. Osoitetaan, että kaikki x:n ositukset x = uvw rikkovat jotain lemman ehtoa.
Tekstissä tarkasteltavien kielten kuuluminen eri kieliluokkiin. se osoitetaan esittämällä kieli luokan määrittelevällä formalismilla. Esimerkiksi kieli voidaan todistaa säännölliseksi muodostamalla sen tunnistava äärellinen automaatti. Pumppauslemmat hyödyntävät kuhunkin kieliluokkaan kuuluvien kielten rakenteellista samankaltaisuutta. Esimerkiksi säännölliset kielet määritellään äärellisillä automaateilla, joilla on rajallisesti muistia, joten niillä ei voida tunnistaa kieltä, joka vaatii mielivaltaisen suuriksi kasvavien syötteiden muistamista. Tällainen kieli on vaikkapa: L = {a i j c k i, j, k N ja i + j = k}. Tarkastaessaan kuuluko sana x kieleen L automaatti joutuu muistamaan sekä a- että -merkkien lukumäärän. Äärellisten automaattien muistina toimivat automaatin tilat, joten kone joutuu siirtymään aina uuteen tilaan uuden a:n tai :n luettuaan seuraavaan tapaan: a a a a a c c c c c...... c c c c c... Tähän koneeseen tarvitaan kuitenkin ääretön määrä tiloja, sillä kielen määrittely ei aseta rajoja sille, montako a- ja -merkkiä siinä saa olla. Koska kieltä ei voida tunnistaa äärellisellä automaatilla, se ei ole säännöllinen. Yllä oleva todistelu jättää kuitenkin vielä avoimeksi mahdollisuuden, että jollain muulla periaatteella rakennettu äärellinen automaatti voisi tunnistaa sen. Todistus saadaan täsmälliseksi osoittamalla pumppauslemmalla, että mikä tahansa kielen tunnistava automaatti on väistämättä ääretön. 2 Säännöllisten kielten pumppauslemma Säännöllisten kielten pumppauslemma kuuluu seuraavasti: Määritelmä 1 Jos L on säännöllinen kieli, niin on olemassa jokin p 1 siten, että kaikille sanoille x L pätee: jos x p, niin x voidaan esittää muodossa x = uvw, missä: 1. uv p; 2. v > 0; ja 3. uv k w L kaikilla k N. Suorasanaisesti lemman ehdot voidaan selittää yhdellä lauseella: Äärettömän säännöllisen kielen tunnistavassa tilakoneessa on silmukka. Seuraavaksi käydään läpi lemman ehdot tarkemmin. Lemmassa esiintyvä parametri p vastaa pienimmän L:n tunnistavan deterministisen äärellisen automaatin tilojen määrää. Deterministinen automaatti käyttää jokaisella laskenta-askeella täsmälleen yhden merkin syötteestä. Jos kieleen kuuluvassa sanassa x on enemmän merkkejä kuin automaatissa tiloja, niin silloin automaatissa täytyy olla jossain kohtaa silmukka, josta päästään vielä hyväksyvään lopputilaan. Sana x jaetaan kolmeen osaan x = uvw. Näistä u on sanan alkuosa ennen silmukkaa, v silmukassa kierretty osa ja w loppuosa silmukan jälkeen. Tilakoneena asian voi esittää seuraavasti: v u w Ositukselle annettujen ehtojen perustelut ovat seuraavat:
1. uv p: laskennan täytyy joutua silmukkaan ennen kuin automaatista loppuvat tilat kesken; 2. v > 0: silmukka ei voi olla tyhjä vaan siihen täytyy kuulua ainakin yksi ei-tyhjä siirtymä; ja 3. uv k w L kaikilla k N: silmukka v voidaan kiertää mielivaltaisen monta kertaa ja silti voidaan päästä w:llä hyväksyvään lopputilaan. Osituksen v ei ole välttämättä ainoa x:n osajono, joka luetaan silmukassa. Esimerkiksi kielen L(a ) tunnistavassa koneessa on kaksi silmukkaa, yksi kummallekin tähtilausekkeelle. 2.1 Lemman soveltaminen Säännöllisten kielten pumppauslemmaa sovelletaan siten, että etsitään jokin kieleen kuuluva tarpeeksi pitkä sana, jota ei voida osittaa lemman ehtojen mukaisesti. Lemma sanoo, että kaikille sanoille x on olemassa jokin ositus. Todistuksessa täytyy osoittaa, että jonkin sanan kaikki ositukset johtavat ristiriitaan. Todistetaan esimerkin vuoksi, että kieli A = {a m m m 0} (1) ei ole säännöllinen. Tarkasteltava sana kannattaa valita siten, että lemman ensimmäisen ehdon täyttäviä osituksia on mahdollisimman vähän. Parhaiten tämä toteutuu siten, että otetaan sana, jonka p ensimmäistä merkkiä (missä p on pumppauslemmassa esiintyvä kielestä riippuva parametri) ovat kaikki samoja. Yleensä kannattaa valita näistä sanoista kaikkein yksinkertaisin. Kielen A tapauksessa yksinkertaisin vastaesimerkki on x = a p p A. Koska x = 2p > p, on sana tarpeeksi pitkä. Lemman ehdosta uv p seuraa, että kaikki x:n mahdolliset ositukset ovat muotoa: u = a i v = a j w = a p (i+j) p, missä i + j p. Ehdosta v > 0 seuraa, että j > 0. Tässä täytyy erikoisesti kiinnittää huomiota siihen, että (2) ei ole yksi ainoa ositus, vaan se on joukko ehtoja, jotka x:n ositusten täytyy täyttää. Varsinaiset ositukset saadaan siitä sijoittamalla muuttujien i ja j paikalle sopivat lukuarvot. Todistus on jo aika lähellä loppuaan, mutta vielä täytyy osoittaa, että mikään (2):n täyttävä ositus ei voi täyttää lemman kolmatta ehtoa ( k : uv k w L). Käytännössä tämä tapahtuu siten, että etsitään jokin k:n arvo, jolla pumpattu sana ei kuulu kieleen. Yleensä on helpointa kokeilla ensin arvoa k = 0: uv 0 w = uw = a i a p (i+j) p = a p j p Koska kaikilla osituksilla j > 0, on p j < p ja a p j p / A. Tästä nähdään, että A ei ole säännöllinen. Kertaus: löydettiin kieleen A kuuluva tarpeeksi pitkä sana, jonka kaikki ositukset rikkovat ainakin yhtä pumppauslemman ehtoa. Jos A olisi säännöllinen, niin kaikki sen pitkät sanat voitaisiin osittaa, joten A ei voi olla säännöllinen. (2) 4
2.2 Yleisiä virheitä lemman käytössä Pumppauslemmaa käytettäessä kannattaa erityisesti varoa seuraavien tyypillisten virheiden tekemistä: 1. sanan x:n ositusten puutteellinen läpikäynti; 2. pumppautuvan sanan x käyttäminen vastaesimerkkinä; 3. väärään suuntaan pumppaaminen; 4. liian lyhyen x:n käyttäminen; 5. kielen L mielivaltaisen osajoukon L tarkastelu; ja 6. väärän pumppauslemman soveltaminen. 2.2.1 Puutteellinen ositus Tarkastellaan uudelleen kieltä A = {a m m m 0}, mutta tällä kertaa tutkitaan sanaa x = a q q, missä q = p/2. 1 Koska x p, on x tarpeeksi pitkä. Nyt kohdan (2) mukaiset ositukset muuttuvat muotoon: u = a i v = a j w = a q (i+j) q, (2 ) missä i + j q, j > 0. Kuten yllä, uv / A. Tällä kertaa todistusta ei kuitenkaan saa jättää tähän, sillä x voidaan osittaa muillakin ehdot uv p ja v > 0 toteuttavilla tavoilla. Nämä muut ositukset ovat muotoa: u = a q i v = j w = q (i+j), (3) missä i + j q, ja u = a q i v = a i j w = q j, (4) missä i + j > 0 ja i, j q. Todistettaessa kieltä A epäsäännölliseksi sanalla a p/2 p/2 täytyy siis erikseen tarkistaa se, että kaikki muotoja (2 ), (3) ja (4) olevat ositukset johtavat ristiriitaan. Tämän takia tutkittava sana kannattaakin valita huolella, niin että sillä on mahdollisimman vähän ehdon uv p täyttäviä osituksia. 1 Merkintä p/2 tarkoittaa pienintä kokonaislukua y, jolle pätee p/2 y
2.2.2 Pumppautuva sana vastaesimerkkinä Pumppauslemman perusteella kieli ei ole säännöllinen, jos siihen kuuluu jokin tarpeeksi pitkä sana, jota ei voida pumpata. Tämä ei kuitenkaan tarkoita sitä, että kaikki kieleen kuuluvat pitkät sanat olisivat välttämättä pumppauskelvottomia. Tarkastellaan kieltä: B = {a m n m n}. Sana x = a p+1 p kuuluu kieleen ja x > p. Tälle löytyy kuitenkin ositus: u = a p 1 v = a w = a p, joka toteuttaa kaikki ehdot. Suoraan nähdään, että uv = a p = p ja v = a = 1 > 0. Tarkastellaan v:n pumppaamista muutamalla k:n arvolla: uv 0 w = a p p B uv 2 w = a p+2 p B uv 3 w = a p+3 p B.. Koska k:n kasvattaminen ainoastaan lisää sanan alkuun a-kirjaimia, on selvää että kaikki näin saatavat sanat kuuluvat kieleen. Kieltä B ei voida osoittaa epäsäännölliseksi sanalla x = a p+1 p. Sillä, että jotkin x:n ositukset johtavat ristiriitaan (esim. u = a, v = a p 1 ja w = a p ) ei ole väliä. Jos on olemassa ainakin yksi lemman ehdot täyttävä ositus, niin sana täyttää lemman ehdot. Kielen B voi todistaa ei-säännölliseksi vaikkapa sanalla a p p. 2.2.3 Väärään suuntaan pumppaaminen Yleensä on yksinkertaisinta kokeilla ensin 0-pumppausta, eli poistaa v kokonaan sanasta. Tämä ei kuitenkaan välttämättä riitä todistuksen tekemiseen, vaan pumppaus joudutaankin tekemään ylöspäin. Näin käy esimerkiksi kielellä: C = {a m n m n}. (5) Jälleen kerran yksinkertaisin kandidaatti on a p p, jonka kaikki ositukset ovat tuttua muotoa (2). Nyt kuitenkin uw = a p j p C, joten pelkkä 0-pumppaus ei riitä osoittamaan epäsäännöllisyyttä. Sitä vastoin kasvattamalla k:n arvoa saadaan: joten C ei ole säännöllinen. uv 2 w = a p+j p / C
 
Ylös