pumppauslemma
Mikko <>
Pumppauslemma sanoo että jos kieli on säännöllinen, sen n:ää pidemmät
merkkijonot x voidaan jakaa osiin uvw, siten että osa v pumppautuu.
uv <= n
ja v >=1
Mutta onko niin että myös uvw <=n ?
Eli sen lisäksi että pumpattavan kohdan täytyy mahtua automaattiin, myös
loppuosan w täytyy sinne mahtua. Eli uv=n vain mikäli w=tyhjä ?
Entä onko niin, että riittää (siihen että pumppauslemma ei todista kieltä
epäsäännölliseksi) että jokaiselle merkkijonolle x >=n, löytyy "jokin" uvw
jako, jolla se pumppautuu, mutta tuon jaon ei tarvitse päteä muille kielen
L merkkijonoille?
eli jos otetaan 3 eri merkkijonoa, x, y ja z, riittääkö jos
löydetään 3 eri jakoa uvw, ja kukin x, y ja z pumppaantuu yhdellä noista?
Eli voisiko ajatella että nuo 3 jakoa ovat 3 eri äärellistä automaattia,
joista voi koota ne yhdistämällä epädeterministisen automaatin, joka
hyväksyy jos jokin noista hyväksyy?
Harri Haanpaa
>
> Pumppauslemma sanoo että jos kieli on säännöllinen, sen n:ää pidemmät
> merkkijonot x voidaan jakaa osiin uvw, siten että osa v pumppautuu.
>
> uv <= n
> ja v >=1
>
> Mutta onko niin että myös uvw <=n ?
Tässä on nyt jonkinlainen sekaannus. Tietenkin jos |x| > n ja x = uvw, niin
|uvw| > n.
> Eli sen lisäksi että pumpattavan kohdan täytyy mahtua automaattiin, myös
> loppuosan w täytyy sinne mahtua. Eli uv=n vain mikäli w=tyhjä ?
Kyllä w voi sisältää mitä tahansa. Pumppauslemma sanoo, että mitä
tahansa n:ää pidempää merkkijonoa voidaan pumpata, ja silloin
x=uvw voi olla miten pitkä tahansa.
> Entä onko niin, että riittää (siihen että pumppauslemma ei todista kieltä
> epäsäännölliseksi) että jokaiselle merkkijonolle x >=n, löytyy "jokin" uvw
> jako, jolla se pumppautuu, mutta tuon jaon ei tarvitse päteä muille kielen
> L merkkijonoille?
Jjoo.
> eli jos otetaan 3 eri merkkijonoa, x, y ja z, riittääkö jos
> löydetään 3 eri jakoa uvw, ja kukin x, y ja z pumppaantuu yhdellä noista?
Voi kai sitä noinkin ajatella.
> Eli voisiko ajatella että nuo 3 jakoa ovat 3 eri äärellistä automaattia,
> joista voi koota ne yhdistämällä epädeterministisen automaatin, joka
> hyväksyy jos jokin noista hyväksyy?
Tätä en oikein ymmärrä. En ymmärrä, miten jaot olisivat äärellisiä
automaatteja.
--------------------------
Pumppauslemma äärellisille automaateille noin yleisesti menee kutakuinkin
seuraavasti:
Jokaiselle säännölliselle kielelle L on olemassa jokin sellainen n, että
kaikkia L:ään kuuluvia merkkijonoja, jotka ovat pidempiä kuin n
(yhtäsuuruuskin riittänee?), voidaan pumpata jostakin kohtaa.
"Voidaan pumpata jostakin kohtaa" tarkoittaa sitä, että kun x = u v w kuuluu
kieleen, myös u v^i w kuuluu kieleen kaikilla i, ja kuten kirjoititkin,
|uv| <= n ja |v| >= 1.
Tällä tavoin irrallaan esitettynä pumppauslemma ei vaikuta erityisen
järjelliseltä tai mielenkiintoiselta, mutta sehän onkin lemma (aputulos),
jota voidaan käyttää todistettaessa, että jokin kieli ei ole säännöllinen.
Tällöin tyypillinen todistuksen rakenne voi olla:
Tehdään vastaoletus: oletetaan, että kieli olisi säännöllinen. Silloin
pumppauslemman nojalla on olemassa n, jota pidempiä kieleen kuuluvia
merkkijonoja voidaan pumpata. Mutta nytpä tempaisemme hatusta merkkijonon,
joka on kyllä riittävän pitkä, mutta jota ei kuitenkaan voida pumpata
pumppauslemmalla! Tämä on ristiriita, eikä kieli voi olla säännöllinen.
Toivottavasti tästä on apua,
Harri Haanpää
Mikko <>
> In article <LkXjb.630$uW6...@read3.inet.fi>, Mikko wrote:
>>
>> Pumppauslemma sanoo että jos kieli on säännöllinen, sen n:ää pidemmät
>> merkkijonot x voidaan jakaa osiin uvw, siten että osa v pumppautuu.
>>
>> uv <= n
>> ja v >=1
>>
>> Mutta onko niin että myös uvw <=n ?
>
> Tässä on nyt jonkinlainen sekaannus. Tietenkin jos |x| > n ja x = uvw,
> niin
> |uvw| > n.
>
Mielestäni x != uvw
x = u v^i w
Jos uvw ajatellaan äärellisenä automaattina, x on suurempi kuin automaatti.
esim automaatti jolla tilat 1,2 ja 3
(3:s tila hyväksyvä, tunnistaa kielen ab*a)
1 -a- 2 -b- 2 -a- 3 (eli 2:sta pääsee b:llä itseensä)
u=a
v=b
w=a
tuossa automaatissa on 3 tilaa, ja |uvw| = 3
Eli nuo tilat mahtuvat automaattiin.
otetaan x = abbba, eli |x|=5
|uv^3w|=5 ,mutta
|uvw| = 3, eli uvw <= n
Tuon siirtymän w (= 'b', siirtymä tilasta 2 tilaan 3) täytyy olla automaatin
sisällä, jotta automaatti voisi tunnistaa kyseisen merkkijonon.
>> Eli sen lisäksi että pumpattavan kohdan täytyy mahtua automaattiin, myös
>> loppuosan w täytyy sinne mahtua. Eli uv=n vain mikäli w=tyhjä ?
>
> Kyllä w voi sisältää mitä tahansa. Pumppauslemma sanoo, että mitä
> tahansa n:ää pidempää merkkijonoa voidaan pumpata, ja silloin
> x=uvw voi olla miten pitkä tahansa.
Joo mutta mikäli uvw <=n, silloin siinä erikoistapauksessa että uv=n, eli
automaatin lopputila kuuluu silmukkaan (v) ei w:lle jää enää tilaa.
Samoin koko automaatti voi olla silmukkaa, eli v=n jolloin u = e ja w = e
>
>> Entä onko niin, että riittää (siihen että pumppauslemma ei todista kieltä
>> epäsäännölliseksi) että jokaiselle merkkijonolle x >=n, löytyy "jokin"
>> uvw jako, jolla se pumppautuu, mutta tuon jaon ei tarvitse päteä muille
>> kielen L merkkijonoille?
>
> Jjoo.
>
>> eli jos otetaan 3 eri merkkijonoa, x, y ja z, riittääkö jos
>> löydetään 3 eri jakoa uvw, ja kukin x, y ja z pumppaantuu yhdellä noista?
>
> Voi kai sitä noinkin ajatella.
>
>> Eli voisiko ajatella että nuo 3 jakoa ovat 3 eri äärellistä automaattia,
>> joista voi koota ne yhdistämällä epädeterministisen automaatin, joka
>> hyväksyy jos jokin noista hyväksyy?
>
> Tätä en oikein ymmärrä. En ymmärrä, miten jaot olisivat äärellisiä
> automaatteja.
Koska säännöllisen kielen voi tunnistaa äärellisellä automaatilla.
Eikö pumppauslemma juuri yritä todistaa ettei ole olemassa äärellistä
automaattia, jolla merkkijono x > n pumppautuisi.
Eli tässä tapauksessa osoitamme että löytyy jako uvw
(= äärellinen automaatti), joka tunnistaa merkkijonon x.
Mutta siis sanooko lemma vain että merkkijonolle x > n löytyy automaatti
uvw, joka
1) tunnistaa x:n
2) ja yhdelläkään i:n arvolla uv^iw ei ole kieleen kuulumaton.
Mutta tällä valitulla jaolla uv^iw :n ei tarvitse tuottaa koko kieltä kun
i:tä pumpataan?
>
> --------------------------
>
> Pumppauslemma äärellisille automaateille noin yleisesti menee kutakuinkin
> seuraavasti:
>
> Jokaiselle säännölliselle kielelle L on olemassa jokin sellainen n, että
> kaikkia L:ään kuuluvia merkkijonoja, jotka ovat pidempiä kuin n
> (yhtäsuuruuskin riittänee?), voidaan pumpata jostakin kohtaa.
>
> "Voidaan pumpata jostakin kohtaa" tarkoittaa sitä, että kun x = u v w
> kuuluu kieleen, myös u v^i w kuuluu kieleen kaikilla i, ja kuten
> kirjoititkin,
> |uv| <= n ja |v| >= 1.
>
> Tällä tavoin irrallaan esitettynä pumppauslemma ei vaikuta erityisen
> järjelliseltä tai mielenkiintoiselta, mutta sehän onkin lemma (aputulos),
> jota voidaan käyttää todistettaessa, että jokin kieli ei ole säännöllinen.
Mielestäni lemma on hyvin (liiankin?) yksinkertainen.
Mielestäni se sanoo vain että jotta äärellinen automaatti voisi tunnistaa
kielen, täytyy osien
u = tilat ennen silmukkaa
v = silmukka
w = simukan jälkeiset tilat
olla automaatin sisällä,
Siksi mietinkin olenko ymmärtänyt jotain väärin?
Ajattelin että |uvw| <= n pätee, mutta ehkä lemman soveltamiseen riittää sen
lievempi muoto |uv| < n (joka luonnollisesti uv <= n jos uvw<=n), mutta
onko näin?
Mikko <>
>
> Mielestäni se sanoo vain että jotta äärellinen automaatti voisi tunnistaa
> kielen, täytyy osien
>
> u = tilat ennen silmukkaa
> v = silmukka
> w = simukan jälkeiset tilat
>
> olla automaatin sisällä,
itseasiassa u,v ja w taitavat olla äärellisen automaatin siirtymiä, eikä
tiloja.
Mikko <>
Ajattelin niin että jos meillä on kieli L (säännöllinen)
L = { x kuuluu (a,b)* | (x mod 5 = 0) or (x mod 2 = 0) or (x = aaa) }
yritämme todistaa kielen epäsäännölliseksi käyttäen pumppauslemmaa.
Teemme vastaoletuksen: L on säännöllinen.
Nyt jokaiselle x c L, |x| >=n löytyy jako uvw, eli äärellinen automaatti
u = siirtymät alusta silmukan alkuun
v = silmukan siirtymät
w = siirtymät silmukan lopusta loppuun
Jos voimme osoittaa että on joku x, |x| >=n, jolle ei löydy jakoa uvw, eli
äärellistä automaattia joka tunnistaa sen, olemme todistaneet että kieli L
ei ole säännöllinen.
Nyt jos otamme x = aaaaa
jos otamme jaon
u = e
v = (a,b)^5 (5 tilaa, 5. siirtymä palaa ensimmäiseen)
w = e
1) uv^5w = aaaaa
2) ja uv^iw kaikilla i:n arvoilla kuuluu kieleen
Eli valittu uvw on äärellinen automaatti, joka tunnistaa annetun merkkijonon
+ osajoukon kielestä L (tähän automaattiin myös pätee mainitsemani uvw <=n,
eli uvw = n = 5)
merkkijonolle x = bbbb löyttyy myös automaatti uvw(2) joka tunnistaa sen +
osajoukon kielestä L.
Kumpikaan uvw(1) tai uvw(2) eivät kuitenkaan tunnista kieltä L, vaan
ainoastaan osan siitä.
Yhdistämällä automaattien uvw(1) ja uvw(2) alkutilat epsilonsiirtymillä
uuteen alkutilaan, ja lopputilat epsilonsiirtymillä uuteen lopputilaan,
saamme epädeterministisen äärellisen automaatin joka tunnistaa ne molemmat.
Eli jos on k kappaletta merkkijonoja x, |x| >=n, x c L, voi olla k
kappaletta erilaista jakoa uvw, jotka kukin tunnistavan vain tuon yhden
merkkijonon (+ mahdollisesti osajoukon kielestä L)
Kunhan k on rajallinen määrä, voi näistä automaateista yhdistää suuremman
automaatin joka tunnistaa nuo kaikki.
Ja samalla noiden pienempien uvw - automaattien rajat n saa ylittää (ja
kahden eri uvw-automaatin n on keskenään eri luku), ja yhdistetyn
automaatin tilojen määrä saa olla kaikkien uvw-automaattien n:t
yhteenlaskettuna (koska luku n ei ollut tiedossa, eli ei ole sidottu).
Eli ilmeisesti siihen mitä mietin, pätee
- uvw <= n
ja
- annetulle merkkijonolle x, |x| >=n esitetyn automaatin/jaon uvw täytyy
tunnistaa vain tuo merkkijono x, ei kieltä L ( v:n pumppaus i:llä vaatii
vain että automaatti ei tunnista kieleen kuulumatonta merkkijonoa, v:n
pumppauksen i:llä ei tarvitse tuottaa kieltä L)
- ja käytännössä tuo pumppauslemmalle esitetty jako uvw, usein on automaatti
joka tunnistaa osan kielestä L. Varsinainen äärellinen automaatti joka
tunnistaa kielen L, saadaan yhdistämällä nuo pienemmät automaatit.
Eli pumppauslemma ei etsi automaattia joka tunnistaa kielen L, se etsii vain
pienempää automaattia joka tunnista annetun merkkijonon x, x c L
Tuo ehkä oli se eniten hämäävin, eli riittää että löydetään jokin äärellinen
automaatti joka tunnistaa merkkijonon x, mutta tuon automaatin ei tarvitse
tunnistaa kieltä L.
Mutta samalla tuo selittääkin miksi kieli todistetaan säännölliseksi
esittämällä äärellinen automaatti.
Eli silloin pitää kattaa kaikki mahdollist kieleen kuuluvat merkkijonot x.
(sama hoituisi esittämällä jokaiselle mahdolliselle x, x c L jokin
automaatti joka tunnistaa sen, mutta silloin on nimenomaan esitetty
äärellinen automaatti joka tunnistaa kielen L - koska se saadaan
yhdistämällä nuo pienemmät automaatit)
Valmari Antti
Mikko kirjoitti:
> Siksi mietinkin olenko ymmärtänyt jotain väärin?
Siltä kyllä kovasti vaikuttaa.
Pumppauslemman idea on erittäin yksinkertainen. Olkoon L säännöllinen
kieli. (Kieli on kokoelma äärellisiä merkkijonoja. Merkkijono on nolla
tai useampia merkkejä pantuna peräkkäin. Merkit on poimittu jostakin
ennalta sovitusta joukosta, jota kutsutaan aakkostoksi.)
"Säännöllinen" kieli voidaan määritellä ainakin kolmella eri tavalla,
mutta jatkon kannalta olennainen asia on se, että jokaiselle säännölliselle
kielelle on olemassa (mahdollisesti epädeterministinen) äärellinen
automaatti, joka hyväksyy kyseisen kielen. Äärellinen automaatti on
verkkomainen rakenne, jossa on äärellinen joukko solmuja (piirretään
ympyröinä), joista yksi on nimeltään alkusolmu ja jokin osa (ei yhtään,
kaikki tai mitä tahansa siltä väliltä) on nimetty loppusolmuiksi. Solmujen
välille on piirretty nuolia. Jokaisen nuolen varrelle on kirjoitettu
joko jokin aakkoston alkio tai erikoismerkki epsilon, joka tarkoittaa
"ei aakkoston alkiota". Äärellisen automaatin määritelmässä kerrotaan
myös käytettävä aakkosto.
Äärellinen automaatti hyväksyy merkkijonon sigma, jos on olemassa polku
(= nuolia pitkin kulkeva, vähintään 0 askelta pitkä reitti solmusta toiseen,
sieltä kolmanteen jne.), joka alkaa alkusolmusta, päättyy johonkin
loppusolmuun, ja jonka varrelta järjestyksessä poimittujen merkkien jono
kun epsiloneja ei oteta mukaan on sigma. Sama merkkijono voidaan
mahdollisesti "lukea" (= kulkea sen mukainen alkusolmusta alkava polku)
usealla eri tavalla (tätä tarkoittaa "epädeterministinen"), mutta
hyväksymiseen riittää yksikin tapa, joka vie lopputilaan.
Olkoon siis L säännöllinen kieli. Sen hyväksyvässä automaatissa on jokin
äärellinen määrä tiloja, vaikka n. Oletetaan, että luetaan merkkijono,
jossa on ainakin n merkkiä siten, että päädytään johonkin lopputilaan.
Viimeistään ännännen merkin lukemisen jälkeen on pakko tulla takaisin johonkin
solmuun q jossa on käyty jo, ja vieläpä siten, että käyntien välillä on ollut
ainakin yksi muulla kuin epsilonilla nimetty kaari --- muutoinhan solmut loppuvat
kesken. Merkatkaamme
u = alkusolmusta solmuun q vievän polun varrelta luetut merkit ilman epsiloneja
v = solmun q ensimmäisen ja toisen käynnin välillä luetut ...
w = solmusta q loppusolmuun jatkettaessa luetut ...
Koko luettu merkkijono on siis uvw. Nyt q:sta q:hun vievä silmukka voidaan
yhden kerran sijaan lukea nolla, kaksi, kolme, ... kertaa, joten nähdään,
että automaatti hyväksyy myös merkkijonot uw, uvvw, uvvvw, uvvvvw, ...
|v| >= 1, koska q:ssa käyntien välissä luettiin ainakin yksi merkki.
|uv| <= n, koska toisto alkaa viimeistään n merkin lukemisen jälkeen.
Huomaa, että pumppauslemma ei *vaadi*, että täytyy olla |uvw| >= n ennen
kuin voi pumpata. Jos |uvw| < n, niin pumppaaminen saattaa olla mahdollista
tai mahdotonta --- pumppauslemma ei kerro asiasta mitään. Pumppauslemma
kertoo vain, että jokainen merkkijono jonka pituus on >= n sisältää
pumpattavan osan.
> Mielestäni x != uvw
Ei, vaan x = uvw. Kirjoitithan itsekin: "x voidaan jakaa osiin uvw".
> Jos uvw ajatellaan äärellisenä automaattina, x on suurempi kuin automaatti.
uvw ei ole automaatti vaan merkkijono.
Arvaan kyllä jatkotekstisi perusteella mitä ajat takaa "automaatilla uvw".
En usko ajatuksesi auttavan asian ymmärtämistä.
> Tuon siirtymän w (= 'b', siirtymä tilasta 2 tilaan 3) täytyy olla automaatin
> sisällä, jotta automaatti voisi tunnistaa kyseisen merkkijonon.
Kyllä (jos ymmärsin oikein mitä tarkoitat), mutta tästä ei seuraa juuri
mitään, koska kyseinen siirtymä saattaa käyttää solmuja ja jopa kaarta,
joita on käytetty aiemminkin.
> Joo mutta mikäli uvw <=n, silloin siinä erikoistapauksessa että uv=n, eli
> automaatin lopputila kuuluu silmukkaan (v) ei w:lle jää enää tilaa.
Kyllä jää, vertaa edellinen.
> Eikö pumppauslemma juuri yritä todistaa ettei ole olemassa äärellistä
> automaattia, jolla merkkijono x > n pumppautuisi.
Ei. Tuossa on käsitteet sekaisin. Pumppauslemman yleisin käyttötarkoitus
on sen todistaminen, että ei ole äärellistä automaattia, joka hyväksyy
annetun kielen. Todistus kulkee siten, että otetaan äärellinen automaatti
joka hyväksyy *ainakin* kaikki kieleen kuuluvat merkkijonot, ja osoitetaan
pumppaamalla että se hyväksyy *myös kielen ulkopuolisen* merkkijonon. Se
ei siis hyväksy haluttua kieltä koska se hyväksyy "liikaa".
> Eli tässä tapauksessa osoitamme että löytyy jako uvw
> (= äärellinen automaatti)
Jako uvw ei ole äärellinen automaatti.
> Mutta siis sanooko lemma vain että merkkijonolle x > n löytyy automaatti
Ei. Automaatti on ensin ja vasta sitten merkkijono x. Automaatin saamiseksi
ei aloiteta yhdestä merkkijonosta x, vaan kokonaisesta kielestä.
> Mielestäni lemma on hyvin (liiankin?) yksinkertainen.
Se on hyvin yksinkertainen.
> Mielestäni se sanoo vain että jotta äärellinen automaatti voisi tunnistaa
> kielen, täytyy osien
>
> u = tilat ennen silmukkaa
> v = silmukka
> w = simukan jälkeiset tilat
>
> olla automaatin sisällä,
>
> Siksi mietinkin olenko ymmärtänyt jotain väärin?
Minusta näyttää, että sekoitat kielet ja merkkijonot toisiinsa.
> |uv| < n
|uv| < n ei riitä.
> itseasiassa u,v ja w taitavat olla äärellisen automaatin siirtymiä, eikä
> tiloja.
Eivät ne ole siirtymiäkään, vaan merkkijonoja. Automaatissa niitä vastaa
kokonainen polku.
> Eli jos on k kappaletta merkkijonoja
> Kunhan k on rajallinen määrä, voi näistä automaateista yhdistää suuremman
> automaatin joka tunnistaa nuo kaikki.
Jos kielessä on vain äärellinen määrä merkkijonoja, niin kieli on
säännöllinen.
> Eli pumppauslemma ei etsi automaattia joka tunnistaa kielen L, se etsii vain
> pienempää automaattia joka tunnista annetun merkkijonon x, x c L
Ei se etsi automaattia. Jos se jotakin "etsii", niin merkkijonoja.
> Tuo ehkä oli se eniten hämäävin, eli riittää että löydetään jokin äärellinen
> automaatti joka tunnistaa merkkijonon x, mutta tuon automaatin ei tarvitse
> tunnistaa kieltä L.
Olet aivan hakoteillä.
> Mutta samalla tuo selittääkin miksi kieli todistetaan säännölliseksi
> esittämällä äärellinen automaatti.
Kielen voi todistaa säännölliseksi esittämällä äärellinen automaatti joka
hyväksyy sen, mutta tällä asialla ei ole mitään tekemistä pumppauslemman kanssa.
> Eli silloin pitää kattaa kaikki mahdollist kieleen kuuluvat merkkijonot x.
Ja samalla pitää välttää kattamasta mitään ylimääräistä.
--- Antti Valmari ---
Mikko <>
>
> Mikko kirjoitti:
>> Siksi mietinkin olenko ymmärtänyt jotain väärin?
>
> Siltä kyllä kovasti vaikuttaa.
>
Mutta miksi siinä tapauksessa esimerkkini toimivat?
> Olkoon siis L säännöllinen kieli. Sen hyväksyvässä automaatissa on jokin
> äärellinen määrä tiloja, vaikka n. Oletetaan, että luetaan merkkijono,
> jossa on ainakin n merkkiä siten, että päädytään johonkin lopputilaan.
> Viimeistään ännännen merkin lukemisen jälkeen on pakko tulla takaisin
> johonkin solmuun q jossa on käyty jo, ja vieläpä siten, että käyntien
> välillä on ollut ainakin yksi muulla kuin epsilonilla nimetty kaari ---
> muutoinhan solmut loppuvat kesken. Merkatkaamme
>
> u = alkusolmusta solmuun q vievän polun varrelta luetut merkit ilman
> epsiloneja
> v = solmun q ensimmäisen ja toisen käynnin välillä luetut ...
> w = solmusta q loppusolmuun jatkettaessa luetut ...
>
> Koko luettu merkkijono on siis uvw. Nyt q:sta q:hun vievä silmukka voidaan
> yhden kerran sijaan lukea nolla, kaksi, kolme, ... kertaa, joten nähdään,
> että automaatti hyväksyy myös merkkijonot uw, uvvw, uvvvw, uvvvvw, ...
> |v| >= 1, koska q:ssa käyntien välissä luettiin ainakin yksi merkki.
> |uv| <= n, koska toisto alkaa viimeistään n merkin lukemisen jälkeen.
>
> Huomaa, että pumppauslemma ei *vaadi*, että täytyy olla |uvw| >= n ennen
> kuin voi pumpata.
jos n oli automaatin tilojen määrä, ei automaatti voi tunnistaa > uvw, eli
jaolla uvw > n emme saa säännöllistä kieltä.
> Jos |uvw| < n, niin pumppaaminen saattaa olla
> mahdollista tai mahdotonta --- pumppauslemma ei kerro asiasta mitään.
> Pumppauslemma kertoo vain, että jokainen merkkijono jonka pituus on >= n
> sisältää pumpattavan osan.
Jos kieli on säännöllinen, on pumppaaminen mahdollista uvw <=n
vai voiko joku esittää yhdenkin vastaesimerkin?
merkkijonon x > n, kuuluen säännölliseen kieleen, jolle ei pätisi uvw <= n
>
>
>> Mielestäni x != uvw
>
> Ei, vaan x = uvw. Kirjoitithan itsekin: "x voidaan jakaa osiin uvw".
...siten että kun osaa v pumpataan i kertaa, saadaan aikaan x
>
>> Jos uvw ajatellaan äärellisenä automaattina, x on suurempi kuin
>> automaatti.
>
> uvw ei ole automaatti vaan merkkijono.
Ei, u + (v*i) + w on merkkijono
uvw ei ole käsitelty merkkijono
>
> Arvaan kyllä jatkotekstisi perusteella mitä ajat takaa "automaatilla uvw".
> En usko ajatuksesi auttavan asian ymmärtämistä.
>
>
>> Tuon siirtymän w (= 'b', siirtymä tilasta 2 tilaan 3) täytyy olla
>> automaatin sisällä, jotta automaatti voisi tunnistaa kyseisen
>> merkkijonon.
>
> Kyllä (jos ymmärsin oikein mitä tarkoitat), mutta tästä ei seuraa juuri
> mitään, koska kyseinen siirtymä saattaa käyttää solmuja ja jopa kaarta,
> joita on käytetty aiemminkin.
Silloin kyseessä ei taida olla w, vaan v tai v(2), eli automaatti joka
sisältää useampia silmukoita (en ole useamman silmukan automaatteja paljon
pohtinut, mutta oletan ettei se tuo asiaan varsinaista uutta)
Jos kuljemme solmua tai kaarta jota on käytetty aiemmin, teemme silmukan,
eli kierrämme osaa v
w on osa silmukan lopusta merkkijonon loppuun.
>
>
>> Joo mutta mikäli uvw <=n, silloin siinä erikoistapauksessa että uv=n, eli
>> automaatin lopputila kuuluu silmukkaan (v) ei w:lle jää enää tilaa.
>
> Kyllä jää, vertaa edellinen.
Jos osa w käyttää jotain kaarta/tilaa uudelleen, se voi tehdä sen äärettömän
monta kertaa, eli kyseessä on sulkeuma - v
>
>> Eikö pumppauslemma juuri yritä todistaa ettei ole olemassa äärellistä
>> automaattia, jolla merkkijono x > n pumppautuisi.
>
> Ei. Tuossa on käsitteet sekaisin. Pumppauslemman yleisin käyttötarkoitus
> on sen todistaminen, että ei ole äärellistä automaattia, joka hyväksyy
> annetun kielen. Todistus kulkee siten, että otetaan äärellinen automaatti
> joka hyväksyy *ainakin* kaikki kieleen kuuluvat merkkijonot, ja osoitetaan
> pumppaamalla että se hyväksyy *myös kielen ulkopuolisen* merkkijonon. Se
> ei siis hyväksy haluttua kieltä koska se hyväksyy "liikaa".
mehän voisimme ottaa sulkeuman aakkostosta, ja saamme äärellisen automaatin
joka hyväksyy kaiken mahdollisen aakkostoon sisältyvän.
tuolla logiikalla voisimme todistaa minkä tahansa kielen epäsäännölliseksi.
>
>
>> Eli tässä tapauksessa osoitamme että löytyy jako uvw
>> (= äärellinen automaatti)
>
> Jako uvw ei ole äärellinen automaatti.
mikäli uv*iw on säännölliseen kieleen kuuluva merkkijono, on olemassa
äärellinen automaatti joka tunnistaa sen, ja tuollaisen automaatin yksi
mahdollinen jako on uvw
>
>> Mutta siis sanooko lemma vain että merkkijonolle x > n löytyy automaatti
>
> Ei. Automaatti on ensin ja vasta sitten merkkijono x. Automaatin
> saamiseksi ei aloiteta yhdestä merkkijonosta x, vaan kokonaisesta
> kielestä.
Jos yritämme todistaa että kieli on epäsäännöllinen, ei ole olemassakaan
äärellistä automaattia joka kielen tunnistaisi.
Kielen epäsäännölliseksi osoittamiseen riittää että löydämme yhden kieleen
kuuluvan merkkijonon x, jolle ei ole olemassa äärellistä automaattia joka
sen tunnistaisi.
>
>
>> Mielestäni lemma on hyvin (liiankin?) yksinkertainen.
>
> Se on hyvin yksinkertainen.
>
Miksi kaikki sitten tulkitsevat sitä niin vaikeasti?
>
>> Mielestäni se sanoo vain että jotta äärellinen automaatti voisi tunnistaa
>> kielen, täytyy osien
>>
>> u = tilat ennen silmukkaa
>> v = silmukka
>> w = simukan jälkeiset tilat
>>
>> olla automaatin sisällä,
>>
>> Siksi mietinkin olenko ymmärtänyt jotain väärin?
>
> Minusta näyttää, että sekoitat kielet ja merkkijonot toisiinsa.
pumppauslemma yrittää todistaa vain yhden merkkijonon joka kuuluu kieleen
epäsäännölliseksi.
jos kieleen kuuluu yksikin merkkijono jota ei voi tunnistaa äärellisellä
automaatilla, on koko kieli epäsäännöllinen.
toiseen suuntaan, jos todistetaan kieltä säännölliseksi, ei riitä yksi
merkkijono, vaan täytyy todistaa että kaikki kieleen kuuluvat merkkijonot
voi tunnistaa äärellisellä automaatilla.
>
>
>> |uv| < n
>
> |uv| < n ei riitä.
>
>
>> itseasiassa u,v ja w taitavat olla äärellisen automaatin siirtymiä, eikä
>> tiloja.
>
> Eivät ne ole siirtymiäkään, vaan merkkijonoja. Automaatissa niitä vastaa
> kokonainen polku.
onko polku useamman tilan kautta kulkevat siirtymät yhdessä?
siinä tapauksessa kyseessä on polku.
koska esim silmukka v voi sisältää useita tiloja ja siirtymiä (ja jopa
silmukoita) ennenkuin palaa alkutilaansa.
>
>
>> Eli jos on k kappaletta merkkijonoja
>
>> Kunhan k on rajallinen määrä, voi näistä automaateista yhdistää suuremman
>> automaatin joka tunnistaa nuo kaikki.
>
> Jos kielessä on vain äärellinen määrä merkkijonoja, niin kieli on
> säännöllinen.
mutta nuo voivat olla k kappaletta pumppautuvia merkkijonoja. Eli kukin
sisältää äärettömän määrän merkkijonoja, jotka kuuluvat kieleen.
>
>> Eli pumppauslemma ei etsi automaattia joka tunnistaa kielen L, se etsii
>> vain pienempää automaattia joka tunnista annetun merkkijonon x, x c L
>
> Ei se etsi automaattia. Jos se jotakin "etsii", niin merkkijonoja.
se etsii yhtä merkkijonoa, (joka valitaan itse) sen jälkeen osoitetaan ettei
ole äärellistä automaattia joka sen tunnistaisi.
>
>> Tuo ehkä oli se eniten hämäävin, eli riittää että löydetään jokin
>> äärellinen automaatti joka tunnistaa merkkijonon x, mutta tuon automaatin
>> ei tarvitse tunnistaa kieltä L.
>
> Olet aivan hakoteillä.
>
>
>> Mutta samalla tuo selittääkin miksi kieli todistetaan säännölliseksi
>> esittämällä äärellinen automaatti.
>
> Kielen voi todistaa säännölliseksi esittämällä äärellinen automaatti joka
> hyväksyy sen, mutta tällä asialla ei ole mitään tekemistä pumppauslemman
> kanssa.
pumppauslemma on kai jonkinlainen sekoitus äärellista automaattia (lemmassa
on n, joka on äärellisen automaatin tilojen määrä) ja säännöllistä
lauseketta - uvw ,jotka ovat merkkijonoja.
mutta koska äärellinen automaatti ja säännöllinen lauseke ovat yhtä
ilmaisuvoimaisia, voimme kummalla tahansa käsitellä *kaikki* säännölliset
lausekkeet, voimme rajata lemman käsittelyn automaatteihin ja vaihtaa nuo
säännöllisen lauksekkeen merkkijonot uvw, äärellisen automaatin polkuihin.
Pumppauslemma ei taida tarjota tekniikan puolesta mitään uutta säännöllisen
kielen käsittelyyn, vaan se käyttää äärellisten automaattien ja
säännöllisten lausekkeiden tekniikoita?
n on automaatin tilojen määrä ja
u,v,w ovat merkkijonoja, kuten säännöllisissä lausekkeissa.
Sitä miksei lemma suoraan pitäydy äärellisissä automaateissa en ymmärrä.
Mielestäni äärelliset automaatit selittävät asian paljon selkeämmin, ja
säännöllisen lausekkeen ei pitäisi tuoda mitään uutta ilmaisuvoimaa.
Ehkä jos u,v,w ovat polkuja, eikä siirtymiä, ovat ne siinä mielessä
lähempänä säännöllistä lauseketta.
Eli lemma työskentelee äärellisellä automaatilla mutta käyttää polkuja
siirtymien sijaan.
Mikko <>
> pumppauslemma on kai jonkinlainen sekoitus äärellista automaattia
> (lemmassa on n, joka on äärellisen automaatin tilojen määrä) ja
> säännöllistä lauseketta - uvw ,jotka ovat merkkijonoja.
>
> mutta koska äärellinen automaatti ja säännöllinen lauseke ovat yhtä
> ilmaisuvoimaisia, voimme kummalla tahansa käsitellä kaikki säännölliset
> lausekkeet,
Tuon piti tietenkin kuulua "...käsitellä kaikki säännölliset kielet"
Jussi Piitulainen
> Kielen epäsäännölliseksi osoittamiseen riittää että löydämme yhden
> kieleen kuuluvan merkkijonon x, jolle ei ole olemassa äärellistä
> automaattia joka sen tunnistaisi.
Leikkasin viestistä vain kohdat, joissa näyttää esiintyvän ajatus,
että voisi olla olemassa merkkijono, jota mikään äärellinen automaatti
ei tunnistaisi. Tämä on hölynpölyä. Automaattihan on helppo tehdä
heti, kun merkkijono on annettu.
Säännöllisyys ei ole merkkijonon ominaisuus, vaan merkkijonojen joukon
eli "kielen" ominaisuus. Kaikissa epäsäännöllisissä kielissä on
ääretön määrä merkkijonoja; jokainen yhden merkkijonon joukko on
säännöllinen.
[Seuraa vain lainauksia, joissa sama virhe näyttää toistuvan.]
> pumppauslemma yrittää todistaa vain yhden merkkijonon joka kuuluu
> kieleen epäsäännölliseksi.
> jos kieleen kuuluu yksikin merkkijono jota ei voi tunnistaa
> äärellisellä automaatilla, on koko kieli epäsäännöllinen.
> toiseen suuntaan, jos todistetaan kieltä säännölliseksi, ei riitä
> yksi merkkijono, vaan täytyy todistaa että kaikki kieleen kuuluvat
> merkkijonot voi tunnistaa äärellisellä automaatilla.
> se etsii yhtä merkkijonoa, (joka valitaan itse) sen jälkeen
> osoitetaan ettei ole äärellistä automaattia joka sen tunnistaisi.
--
dynamo
>>on sen todistaminen, että ei ole äärellistä automaattia, joka hyväksyy
>>annetun kielen. Todistus kulkee siten, että otetaan äärellinen automaatti
>>joka hyväksyy *ainakin* kaikki kieleen kuuluvat merkkijonot, ja
osoitetaan
>>pumppaamalla että se hyväksyy *myös kielen ulkopuolisen* merkkijonon. Se
>>ei siis hyväksy haluttua kieltä koska se hyväksyy "liikaa".
>
>
> mehän voisimme ottaa sulkeuman aakkostosta, ja saamme äärellisen
automaatin
> joka hyväksyy kaiken mahdollisen aakkostoon sisältyvän.
>
> tuolla logiikalla voisimme todistaa minkä tahansa kielen
epäsäännölliseksi.
Arvoisa Mikko <,
yllä oleva kommentti Valmarin vastaukseen osoittaa, että olet kyllä
ymmärtänyt asian aivan väärin.
Ja kyllä jokaiselle merkkijonolle varmasti löytyy äärellinen automaatti,
joka hyväksyy sen. Tiloja on yllättäen yhtä monta kuin sanassa kirjaimia.
Lue Antti Valmarin vastaus tarkkaan, niin opit ehkä mitä pumppauslemma
tarkoittaa ja miten sitä käytetään.
Ja tosiaan, pumppauslemma on helppo, paljon helpompi kuin luulet.
T. Vesa Halava
dynamo
> >>Ei. Tuossa on käsitteet sekaisin. Pumppauslemman yleisin
käyttötarkoitus
> >>on sen todistaminen, että ei ole äärellistä automaattia, joka hyväksyy
> >>annetun kielen. Todistus kulkee siten, että otetaan äärellinen
> automaatti
> >>joka hyväksyy *ainakin* kaikki kieleen kuuluvat merkkijonot, ja
> osoitetaan
> >>pumppaamalla että se hyväksyy *myös kielen ulkopuolisen*
merkkijonon. Se
> >>ei siis hyväksy haluttua kieltä koska se hyväksyy "liikaa".
> >
> >
> > mehän voisimme ottaa sulkeuman aakkostosta, ja saamme äärellisen
> automaatin
> > joka hyväksyy kaiken mahdollisen aakkostoon sisältyvän.
> >
> > tuolla logiikalla voisimme todistaa minkä tahansa kielen
> epäsäännölliseksi.
>
>
> Arvoisa Mikko <,
>
> yllä oleva kommentti Valmarin vastaukseen osoittaa, että olet kyllä
> ymmärtänyt asian aivan väärin.
>
> Ja kyllä jokaiselle merkkijonolle varmasti löytyy äärellinen automaatti,
> joka hyväksyy sen. Tiloja on yllättäen yhtä monta kuin sanassa kirjaimia.
Anteeksi, sanan pituus +1!
Mikko <>
> Mikko writes:
>
>> Kielen epäsäännölliseksi osoittamiseen riittää että löydämme yhden
>> kieleen kuuluvan merkkijonon x, jolle ei ole olemassa äärellistä
>> automaattia joka sen tunnistaisi.
>
> Leikkasin viestistä vain kohdat, joissa näyttää esiintyvän ajatus,
> että voisi olla olemassa merkkijono, jota mikään äärellinen automaatti
> ei tunnistaisi. Tämä on hölynpölyä. Automaattihan on helppo tehdä
> heti, kun merkkijono on annettu.
okei, huomasin että tuossa päädyn umpikujaan.
"Pumppauslemma:
Olkoon A säännöllinen kieli. Tällöin on olemassa sellainen n >= 1, että mikä
tahansa x c A, |x| >=n, voidaan jakaa osiin x = uvw siten, että |uv|<=n,
|v| >=1, ja uv^iw c A kaikilla i=0,1,2..."
(Laskennan teoria / Pekka Orponen)
Lemma sanoo että on olemassa luku n.
Vastaoletuksen jälkeen valitsemme merkkijonon x jonka pituus > n
esim x=a^nb^n
nythän x on nimenomaan yksi merkkijono, ei merkkijonojen joukko.
Mutta jos kieli ei olekaan säännöllinen, ei tuota lukua n ole olemassa,
joten merkkijonoa x = a^nb^n ei sitäkään ole olemassa.
Eli kieli todistetaan epäsäännölliseksi merkkijonon x perusteella,
osoittamalla että ei ole olemassa äärellistä automaattia joka tunnistaisi
merkkijonon x, mutta samalla seuraa ettei x:ää olekaan olemassa.
Virtanen Antti
> Ajattelin niin että jos meillä on kieli L (säännöllinen)
>
> L = { x kuuluu (a,b)* | (x mod 5 = 0) or (x mod 2 = 0) or (x = aaa) }
Tarkoittanet että kieleen kuuluvat kaikki merkkijonot, jotka koostuvat
merkeistä a ja b ja joiden pituus on jaollinen viidellä tai kahdella,
sekä merkkijono aaa.
> yritämme todistaa kielen epäsäännölliseksi käyttäen pumppauslemmaa.
Se ei ole kovinkaan hyödyllistä.
> Teemme vastaoletuksen: L on säännöllinen.
>
> Nyt jokaiselle x c L, |x| >=n löytyy jako uvw, eli äärellinen automaatti
>
> u = siirtymät alusta silmukan alkuun
> v = silmukan siirtymät
> w = siirtymät silmukan lopusta loppuun
>
> Jos voimme osoittaa että on joku x, |x| >=n, jolle ei löydy jakoa uvw, eli
> äärellistä automaattia joka tunnistaa sen, olemme todistaneet että kieli L
> ei ole säännöllinen.
Kyllä, mutta en tiedä onko pumppauslemmalla varsinaisesti mitään
tekemistä tämän asian kanssa. Tietenkin haetaan automaattia, joka
tunnistaa vain merkkijonon x.
> Eli jos on k kappaletta merkkijonoja x, |x| >=n, x c L, voi olla k
> kappaletta erilaista jakoa uvw, jotka kukin tunnistavan vain tuon yhden
> merkkijonon (+ mahdollisesti osajoukon kielestä L)
>
> Kunhan k on rajallinen määrä, voi näistä automaateista yhdistää suuremman
> automaatin joka tunnistaa nuo kaikki.
Kyllä. Kielet, joissa on äärellinen määrä merkkijonoja eivät olekaan
mielenkiintoisia missään mielessä.
> Ja samalla noiden pienempien uvw - automaattien rajat n saa ylittää (ja
> kahden eri uvw-automaatin n on keskenään eri luku), ja yhdistetyn
> automaatin tilojen määrä saa olla kaikkien uvw-automaattien n:t
> yhteenlaskettuna (koska luku n ei ollut tiedossa, eli ei ole sidottu).
Kyllä.
> Eli pumppauslemma ei etsi automaattia joka tunnistaa kielen L, se etsii
> vain pienempää automaattia joka tunnista annetun merkkijonon x, x c L
Kuten Valmarin Antti jo totesi, pumppauslemmaa yleensä käytetään
todistamaan jokin kieli epäsäännölliseksi.
> Mutta samalla tuo selittääkin miksi kieli todistetaan säännölliseksi
> esittämällä äärellinen automaatti.
Jokainen säännöllinen automaatti toteuttaa jonkin säännöllisen
kielen. On kokonaan eri asia päätellä minkä kielen automaatti
toteuttaa, tai millainen automaatti toteuttaa jonkin kielen L.
> Eli silloin pitää kattaa kaikki mahdollist kieleen kuuluvat merkkijonot x.
Ja vain ne. Esitetty äärellinen automaatti ei saa kattaa muita
merkkijonoja, kuin määriteltyyn kieleen kuuluvat
merkkijonot.
Pumppauslemman avulla voidaan joskus näppärästi osoittaa, että annettu
äärellinen automaatti ei vastaa haluttua kieltä, tai ettei ole
mahdollista luoda kielen tunnistavaa äärellistä
automaattia. Luonnollisesti pumppauslemmalla on käyttöä todistamisessa
vasta, jos kieli sisältää äärettömän pitkiä merkkijonoja.
Jotta äärellinen automaatti jossa on n tilaa voi hyväksyä kieleen
kuuluvan merkkijonon, jonka pituus on > n, kuljettujen kaarien täytyy
muodostaa jossain vaiheessa silmukka. Mikään ei estä kulkemasta tätä
silmukkaa mielivaltaisen monta kertaa. Lemmaa voidaan (joskus) käyttää
osoittamaan, ettei ole mahdollista luoda "pumppaussilmukkaa", jonka
avulla kaikki kieleen kuuluvat merkkijonot saadaan erotettua kieleen
kuulumattomista.
> (sama hoituisi esittämällä jokaiselle mahdolliselle x, x c L jokin
> automaatti joka tunnistaa sen, mutta silloin on nimenomaan esitetty
> äärellinen automaatti joka tunnistaa kielen L - koska se saadaan
> yhdistämällä nuo pienemmät automaatit)
Kyllä. Edelleenkin, yksikään osa-automaatti ei saa hyväksyä yhtään
kieleen kuulumatonta merkkijonoa.
Toivottavasti minusta oli jotain apua (enkä puhunut pahasti höpöjä) :)
--
// Antti "lokori" Virtanen -//- http://www.students.tut.fi/~virtanea
Jussi Piitulainen
> "Pumppauslemma:
> Olkoon A säännöllinen kieli. Tällöin on olemassa sellainen n >= 1,
> että mikä tahansa x c A, |x| >=n, voidaan jakaa osiin x = uvw siten,
> että |uv|<=n, |v| >=1, ja uv^iw c A kaikilla i=0,1,2..."
> (Laskennan teoria / Pekka Orponen)
Täytyypä harrastaa, kun on tilaisuus. En ollut tätä oppinut ennen kuin
nyt...
> Lemma sanoo että on olemassa luku n.
> Vastaoletuksen jälkeen valitsemme merkkijonon x jonka pituus > n
>
> esim x=a^nb^n
>
> nythän x on nimenomaan yksi merkkijono, ei merkkijonojen joukko.
Ilmeisesti tarkoitus on osoittaa kieli L = { a^m b^m | m in N }
epäsäännölliseksi. Todistus: jos L on säännöllinen, siihen kuuluu
muitakin alkioita - ristiriita.
Ongelma ei ole x vaan muut merkkijonot u v^k w.
> Mutta jos kieli ei olekaan säännöllinen, ei tuota lukua n ole
> olemassa, joten merkkijonoa x = a^nb^n ei sitäkään ole olemassa.
Kun johdetaan ristiriitaa oletuksesta, että kieli on säännöllinen, ei
tarvitse huolehtia mahdollisuudesta, että se ei ole säännöllinen.
Jos kieli on säännöllinen, jokainen riittävän pitkä sen alkio voidaan
jakaa osiin u v w niin, että jokainen u v^k w kuuluu kieleen. Jos voit
osoittaa, että jokin u v^k w ei kuulu kieleen, kieli ei ole
säännöllinen.
> Eli kieli todistetaan epäsäännölliseksi merkkijonon x perusteella,
> osoittamalla että ei ole olemassa äärellistä automaattia joka
> tunnistaisi merkkijonon x, mutta samalla seuraa ettei x:ää olekaan
> olemassa.
Automaatti on oletuksen mukaan olemassa, ja merkkijono on tietenkin
olemassa, mutta automaatti tunnistaa väkisin muitakin jonoja. Yritä
jakaa a^n b^n osiin u v w niin, että u v v w olisi muotoa a^m b^m.
Näet. Mahdollisia tapauksia on pieni äärellinen määrä.
(Huomaa, että L sisältyy kieleen a^* b^*, joka on säännöllinen. Huomaa
myös, että jokainen L:n äärellinen osajoukko on säännöllinen. Miksi
lemma ei toimi niiden kohdalla?)
... kiitoksia. Tämä oli opettavaista.
--
Jussi
Virtanen Antti
> "Pumppauslemma:
> Olkoon A säännöllinen kieli. Tällöin on olemassa sellainen n >= 1, että mikä
> tahansa x c A, |x| >=n, voidaan jakaa osiin x = uvw siten, että |uv|<=n,
>|v| >=1, ja uv^iw c A kaikilla i=0,1,2..."
> (Laskennan teoria / Pekka Orponen)
>
> Lemma sanoo että on olemassa luku n.
> Vastaoletuksen jälkeen valitsemme merkkijonon x jonka pituus > n
>
> esim x=a^nb^n
>
> nythän x on nimenomaan yksi merkkijono, ei merkkijonojen joukko.
Tässä on nyt kyse eri n:stä. Tuolla ylempänä n viittaa kielen
tunnistavan äärellisen automaatin tilojen määrään ja tässä itse kielen
määritelmään. Tietysti voit määritellä kielen x=a^nb^n, jossa n on
jokin kiinteä luku, mutta silloin kielesi on triviaalisti säännöllinen
kieli.
> Mutta jos kieli ei olekaan säännöllinen, ei tuota lukua n ole olemassa,
> joten merkkijonoa x = a^nb^n ei sitäkään ole olemassa.
Tokihan merkkijonot a^nb^n ovat olemassa (abstraktissa mielessä)
kaikille n:n arvoille, olettaen, että n on kokonaisluku. Jokaista
äärellistä merkkijonoa a^nb^n varten voidaan rakentaa äärellinen
automaatti, joka tunnistaa kyseisen merkkijonon ja vain sen.
Ei kuitenkaan voida rakentaa äärellistä automaattia, joka tunnistaisi
kaikki merkkijonot a^nb^n, kaikille n:n mahdollisille
kokonaislukuarvoille, mutta hylkäisi kaikki muut
merkkijonot. Pumppauslemman avulla tämä voidaan todistaa, ja siten
päätellä ettei kieli a^nb^n ole säännöllinen.
> Eli kieli todistetaan epäsäännölliseksi merkkijonon x perusteella,
> osoittamalla että ei ole olemassa äärellistä automaattia joka tunnistaisi
> merkkijonon x, mutta samalla seuraa ettei x:ää olekaan olemassa.
Mille tahansa annetulle (äärellisen mittaiselle) merkkijonolle x voidaan
rakentaa äärellinen automaatti, joka tunnistaa sen ja vain sen.
--
// Antti "lokori" Virtanen -//- http://www.students.tut.fi/~virtanea -//- 050-4004278
Mikko <>
> On 2003-10-21, Mikko <> wrote:
>
>> "Pumppauslemma:
>> Olkoon A säännöllinen kieli. Tällöin on olemassa sellainen n >= 1, että
>> mikä tahansa x c A, |x| >=n, voidaan jakaa osiin x = uvw siten, että
>> |uv|<=n,
>>|v| >=1, ja uv^iw c A kaikilla i=0,1,2..."
>> (Laskennan teoria / Pekka Orponen)
>>
>> Lemma sanoo että on olemassa luku n.
>
>> Vastaoletuksen jälkeen valitsemme merkkijonon x jonka pituus > n
>>
>> esim x=a^nb^n
>>
>> nythän x on nimenomaan yksi merkkijono, ei merkkijonojen joukko.
>
> Tässä on nyt kyse eri n:stä. Tuolla ylempänä n viittaa kielen
> tunnistavan äärellisen automaatin tilojen määrään ja tässä itse kielen
> määritelmään. Tietysti voit määritellä kielen x=a^nb^n, jossa n on
> jokin kiinteä luku, mutta silloin kielesi on triviaalisti säännöllinen
> kieli.
ei vaan kyseessä on sama n.
Juuri siksi x sidotaan n:ään, että näin voidaan valita yksittäinen
merkkijono, x >= n
nyt mikäli automaatti tunnistaa x:n, sen täytyy käyttää silmukkaa.
>> Mutta jos kieli ei olekaan säännöllinen, ei tuota lukua n ole olemassa,
>> joten merkkijonoa x = a^nb^n ei sitäkään ole olemassa.
>
> Tokihan merkkijonot a^nb^n ovat olemassa (abstraktissa mielessä)
> kaikille n:n arvoille, olettaen, että n on kokonaisluku. Jokaista
> äärellistä merkkijonoa a^nb^n varten voidaan rakentaa äärellinen
> automaatti, joka tunnistaa kyseisen merkkijonon ja vain sen.
oleellista on että kyseinen automaatti n, on pienempi kuin merkkijono x
jonka se tunnistaa.
Jos säännöllinen kieli sisältää silmukan, otat miten suuren automaatin
tahansa, aina on suurempi merkkijono, joka automaatin pitää hyväksyä.
> Ei kuitenkaan voida rakentaa äärellistä automaattia, joka tunnistaisi
> kaikki merkkijonot a^nb^n, kaikille n:n mahdollisille
> kokonaislukuarvoille, mutta hylkäisi kaikki muut
> merkkijonot. Pumppauslemman avulla tämä voidaan todistaa, ja siten
> päätellä ettei kieli a^nb^n ole säännöllinen.
>
>> Eli kieli todistetaan epäsäännölliseksi merkkijonon x perusteella,
>> osoittamalla että ei ole olemassa äärellistä automaattia joka tunnistaisi
>> merkkijonon x, mutta samalla seuraa ettei x:ää olekaan olemassa.
>
> Mille tahansa annetulle (äärellisen mittaiselle) merkkijonolle x voidaan
> rakentaa äärellinen automaatti, joka tunnistaa sen ja vain sen.
>
Merkkijono x on äärellinen. Mutta sen pituus on suurempi kuin sen
automaatin, joka tunnistaa x:n
Jori Mantysalo
> Pumppauslemman yleisin käyttötarkoitus on sen todistaminen, että ei
> ole äärellistä automaattia, joka hyväksyy annetun kielen. Todistus
> kulkee siten, että otetaan äärellinen automaatti joka hyväksyy
> *ainakin* kaikki kieleen kuuluvat merkkijonot, ja osoitetaan
> pumppaamalla että se hyväksyy *myös kielen ulkopuolisen*
> merkkijonon. Se ei siis hyväksy haluttua kieltä koska se hyväksyy
> "liikaa".
Saisiko yksinkertainen ihminen esimerkin tuollaisesta ei-säännöllisestä
kielestä ja sitä vastaavasta todistuksesta?
Tälläkö tavalla voidaan todistaa, että äärellinen automaatti ei voi
tunnistaa kieltä "A- ja B-kirjaimia miten monta vain, molempia yhtä
monta" tai "ensin A-kirjaimia mielivaltaisen monta ja sitten B-kirjaimia
yhtä monta"?
--
Pakanasanomat - julkijumalattoman kulttuurin helmi
http://tampere.vapaa-ajattelijat.fi/pakanasanomat/2003-3/
Jussi Piitulainen
> Valmari Antti kirjoitti:
>
>> Pumppauslemman yleisin käyttötarkoitus on sen todistaminen, että ei
>> ole äärellistä automaattia, joka hyväksyy annetun kielen. Todistus
>> kulkee siten, että otetaan äärellinen automaatti joka hyväksyy
>> *ainakin* kaikki kieleen kuuluvat merkkijonot, ja osoitetaan
>> pumppaamalla että se hyväksyy *myös kielen ulkopuolisen*
>> merkkijonon. Se ei siis hyväksy haluttua kieltä koska se hyväksyy
>> "liikaa".
>
> Saisiko yksinkertainen ihminen esimerkin tuollaisesta ei-säännöllisestä
> kielestä ja sitä vastaavasta todistuksesta?
>
> Tälläkö tavalla voidaan todistaa, että äärellinen automaatti ei voi
> tunnistaa kieltä "A- ja B-kirjaimia miten monta vain, molempia yhtä
> monta" tai "ensin A-kirjaimia mielivaltaisen monta ja sitten
> B-kirjaimia yhtä monta"?
Jep. Jos automaatti hyväksyy mielivaltaisen pitkiä A^m B^m jonoja,
niin se hyväksyy sellaisen A^n B^n, jossa on enemmän merkkejä kuin
automaatissa tiloja. Hyväksyvässä reitissä on sykli. Jaetaan jono
kolmeen osaan: A^n B^n = u v w. Syklissä luetaan v. Koska syklin voi
kulkea kahteen kertaan, myös u v v w kuuluu automaatin kieleen. Se ei
kuitenkaan voi olla muotoa A^m B^m.
--
Jussi
Valmari Antti
Jori Mäntysalo kysyi:
> Saisiko yksinkertainen ihminen esimerkin tuollaisesta ei-säännöllisestä
> kielestä ja sitä vastaavasta todistuksesta?
En tiedä voiko yksinkertainen ihminen saada, mutta Sinä kyllä voit.
Itse asiassa sellainen on tässä keskustelussa jo esitetty, mutta paloina,
joten voi olla hyödyllistä esittää kootusti.
Siis:
> "ensin A-kirjaimia mielivaltaisen monta ja sitten B-kirjaimia yhtä monta"?
Tarkastellaan *mitä tahansa* äärellistä automaattia N, joka hyväksyy
*ainakin* kaikki yllä olevan kuvauksen mukaiset merkkijonot.
Sivuhaara: sellainen automaatti on olemassa --- esimerkiksi yksitilainen
automaatti, jonka ainokainen tila on lopputila, ja jossa on kaari sekä
A-kirjaimella että B-kirjaimella. Jatko ei kuitenkaan riipu siitä, onko
sellaista olemassa.
Olkoon n automaatin N tilojen määrä.
Tarkastellaan merkkijonoa "ensin n A-kirjainta, sitten n B-kirjainta".
Se on kuvauksen mukainen. Niinpä N hyväksyy sen.
Tässä vaiheessa tottunut laskija vetoaa pumppauslemmaan, mutta selkeyden
vuoksi vetoan suoraan siihen syyhyn, miksi pumppauslemma pätee. Koska N
hyväksyy tarkastelun kohteena olevan merkkijonon, on olemassa polku
alkutilasta johonkin lopputilaan jonka varrelta koottujen A- ja B-kirjainten
jono on kyseinen merkkijono. Tämähän on hyväksymisen määritelmä.
Viimeistään kun on luettu tasan n A-kirjainta, kyseisen polun täytyy tulla
uudelleen solmuun jossa se on jo käynyt, koska uudet solmut loppuvat kesken
viimeistään silloin. Polussa täytyy siis olla silmukka jo ennen kuin yhtään
B-kirjainta on luettu.
Siltä varalta, että automaatissa on epsilon-kaaria tarvitaan vielä ylimääräinen
ajatuskiemura. Vaikka otettaisiin laskuissa huomioon vain alkusolmu sekä
ne polun solmut, joita edeltävä kaari ei ole epsilon-kaari, niin siltikin toisto
alkaa viimeistään n A-kirjaimen jälkeen. Nyt solmun ja sen toiston välillä
luetaan ainakin yksi A. Polussa täytyy siis olla silmukka, jossa luetaan ainakin
yksi A, ja joka sijaitsee ennen kuin yhtään B-kirjainta on luettu.
Kuljetaanpa polku, joka on muuten sama kuin äskeinen, mutta jätetään silmukka
kiertämättä. Se alkaa alkusolmusta, lukee alle n A-kirjainta, lukee
n B-kirjainta, ja päättyy loppusolmuun. Tämän polun vuoksi automaatti hyväksyy
sanan, jossa on alle n A-kirjainta ja sitten n B-kirjainta. Tämä sana ei ole
kuvauksen mukainen.
Johtopäätös: jokainen äärellinen automaatti, joka hyväksyy kuvauksen
mukaiset merkkijonot, hyväksyy myös ainakin yhden merkkijonon, joka ei
ole kuvauksen mukainen.
Niinpä ei ole olemassa äärellistä automaattia, joka hyväksyy *kaikki*
kuvauksen mukaiset merkkijonot *ja vain ne*.
> "A- ja B-kirjaimia miten monta vain, molempia yhtä monta"
Olkoon äärellisessä automaatissa joka hyväksyy kuvauksen mukaiset
merkkijonot n tilaa. Jono A^nB^n on kuvauksen mukainen, joten automaatti
hyväksyy sen. Kuten äsken, nähdään, että automaatti hyväksyy myös jonkin
A^mB^n missä m < n, vaikka ei saisi.
--- Antti Valmari ---
Jukka Suomela
> Siltä varalta, että automaatissa on epsilon-kaaria tarvitaan vielä
> ylimääräinen ajatuskiemura.
Mielenkiinnosta tiedustelen, miksi et yksinkertaisesti vaadi, että
automaatista on ensin poistettu epsilon-siirtymät?
--
Jukka Suomela - http://www.iki.fi/suo/
Valmari Antti
Jukka Suomela kysyi:
> Mielenkiinnosta tiedustelen, miksi et yksinkertaisesti vaadi, että
> automaatista on ensin poistettu epsilon-siirtymät?
Jori Mäntysalolle vastatessani olisin voinut niin tehdäkin. Ajattelin
viestiä kirjoittaessani kuitenkin myös alkuperäistä kysyjää, ja
hänellä on käsitteet niin sekaisin, että en halunnut edes yrittää
selittää mitä epsilon-siirtymien poisto tarkoittaa ja missä mielessä
se ei muuta mitään. Nyt selvisin kuudella rivillä, jotka toistavat jo
kertaalleen käytyä ajatuskuviota. Jaa, tästä viestistä tuli 6 riviä lisää :-|
Noin yleisemmin ottaen, epsilon-siirtymien poisto saattaa merkittävästi
kasvattaa kaarten määrää. Näin ollen sitä ei välttämättä kannata aina
tehdä käytännön algoritmeissa, joten on hyvä, että teoriakin sallii ne.
Tosin tässä nimenomaisessa tapauksessa tällä argumentilla ei ole merkitystä.
-- AV