Hetun tarkistus RegExp:llä
Jarkko
joka tarkastaisi henkilötunnuksen.
T: Jare
Tauno Voipio
> Löytyykö keneltäkään valmista RegExp-koodin pätkää
> joka tarkastaisi henkilötunnuksen.
Jää ainakin tarkistusmerkki laskematta.
--
Tauno Voipio
tauno voipio (at) iki fi
Ari Makela
> Jarkko wrote:
>> Löytyykö keneltäkään valmista RegExp-koodin pätkää
>> joka tarkastaisi henkilötunnuksen.
>
> Jää ainakin tarkistusmerkki laskematta.
Kyllä. Ja mitä regexp-murretta halutaan? Niitähän nimittäin riittää.
Perliksi esimerkiksi:
^\d{6}[+-]\d{3][a-zA-Z0-9]$
Tästä puuttuu vielä bisneslogiikkaa: päivämäärä ei voi olla yli
28, 29, 30 tai 31 päivästä, kuukaudesta ja vuodesta riippuen. Kuukausi
ei voi olla yli 12. Hajoaa kun tulee vuosi 10000, mutta silloin ei taida
enää olla SOTU:kaan käytössä.
Perlissä on tehokkaampaa käyttää muotoa
\d\d\d
kuin muotoa
\d{3}
mutta sotun päivämääräosassa helppolukuisuus alkaa jo olemaan ongelma
jos sen kirjoittaa \d\d\d\d\d\d\d\d. Tuohonkin melkein kirjoitin yhden
\d:n liikaa.
Ryhmiä käyttämällä tämän saa pilkottua koodille, joka tekee varsinaisen
tarkistuksen:
my $mday = undef;
my $mon = undef;
my $year = undef;
my $foo = undef;
my $check = undef;
my $cen = undef;
if ($s =~ m/^(\d\d)(\d\d)(\d\d)([+-])(\d\d\d)([A-Za-z0-9])$/) {
$mday = $1;
$mon = $2;
$year = $3;
$cen = $4;
$foo = $5;
$check = $6;
} else {
# sivistyneessä ohjemointikielessa tässä heitettäisiin
# poikkeus
}
# Täällä sitten tarkistetaan, että alustettujen muuttujien
# arvot ovat järkeviä
Ajatus- ja syntaksivirheiden korjaaminen jää kysyjän vastuulle.
--
Ari Makela late autumn -
ha...@arska.org a single chair waiting
http://arska.org/hauva/ for someone yet to come
-- Arima Akito
Jussi Piitulainen
> Jarkko wrote:
>> Löytyykö keneltäkään valmista RegExp-koodin pätkää
>> joka tarkastaisi henkilötunnuksen.
>
> Jää ainakin tarkistusmerkki laskematta.
Käytännössä varmaan niin, mutta jos pätkän pituudelle ei aseteta
rajoituksia, niin sitten onnistuu sekin: mahdollisia hetujahan on
äärellinen määrä. Jollain ohjelmalla voisi generoida sen pätkän.
Jyrki Saarinen
> Löytyykö keneltäkään valmista RegExp-koodin pätkää
> joka tarkastaisi henkilötunnuksen.
Säännöllisillä lausekkeilla ei ole minkäänlaista "laskentakykyä", mitä
hetun viimeinen digitti vaatii.
--
Jyrki
Eero Häkkinen
> Perliksi esimerkiksi:
>
> ^\d{6}[+-]\d{3][a-zA-Z0-9]$
Mitäs sitten kun henkilön HeTu onkin 161007A4379?
Tuhatluvun tunnukseksi on siis hyväksyttävä 1800-luvun (+) ja 1900-luvun (-)
lisäksi myös 2000-luku (A). Lisäksi on kirjaimet G, I, O, Q ja Z eivät
esiinny HeTun tarkistusmerkkinä. Saadaan siis
^\d{6}[A+-]\d{3}[0-9A-FHJ-NPR-Y]$
> Tästä puuttuu vielä bisneslogiikkaa: päivämäärä ei voi olla yli
> 28, 29, 30 tai 31 päivästä, kuukaudesta ja vuodesta riippuen. Kuukausi
> ei voi olla yli 12. Hajoaa kun tulee vuosi 10000, mutta silloin ei taida
> enää olla SOTU:kaan käytössä.
Hajoaa itse asiassa jo, kun tulee vuosi 2100, koska 2100-luvun tunnusta ei
ole vielä päätetty.
Jaakko Kangasharju
> On 2007-10-16, Tauno Voipio <tauno....@INVALIDiki.fi> wrote:
>> Jarkko wrote:
>>> Löytyykö keneltäkään valmista RegExp-koodin pätkää
>>> joka tarkastaisi henkilötunnuksen.
>>
>> Jää ainakin tarkistusmerkki laskematta.
>
> Kyllä. Ja mitä regexp-murretta halutaan? Niitähän nimittäin riittää.
> Perliksi esimerkiksi:
>
> ^\d{6}[+-]\d{3][a-zA-Z0-9]$
Pitää olla ainakin
^\d{6}[A+-]\d{3}[a-zA-Z0-9]$
Onhan 2000-lukua eletty jo kohta kahdeksan vuotta. Ja tuota
tarkistusmerkkiäkin voisi karsia niihin 31 sallittuun, jos haluaisi
tarkentaa.
> Hajoaa kun tulee vuosi 10000, mutta silloin ei taida enää olla
> SOTU:kaan käytössä.
Miksi se hajoaisi juuri vuonna 10000?
--
Jaakko Kangasharju
Join TFFFJ today!
Jussi Paju
>
> Kyllä. Ja mitä regexp-murretta halutaan? Niitähän nimittäin riittää.
> Perliksi esimerkiksi:
>
> ^\d{6}[+-]\d{3][a-zA-Z0-9]$
>
> Tästä puuttuu vielä bisneslogiikkaa: päivämäärä ei voi olla yli
> 28, 29, 30 tai 31 päivästä, kuukaudesta ja vuodesta riippuen. Kuukausi
> ei voi olla yli 12. Hajoaa kun tulee vuosi 10000, mutta silloin ei taida
> enää olla SOTU:kaan käytössä.
Tuo on hajonnut jo, eli ei päde kuin viimeistään vuonna 1999
syntyneille. 2000-luvulla syntyneillä loppuosan erotinmerkki on A, ja
siis vaikka tuon A:n lisäisi, koodi hajoaa vuoden 2999 jälkeen.
Olettaisin, että tuossa erotinmerkissä käytetään samaa kirjainsettiä
kuin tarkistusmerkissäkin, mutta en muista mitä sieltä on jätetty pois
joten en lähde spekuloimaan siitä kuinka pitkälle tulevaisuuteen tuon
asian voisi arvata. Melko todennäköisenä pidän kuitenkin sitä, että
parituhatta vuotta lisää saa lisäämällä B:n ja C:n. ;)
--
Jussi
:: Te audire no possum. Musa sapientum fixa est in aure.
:: I can't hear you. I have a banana in my ear.
Ari Makela
> Onhan 2000-lukua eletty jo kohta kahdeksan vuotta.
No mutta eihän tällä vuosituhannella syntyneitä ihmisiä ole
*oikeasti* olemassa... No ei, olisi pitänyt muistaa kirjoittaa,
että en oikeasti tiedä sotun speksiä eli "katso tuosta mallia" ja korjaa
virheet luettuasi speksin. My bad.
> Miksi se hajoaisi juuri vuonna 10000?
Oikosulku, joka syntyi siitä, että kun vuosi 10000 tulee niin vuosiluku
ei muutu kolminumeroiksi vaan välimerkki vaihtuu.
Kristian Ovaska
>> Jää ainakin tarkistusmerkki laskematta.
>Käytännössä varmaan niin, mutta jos pätkän pituudelle ei aseteta
>rajoituksia, niin sitten onnistuu sekin: mahdollisia hetujahan on
>äärellinen määrä. Jollain ohjelmalla voisi generoida sen pätkän.
Mikä mahtaa olla lyhin säännöllinen lauseke, joka tunnistaa myös
tarkistusmerkin? Suoraviivainen tapahan tuottaa noin 365*100*898
komponenttia yhdistettynä ehtomerkeillä (yksilönumero on välillä 2..899)
ja karkauspäivät päälle, mutta sitä saa varmasti sievennettyä. Tässä olisi
mielenkiintoinen haaste. Lisähaastetta saa vielä siitä, että todistaa
ratkaisun olevan minimaalinen valitulla säännöllisten lausekkeiden
syntaksilla (pysytään poissa Turing-täydellisistä "säännöllisistä
lausekkeista").
--
Kristian Ovaska - http://www.cs.helsinki.fi/u/hkovaska/
Ari Makela
> Onhan 2000-lukua eletty jo kohta kahdeksan vuotta.
No mutta eihän tällä vuosituhannella syntyneitä ihmisiä ole
*oikeasti* olemassa... No ei, olisi pitänyt muistaa kirjoittaa,
että en oikeasti tiedä sotun speksiä eli "katso tuosta mallia" ja korjaa
virheet luettuasi speksin. My bad.
> Miksi se hajoaisi juuri vuonna 10000?
Oikosulku, joka syntyi siitä, että en tullut ajatelleeksi sitä, että
kun vuosi 10000 tulee niin vuosiluku ei muutu kolminumeroiksi vaan
välimerkki vaihtuu.
--
Jussi Paju
> In sfnet.atk.ohjelmointi, Ari Makela <ha...@lagavulin.sappho.net> wrote:
> >
> > Kyllä. Ja mitä regexp-murretta halutaan? Niitähän nimittäin riittää.
> > Perliksi esimerkiksi:
> >
> > ^\d{6}[+-]\d{3][a-zA-Z0-9]$
> >
> > Tästä puuttuu vielä bisneslogiikkaa: päivämäärä ei voi olla yli
> > 28, 29, 30 tai 31 päivästä, kuukaudesta ja vuodesta riippuen. Kuukausi
> > ei voi olla yli 12. Hajoaa kun tulee vuosi 10000, mutta silloin ei taida
> > enää olla SOTU:kaan käytössä.
>
> Tuo on hajonnut jo, eli ei päde kuin viimeistään vuonna 1999
> syntyneille. 2000-luvulla syntyneillä loppuosan erotinmerkki on A, ja
> siis vaikka tuon A:n lisäisi, koodi hajoaa vuoden 2999 jälkeen.
> Melko todennäköisenä pidän kuitenkin sitä, että
> parituhatta vuotta lisää saa lisäämällä B:n ja C:n. ;)
Menin sitten itsekin halpaan kirjoitellessani "fiksuja", tosiaan A on
vain 20xx syntyneille ja tod.näk. B ja C 21xx ja 22xx syntyneille.
Pahus.
Asko Telinen
jep.
Helpoin tapa on varmaan jo aikaisemmissa viesteissä esitetty regexp,
joka tarkistaa vain sotun formaatin. Loput tarkistukset (dd.mm.yy
ylivuodot ym. tarkistusmerkit) sitten ohjelmointikielellä mitä ikinä
käytätkin.
Asko.
--
It is not necessary to understand things in order to argue about them.
Pierre Beaumarchais (1732 - 1799)
Jouko Holopainen
> Tästä puuttuu vielä bisneslogiikkaa: päivämäärä ei voi olla yli
> 28, 29, 30 tai 31 päivästä, kuukaudesta ja vuodesta riippuen. Kuukausi
> ei voi olla yli 12.
Nuo olisi kaikki periaatteessa mahdollista tarkistaa regexpillä, mutta
hommassa ei ole mitään kun se tarkistussumma pitää laskea kuitenkin.
Ja etenkin vuoden mukaan helmikuun päivät ...
"[2902[(96)|(92)|...]]|...". Tähän vielä että 00 on +:n ja -:n kanssa
kakausvuosi muttei A:n :-)
Menipä jo huumorin puolelle, sori.
--
@jhol
Jouko Holopainen
> Lisähaastetta saa vielä siitä, että todistaa
> ratkaisun olevan minimaalinen valitulla säännöllisten lausekkeiden
> syntaksilla (pysytään poissa Turing-täydellisistä "säännöllisistä
> lausekkeista").
Tällaisen todistaminen on (ainakin geneerisessä tapauksessa) teoriankin¹
mukaan mahdotonta, luultavasti myös tässä tapauksessa ainakin
käytännössä mahdotonta.
¹ ellen muista väärin tai sekoita johonkin muuhun
--
@jhol
Ari Saastamoinen
> Kyllä. Ja mitä regexp-murretta halutaan? Niitähän nimittäin riittää.
> Perliksi esimerkiksi:
>
> ^\d{6}[+-]\d{3][a-zA-Z0-9]$
Paitsi, että toi ei edes toimi. Esim. veljenpoikani HETU ei menisi
tuosta tarkistuksesta läpi, sillä hänellä ei ole hetussa lainkaan
miinusmerkkiä tai plussaa, vaan sillä kohdalla on kirjain A
--
Arzka oh3mqu+...@hyper.fi - En halua follareita mailina
1. Valitse sopiva paikka, ei ihmisten tai rakennusten lahella, jossa
paukku voi aiheuttaa hairiota. - Iso-Kiinalaisen kayttoohje
Jori Mantysalo
> Tästä puuttuu vielä bisneslogiikkaa: päivämäärä ei voi olla yli
> 28, 29, 30 tai 31 päivästä, kuukaudesta ja vuodesta riippuen.
Ja jos kysytään elävän ihmisen hetua, voinee huomioida myös iän.
Wikipedian mukaan vanhin koskaan elänyt suomalainen olisi kuollut
117-vuotiaana, ja varma tieto löytyy 114-vuotiaasta. Joka tapauksessa
yli 130-vuotiaat saa hylätä ilmeisinä virhesyötteinä. (Fiksu softa
voisi myös varoittaa yli 100-vuotiaasta, riippuen toki tilanteesta.)
Jos taas hetu voi kuulua kuolleelle, lienee tässä jokin sellainen
raja, että ihan 1800-luvun alussa syntyneet eivät ole ehtineet saada
hetua.
--
"Monella on koliikkivauvan lisäksi myös koliikkivaimo."
-- PH
Jori Mantysalo
> Mikä mahtaa olla lyhin säännöllinen lauseke, joka tunnistaa myös
> tarkistusmerkin? Suoraviivainen tapahan tuottaa noin 365*100*898
> komponenttia yhdistettynä ehtomerkeillä (yksilönumero on välillä 2..899)
> ja karkauspäivät päälle, mutta sitä saa varmasti sievennettyä.
Noin äkkiseltään ajatellen kovin helppo sieventäminen tarkoittaisi
heikkoa tarkistemerkkiä. Käsittääksen tuon tarkisteen pitäisi olla
sellainen, että yhden merkin korvaaminen tai kahden merkin vaihtaminen
ei voi tuottaa samaa tarkistetta.
Eikun... tarkistemerkkejä oli 31. Eli kyseessä on 9-numeroinen luku,
josta otetaan 31 jakojäännös. Jos siis 9-numeroinen luku kasvaa 31,
62, 93 jne. suuremmaksi, tarkiste pysyy samana. Eli jos luku loppuu
vaikka "54", niin sama tarkiste tulee jos loppu vaihdetaan merkkeihin
54-31="23". Toisella tapaa sanoen 54-45=9, ja 9 != 31, joten lopun
"54" kääntäminen havaitaan. Milloin sitten esimerkiksi
X*10+Y - Y*10+X = 31*N, jossa N=1,2,3... ja X,Y=0,1,2,3...
? Sain tulokseksi, että tuollaisia lukuja ei ole. Ilmeisesti ei
myöskään ole vastaavia numeropareja luvun keskellä, mutta en nyt
jaksa miettiä tätä.
Kai tästä ihan oikeaa teoriaakin on joku tehnyt.
Tuomo
> Kristian Ovaska wrote:
>> Lisähaastetta saa vielä siitä, että todistaa
>> ratkaisun olevan minimaalinen valitulla säännöllisten lausekkeiden
>> syntaksilla (pysytään poissa Turing-täydellisistä "säännöllisistä
>> lausekkeista").
>
> Tällaisen todistaminen on (ainakin geneerisessä tapauksessa) teoriankin¹
> mukaan mahdotonta, luultavasti myös tässä tapauksessa ainakin
> käytännössä mahdotonta.
>
> ¹ ellen muista väärin tai sekoita johonkin muuhun
Opiskeluajoilta muistelen näin:
Säännöllinen lauseke voidaan aina kuvata äärellisenä automaattina.
Äärelliset automaatit voidaan optimoida pienimmäksi mahdolliseksi
(vähiten tiloja) melko yksinkertaisella algoritmilla. Tulos on
todistettavasti 'pienin automaatti'.
Eli rakentamalla automaatin, joka hyväksyy kaikki mahdolliset hetut ja
optimoimalla se, saadaan lyhyin säännöllinen lauseke.
Tämä pitäisi tietysti rajata nykyisin mahdollisiin hetuihin, sillä
viimeistään vuonna 2100 hetun välimerkki muuttuu taas.
--
Tuomo
Kristian Ovaska
>Noin äkkiseltään ajatellen kovin helppo sieventäminen tarkoittaisi
>heikkoa tarkistemerkkiä. Käsittääksen tuon tarkisteen pitäisi olla
>sellainen, että yhden merkin korvaaminen tai kahden merkin vaihtaminen
>ei voi tuottaa samaa tarkistetta.
Toimisikos seuraava. Käsitellään hetua muodossa 10^8*n1 + 10^7+n2 + ...
n9, missä n:t ovat välillä 0..9. Meillä on suorakaiteen muotoinen
äärellinen automaatti, jossa on 9 saraketta ja 31 riviä. Kun luemme
ensimmäisen merkin n1, meillä on yksi luvuista {0, 10^8, 2*10^8, ...,
9*10^8}. Laskemme jakojäännöksen modulo 31 ja laitamme siirtymän sen
mukaisesti riville 0..30 ensimmäisellä sarakkeella. Jos rivi on vaikka 5,
on meillä luku 31*a+5. Kun luemme seuraavan merkin, saamme luvun
31*a+5+10^7*n2. Tämä on kongruentti luvun 5+10^7*n2 kanssa eli edelliseltä
sarakkeelta emme tarvitse muuta kuin tiedon jakojäännöksestä. Nyt laskemme
taas jakojäännöksen ja laitamme siirtymän seuraavalle sarakkeelle.
Sitten pitää vielä hylätä luvattomat päivämäärät, josta tulee jonkun
verran lisää siirtymiä.
Jouko Holopainen
> Säännöllinen lauseke voidaan aina kuvata äärellisenä automaattina.
> Äärelliset automaatit voidaan optimoida pienimmäksi mahdolliseksi
> (vähiten tiloja) melko yksinkertaisella algoritmilla. Tulos on
> todistettavasti 'pienin automaatti'.
Kuulostaa epäilyttävältä, sillä ei ole geneeristä tapaa todistaa että
kaksi säännöllistä lauseketta hyväksyvät ja hylkäävät aina samat
merkkijonot.
Paino sanalla "geneeristä", eli ehkäpä k.o. algoritmi tässä rajatussa
tapauksessa toimii.
--
@jhol
Kristian Ovaska
>Tuomo wrote:
>> Säännöllinen lauseke voidaan aina kuvata äärellisenä automaattina.
>> Äärelliset automaatit voidaan optimoida pienimmäksi mahdolliseksi
>> (vähiten tiloja) melko yksinkertaisella algoritmilla. Tulos on
>> todistettavasti 'pienin automaatti'.
>Kuulostaa epäilyttävältä, sillä ei ole geneeristä tapaa todistaa että
>kaksi säännöllistä lauseketta hyväksyvät ja hylkäävät aina samat
>merkkijonot.
Kyllä minimointi on mahdollista, kaivoin muistin virkistykseksi wanhan
cunnon P. Orposen Laskennan teoria -monisteen, jossa asia selitetään.
Wikipediassa (http://en.wikipedia.org/wiki/Finite_state_machine) on myös
hieman juttua. Mahdollisesti sekoitat Turing-täydellisiin kieliin, joissa
tämänkaltaiset hommat ovat ratkeamattomia.
Timo Korvola
> Eli rakentamalla automaatin, joka hyväksyy kaikki mahdolliset hetut ja
> optimoimalla se, saadaan lyhyin säännöllinen lauseke.
Mitenkäs ajattelit muuntaa minimaalisen deterministisen automaatin
regexpiksi, ja miksi muunnoksen tulos olisi minimaalinen regexp?
--
Timo Korvola <URL:http://www.iki.fi/tkorvola>
Jussi Piitulainen
> Tuomo wrote:
>> Säännöllinen lauseke voidaan aina kuvata äärellisenä automaattina.
>> Äärelliset automaatit voidaan optimoida pienimmäksi mahdolliseksi
>> (vähiten tiloja) melko yksinkertaisella algoritmilla. Tulos on
>> todistettavasti 'pienin automaatti'.
>
> Kuulostaa epäilyttävältä, sillä ei ole geneeristä tapaa todistaa
> että kaksi säännöllistä lauseketta hyväksyvät ja hylkäävät aina
> samat merkkijonot.
Sikäli kuin kyse on laskennan teoriassa tavallisesti määritellyistä
säännöllisistä lausekkeista - äärelliset jonot, alternaatio,
katenaatio ja katenaatiosulkeuma - ne voidaan todella aina muuttaa
äärellisiksi automaateiksi, jotka taas voi determinoida ja minimoida.
Saadaan pienin deterministinen äärellinen automaatti, joka hyväksyy
juuri ne jonot, joihin alkuperäinen lauseke täsmää.
Ainakin determinististen automaattien leikkaus on yksinkertainen
toimitus, samoin sen toteaminen, hyväksyykö leikkausautomaatti mitään
jonoja.
Pienintä säännöllistä lauseketta tällä tavalla ei kuitenkaan saada,
eikä edes pienintä automaattia: epädeterministinen automaatti voi olla
paljon pienempi kuin samat jonot hyväksyvä pienin deterministinen.
Arto Wikla
"regular expression") ilmaisuvoimaa!? Hetuhan on välimerkkeineen 11
merkkiä pitkä merkkijono, joka muodostuu kirjaimista, numeroista
ja (eräistä) erikoismerkeistä. Tuollaisia merkkijonoja on vain
äärellinen määrä ja melko pieni osa niistä kelpaa henkilötunnukseksi.
Kirjoitetaan siis vain sellainen äärimmäisen simppeli säännöllinen
lauseke, joka vaihtoehtoina luettelee kaikki kelvolliset
henkilötunnukset. Lauseke on tosin inhimillisesti ajatellen melko pitkä,
mutta logiikaltaan triviaali... ;-)
Ja itse asiassa siis _kaikki_ äärelliset kielet ovat myös säännöllisiä,
koska pelkällä vaihtoehtojen luettelolla voidaan tunnistaa ja generoida
kaikki kielen lauseet. MOT :-)
Arto
--
Arto Wikla
Ja sitten ne harjoitustehtävät (ope on aina ope... ;-)
1) Kirjoita suosikkiohjelmointikielelläsi ohjelma, joka generoi kaikki
kelvolliset hetut 1800-2099 (so. välimerkit +, - ja A käytössä)
tunnistavan säännollisen lausekkeen suosimallasi "regexp"-kielellä.
Älä unohda ottaa karkausvuosia huomioon.
2) Miten monta erilaista löytyi?
3) Pystyykö suosikki-"regexp"-kielesi käsittelemään noin suurta -
vaikkakin simppeliä - lauseketta?
4) Mikä neuvoksi?
Arto :-)
--
Janne Tuukkanen
> että ihan 1800-luvun alussa syntyneet eivät ole ehtineet saada hetua.
Työeläkenumero tuli käyttöön 1962. Mistään en kuitenkaan
löytänyt tietoa kuka olisi ollut varhaiten syntynyt hetun
haltija. Siinä olisi ihan hauska tietokilpailukysymys.
Syntymävuosi 1850 olisi kai kaiken järjen mukaan kelvollinen
alaraja. Työeläkettä 112 -vuotias tuskin olisi saanut, mutta
1964 hänelle olisi todennäköisesti rekisteröity 114-vuotiaana
Kansaneläkelaitoksen sosiaaliturvatunnus.
JanneT
Jori Mantysalo
> Työeläkenumero tuli käyttöön 1962. Mistään en kuitenkaan
> löytänyt tietoa kuka olisi ollut varhaiten syntynyt hetun
> haltija. Siinä olisi ihan hauska tietokilpailukysymys.
Laitanpa tästä VRK:lle kysymyksen, siellä varmaan on tietoa.
Jori Mantysalo
>> Työeläkenumero tuli käyttöön 1962. Mistään en kuitenkaan
>> löytänyt tietoa kuka olisi ollut varhaiten syntynyt hetun
>> haltija. Siinä olisi ihan hauska tietokilpailukysymys.
> Laitanpa tästä VRK:lle kysymyksen, siellä varmaan on tietoa.
Oikea vastaus on 1.1.1800.
No, ei ihan oikea. Mutta systeemiä luotaessa on joku vuonna 1900
syntynyt vahingossa merkattu 100 vuotta liian vanhaksi. Hetu on sitten
toki passivoitu, mutta sellainen on siis tavallaan olemassa.
Vanhimpia oikeita hetuja VRK:lta vastannut arveli olevan 1850-luvun
lopusta.
Voisi olettaa, että tuo 1800-hetu on sellainen, että voi tulla vastaan
vain valtion sisäisissä tietojärjestelmissä. Tuskin noita passivoituja
hetuja "vuotaa" VRK:n ulkopuolelle mitenkään.
Jussi Paju
>
> Voisi olettaa, että tuo 1800-hetu on sellainen, että voi tulla vastaan
> vain valtion sisäisissä tietojärjestelmissä. Tuskin noita passivoituja
> hetuja "vuotaa" VRK:n ulkopuolelle mitenkään.
Itseasiassa passivoitu tai kuolleen henkilön hetu voi tulla vastaan
VTJkyselyn kautta, jonkinverran olen itse joutunut tuon systeemin kanssa
touhuamaan ja kyselyjä tekevän sovelluksen on hanskattava myös
tuollaiset tapaukset.
http://www.vrk.fi/vrk/home.nsf/pages/D07DFBF22E544291C22571FF003C9AA1?opendocument
Juha Lyytikainen
> Löytyykö keneltäkään valmista RegExp-koodin pätkää
> joka tarkastaisi henkilötunnuksen.
Paska juttu että suomessa voi syntyä vain 999 lasta päivässä.
Jori Mantysalo
>> Löytyykö keneltäkään valmista RegExp-koodin pätkää
>> joka tarkastaisi henkilötunnuksen.
> Paska juttu että suomessa voi syntyä vain 999 lasta päivässä.
Onko NNNNNN-000X -muotoinen tunniste kielletty? De facto niitä ei
taida olla käytössä, mutta mikään virallinen asetus ei tuota kieltäne.
Eli tuhat lasta päivässä.
Tuhat lasta päivässä tekisi teoriassa 365000 lasta vuodessa. Tämä on
luokkaa 5 kertaa ikäluokan koko. Tietenkään syntymät eivät jakaudu
tasan, mutta ei noin suurta piikkiä silti synny.
Ainoa mieleentuleva erikoisuus olisi suuren pakolaisjoukon saapuminen
maasta, jossa ei ole henkilöpapereita, toimivaa hallitusta ym. Tällöin
kai ikä arvioitaisiin, ja ehkä sitten laitettaisiin vaikka 1.1.1970
syntymäajaksi kaikille, joiden arvellaan syntyneet 1970-luvun vaihteessa.
Jaakko Kangasharju
> Jouko Holopainen <jh...@iki.finland.invalid>:
>>Kuulostaa epäilyttävältä, sillä ei ole geneeristä tapaa todistaa että
>>kaksi säännöllistä lauseketta hyväksyvät ja hylkäävät aina samat
>>merkkijonot.
>
> Kyllä minimointi on mahdollista, kaivoin muistin virkistykseksi wanhan
> cunnon P. Orposen Laskennan teoria -monisteen, jossa asia selitetään.
> Wikipediassa (http://en.wikipedia.org/wiki/Finite_state_machine) on myös
> hieman juttua. Mahdollisesti sekoitat Turing-täydellisiin kieliin, joissa
> tämänkaltaiset hommat ovat ratkeamattomia.
Itse asiassa tuo ekvivalenssiongelma on ratkeamaton jo
kontekstittomille kielille. Säännöllisille kielille se tosiaan on
ratkeava, mutta käytetystä formalismista riippuen vaadittava
suoritusaika saattaa vaihdella hyvinkin paljon.
--
Jaakko Kangasharju
Do you cry alone, do you cough by yourself?
Jaakko Kangasharju
> Pienintä säännöllistä lauseketta tällä tavalla ei kuitenkaan saada,
> eikä edes pienintä automaattia: epädeterministinen automaatti voi olla
> paljon pienempi kuin samat jonot hyväksyvä pienin deterministinen.
Ja pienimmän säännöllisen lausekkeen löytäminen ei edes ole kovin
helppo ongelma. Nimittäin säännöllisten lausekkeiden ekvivalenssi on
PSPACE-täydellinen, joten minimalisoinnin on oltava PSPACE-vaikea,
koska sen avulla voi ratkaista ekvivalenssin.
--
Jaakko Kangasharju
Yes, my first name really has two a's and two k's
Copy and paste if you are not sure to get it right
Jaakko Kangasharju
> Säännöllisillä lausekkeilla ei ole minkäänlaista "laskentakykyä", mitä
> hetun viimeinen digitti vaatii.
Säännöllisillä lausekkeilla on kyllä riittävästi "laskentakykyä" hetun
viimeisen merkin tarkistukseen. Kyseessähän on nimittäin vain
modulo-operaatio, jonka toteuttaminen äärellisenä automaattina on aika
helppo homma, eli siis onnistuu myös säännöllisellä lausekkeella.
(siitä en sitten tiedä, kuinka monimutkainen lausekkeesta tulee...)
--
Jaakko Kangasharju
If an aunt had balls, she would be an uncle
Jukka Kohonen
>- - Tällöin
>kai ikä arvioitaisiin, ja ehkä sitten laitettaisiin vaikka 1.1.1970
>syntymäajaksi kaikille, joiden arvellaan syntyneet 1970-luvun vaihteessa.
Hiukan tuontapaista tapahtui, kun sosiaaliturvatunnuksia ruvettiin
antamaan koko väestölle. Joissakin pohjoisen kunnissa olivat väestö-
rekisterissä syntymäajat kasautuneet kuukauden 15. ja 30. päivän
tienoille - taisivat olla arvioita.
--
Jukka....@iki.fi
* Parempi kyy povessa kuin kymmenen oksalla.
Juha Laiho
>Kuulemma yksilönumerokonfliktien välttämiseksi 2000-luvun puolella
>syntyneille jaeltaisiin yksilönumeroita yli 500 (en tunne ketään moista,
>eivätkä ko. ikäluokat vielä sankoin joukoin myöskään asioi omissa
>nimissään)
... kas, en ollut kiinnittänyt tuohon huomiota, mutta voin vahvistaa;
lasteni hetuissa yksilönumerot ovat 5xx ja 6xx.
--
Wolf a.k.a. Juha Laiho Espoo, Finland
(GC 3.0) GIT d- s+: a C++ ULSH++++$ P++@ L+++ E- W+$@ N++ !K w !O !M V
PS(+) PE Y+ PGP(+) t- 5 !X R !tv b+ !DI D G e+ h---- r+++ y++++
"...cancel my subscription to the resurrection!" (Jim Morrison)
Jori Mantysalo
> Toimisikos seuraava. Käsitellään hetua muodossa 10^8*n1 + 10^7+n2 + ...
> n9, missä n:t ovat välillä 0..9. Meillä on suorakaiteen muotoinen
> äärellinen automaatti, jossa on 9 saraketta ja 31 riviä. Kun luemme
> ensimmäisen merkin n1, meillä on yksi luvuista {0, 10^8, 2*10^8, ...,
> 9*10^8}. Laskemme jakojäännöksen modulo 31 ja laitamme siirtymän sen
> mukaisesti riville 0..30 ensimmäisellä sarakkeella. Jos rivi on vaikka 5,
En saa ajatusta konkretisoitua. Miten tuo menisi, jos esim. pitäisi
tarkistaa että kolminumeroinen luku on kolmella jaollinen? Tällainen
esimerkki kai on helpompi esittää.
Kristian Ovaska
Tarkastellaan vaikka lukua 714. Ensin luetaan merkki 7 mikä vastaa lukua
700. Tämän jakojäännös on 1, joten siirtymä alkutilasta menee
ensimmäiselle sarakkeelle riville 1 (rivit numeroidaan 0..2). Sitten
luetaan merkki 1, jolloin meillä on luku 710 eli (a*3+1)+10, missä a*3+1
on edelliseen sarakkeen luku, josta olemme enää kiinnostuneita
jakojäännöksestä. Jätämme tekijän a*3 pois kongruenssisääntöjen nojalla
eli jäljelle jää 11. Tämän jakojäännös on 2, joten siirtymä seuraavaan
sarakkeeseen menee riville 2. Nyt luetaan merkki 4, eli meillä on luku
(b*3+2)+4 = 6 (mod 3). Jakojäännös on 0 ja menemme viimeisellä sarakkeella
riville 0, eli 714 mod 3 = 0.
Kalle Olavi Niemitalo
> Tarkastellaan vaikka lukua 714. Ensin luetaan merkki 7 mikä vastaa lukua
> 700. Tämän jakojäännös on 1, joten siirtymä alkutilasta menee
> ensimmäiselle sarakkeelle riville 1 (rivit numeroidaan 0..2). Sitten
> luetaan merkki 1, jolloin meillä on luku 710 eli (a*3+1)+10, missä a*3+1
> on edelliseen sarakkeen luku, josta olemme enää kiinnostuneita
> jakojäännöksestä. Jätämme tekijän a*3 pois kongruenssisääntöjen nojalla
> eli jäljelle jää 11. Tämän jakojäännös on 2, joten siirtymä seuraavaan
> sarakkeeseen menee riville 2. Nyt luetaan merkki 4, eli meillä on luku
> (b*3+2)+4 = 6 (mod 3). Jakojäännös on 0 ja menemme viimeisellä sarakkeella
> riville 0, eli 714 mod 3 = 0.
Millainen säännöllinen lauseke sitten vastaa tuota tilakonetta?
Tämmöisen nyt ainakin voi Perl 5 -syntaksilla tehdä:
/ [0369]([0369][0369]|[147][258]|[258][147])
|[147]([0369][258]|[147][147]|[258][0369])
|[258]([0369][147]|[147][0369]|[258][258]) /x
mutta näyttää että jos pitäisikin tunnistaa kolminumeroisten
sijasta nelinumeroisia lukuja, niin säännöllisen lausekkeen
pituus kolminkertaistuisi. Voiko tämän eksponentiaalisen
kasvun välttää jollakin kikalla? (Perl-temppuja ei lasketa.)
Kristian Ovaska
>mutta näyttää että jos pitäisikin tunnistaa kolminumeroisten
>sijasta nelinumeroisia lukuja, niin säännöllisen lausekkeen
>pituus kolminkertaistuisi. Voiko tämän eksponentiaalisen
>kasvun välttää jollakin kikalla? (Perl-temppuja ei lasketa.)
Hyvä kysymys. Ei pikaisella nettihaulla löytynyt, onko olemassa
automaatteja, joita vastaava säännöllinen lauseke on väistämättä
eksponentiaalinen (kun sallitaan automaatin muokkaaminen semantiikka
säilyttäen). Yksi lähde [1] käsittelee asiaa ja ainakaan siinä valitulla
tekniikalla eksponentiaalista kasvua ei voi välttää.
Kun tehdään muunnosta toisinpäin RE->FSM, saadaan pienempi automaatti kun
käytetään epädeterministisiä automaatteja. Deterministisestä automaatista
voi tulla eksponentiaalinen RE:n pituuden suhteen. Ehkä muunnoksessa
FSM->RE voi ensin miettiä, miten automaattia voisi muuttaa
epädeterministiseksi siten että se sopii paremmin muunnettavaksi
säännölliseksi lausekkeeksi...
Säännöllinen lauseke on muuten tässä yhteydessä tavallaan välivaihe, koska
lauseke voidaan muuttaa takaisin automaatiksi kun se evaluoidaan.
[1]
Obtaining shorter regular expressions from finite-state automata. YS Han,
D Wood. Theoretical Computer Science, 2007.
Kalle Olavi Niemitalo
> Hyvä kysymys. Ei pikaisella nettihaulla löytynyt, onko olemassa
> automaatteja, joita vastaava säännöllinen lauseke on väistämättä
> eksponentiaalinen (kun sallitaan automaatin muokkaaminen semantiikka
> säilyttäen). Yksi lähde [1] käsittelee asiaa ja ainakaan siinä valitulla
> tekniikalla eksponentiaalista kasvua ei voi välttää.
Jospa muutetaan tehtävää näin:
- Syötteen pituutta ei rajata kolmeen numeroon.
- Syötteessä voi olla vain numeroita 1 ja 2 sekä loppumerkki.
Nollaakaan ei siis tarvitse ymmärtää.
- Automaatin pitää tarkistaa, onko sen saamien numeroiden summa
kolmella jaollinen.
Tähänhän riittää äärellinen deterministinen automaatti, jossa on
kolme tavallista tilaa (senhetkisen summan jakojäännöksille 0, 1
ja 2) ja kaksi lopetustilaa (joihin siirrytään vain loppumerkin
tullessa). Mutta voiko tämän automaatin muuntaa äärellisen
pituiseksi säännölliseksi lausekkeeksi ensinkään?
Eli jos tarvittavan säännöllisen lausekkeen pituus kasvaa
eksponentiaalisesti, niin onko eksponenttina automaatin koko
vai syötteen pituus?
Sami Silvennoinen
> Jospa muutetaan tehtävää näin:
> - Syötteen pituutta ei rajata kolmeen numeroon.
> - Syötteessä voi olla vain numeroita 1 ja 2 sekä loppumerkki.
> Nollaakaan ei siis tarvitse ymmärtää.
> - Automaatin pitää tarkistaa, onko sen saamien numeroiden summa
> kolmella jaollinen.
> Tähänhän riittää äärellinen deterministinen automaatti, jossa on
> kolme tavallista tilaa (senhetkisen summan jakojäännöksille 0, 1
> ja 2) ja kaksi lopetustilaa (joihin siirrytään vain loppumerkin
> tullessa). Mutta voiko tämän automaatin muuntaa äärellisen
> pituiseksi säännölliseksi lausekkeeksi ensinkään?
Kleenen lause: Säännölliset kielet ovat tarkalleen kaikki äärellisten
automaattien tunnistamat kielet.
Eli mille tahansa äärelliselle automaatille (myös epädeterministiselle)
voidaan konstruoida ekvivalentti säännöllinen lauseke.
Tehtäväsi ratkaisu:
/^((1(21)*(22|1)|2)((11|2)(21)*(22|1)|12)*((11|2)(21)*2L|1L)|1(21)*2L|L)$/
Tein sen paperilla enkä jaksanut sievennellä yhtään, joten siellä
on jopa turhia loppumerkkejä (jota merkitsin L:llä). En myöskään
tarkistanut, joten saattaa olla väärinkin, mutta pikaisen testin
perusteella näyttää toimivan.
--
Sami
Jukka Kohonen
>Kalle Olavi Niemitalo <k...@iki.fi> wrote:
>> - Syötteessä voi olla vain numeroita 1 ja 2 sekä loppumerkki.
>> Nollaakaan ei siis tarvitse ymmärtää.
>> - Automaatin pitää tarkistaa, onko sen saamien numeroiden summa
>> kolmella jaollinen.
>
>
>/^((1(21)*(22|1)|2)((11|2)(21)*(22|1)|12)*((11|2)(21)*2L|1L)|1(21)*2L|L)$/
Jeps. Ja vähän lyhyemmin:
/^(1(12)*(2|11)|2(21)*(1|22))*L$/
Tuosta voi sitten suoraviivaisesti rakennella ratkaisun vähän
yleisempään ongelmaan "tunnistettava kaikki kolmella jaolliset
numerojonot, sallitaan numerot 0...9". Korvataan vain kaikki ykköset
[147]:llä, kakkoset [258]:lla ja lisätään uloimpien sulkujen sisään
vaihtoehto [0369].
31:llä jaollisuus vaatii jo vähän isomman lausekkeen :-)
Jori Mantysalo
> Jospa muutetaan tehtävää näin:
> - Syötteen pituutta ei rajata kolmeen numeroon.
> - Syötteessä voi olla vain numeroita 1 ja 2 sekä loppumerkki.
> Nollaakaan ei siis tarvitse ymmärtää.
> - Automaatin pitää tarkistaa, onko sen saamien numeroiden summa
> kolmella jaollinen.
Huomaan nyt kysyneeni huonosti. Alkuperäinen tehtävähän siis koski
hetun tarkistusta, ja siitä nyt erityisesti tarkistemerkin osuutta
eli käytännössä jakojäännöksen luvulla 31 jaettaessa laskemista.
Jaollisuus luvulla kolme onnistuu kymmenlukujärjestelmässä ikäänkuin
kiertotietä, koska siihen sattuu löytymään tuollainen kätevä sääntö.
Vastaavastihan esim. kymmenellä kertominen onnistuu ilman oikeaa
kertomista.
Muutetaan tehtävää siten, että pitää tarkistaa onko kymmenjärjestelmässä
annettu luku jaollinen luvulla 7. Tähän ei taida automaatti taipua?
Kysymys voidaan muotoilla toisinkin: voidaanko vaikkapa 10-numeroisen
luvun jaollisuus luvulla 7 tarkistaa jotenkin olennaisesti helpommin
kuin luettelemalla kaikki vaihtoehdot?
Intuitio sanoo, että ei voida. En osaa tuota nyt formalisoida
siististi, joten tämä jää minulta vain intuition tasolle.
Jukka Kohonen
>Tuosta voi sitten suoraviivaisesti rakennella ratkaisun vähän
>yleisempään ongelmaan "tunnistettava kaikki kolmella jaolliset
>numerojonot, sallitaan numerot 0...9". Korvataan vain kaikki ykköset
>[147]:llä, kakkoset [258]:lla ja lisätään uloimpien sulkujen sisään
>vaihtoehto [0369].
No joo, pitää niitä [0369]-jonoja tunkea useampaankin väliin.
Tämmöinen ainakin tuntuisi toimivan. Testattu luvuilla 0...100000000.
/^([0369]|[147][0369]*([147][0369]*[258][0369]*)*([258]|[147][0369]*[147])|[258][0369]*([258][0369]*[147][0369]*)*([147]|[258][0369]*[258]))*[0369]*$/
Siis tunnistaa kolmella jaolliset numerojonot. (Joissakin
ohjelmointikielissä on kyllä kätevämpiäkin keinoja samaan hommaan.)
Jukka Kohonen
>Muutetaan tehtävää siten, että pitää tarkistaa onko kymmenjärjestelmässä
>annettu luku jaollinen luvulla 7. Tähän ei taida automaatti taipua?
Kyllä se taipuu. Automaatista tulee vaan mutkikkaampi.
Ensinnäkin nyt on 7 eikä 3 mahdollista jakojäännöstä, joten sen takia
tulee lisää tiloja.
Pahempi juttu on, että luvun eri positioilla on eri vaikutus jako-
jäännökseen, joten automaatin täytyy pitää kirjaa siitäkin, missä
positiossa ollaan: eri positioissa on erilaiset siirtymät. Koska
kuitenkin (10^6) % 7 = 1, tarvitsee positio muistaa vain "modulo 6",
eli luvun seitsemäs numero käsitellään samalla tavalla kuin
ensimmäinen, kahdeksas samalla tavoin kuin toinen jne.
(3:lla jaettaessa positiota ei tarvitse muistaa, koska jo (10^1) % 3
= 1, eli jokaisen position vaikutus jakojäännökseen on sama.)
Asioita voi vähän yksinkertaistaa, jos luvun numerot annetaan
käänteisessä järjestyksessä (ensin ykköset, sitten kymmenet jne).
Tällöin selvitään 6*7 = 42 tilan deterministisellä automaatilla.
Se hyväksyy sitten mielivaltaisen pituiset 7:llä jaolliset luvut
(käänteisinä).
Tilat on mukavinta numeroida (r,k), missä r=0,...,6 on senhetkinen
jakojäännös ja k=0,...,5 on käsiteltävän numeron positio (mod 6).
Alkutilasta (0,0) siirrytään tilaan (d%7, 1) jos luetaan numero d.
Tilasta (r,0) siirrytään numerolla d tilaan ((r+d)%7, 1),
tilasta (r,1) siirrytään numerolla d tilaan ((r+10*d)%7, 2),
tilasta (r,2) siirrytään numerolla d tilaan ((r+100*d)%7, 3),
jne.
Hyväksyviä lopetustiloja ovat tilat (0,k).
Samaan tapaan voi yleisemminkin tehdä deterministisen äärellisen
automaatin, joka tunnistaa mielivaltaisen pituiset a:lla jaolliset
luvut b-järjestelmässä (numerot käännettynä). Jos välttämättä haluaa,
sen voi konvertoida (pitkähköksi) säännölliseksi lausekkeeksi.
Jos vielä halutaan, että luvun numerot annetaan länsimaiseen tapaan
isoin ensin, niin on se lisäongelma, ettei ekaa numeroa luettaessa
tiedetä, mitä kymmenen potenssia se vastaa. Suoraviivainen ratkaisu on
käyttää epädeterminististä automaattia, joka "arvaa" aloitusposition,
ja luettuaan luvun loppuun hyväksyy ratkaisun jos _päädyttiin_
positioon nolla. (Epädeterministisen äärellisen automaatin voi
puolestaan muuntaa deterministiseksi.)
Jori Mantysalo
>>Muutetaan tehtävää siten, että pitää tarkistaa onko kymmenjärjestelmässä
>>annettu luku jaollinen luvulla 7. Tähän ei taida automaatti taipua?
> Kyllä se taipuu. Automaatista tulee vaan mutkikkaampi.
> Ensinnäkin nyt on 7 eikä 3 mahdollista jakojäännöstä, joten sen takia
> tulee lisää tiloja.
> Pahempi juttu on, että luvun eri positioilla on eri vaikutus jako-
> jäännökseen, joten automaatin täytyy pitää kirjaa siitäkin, missä
> positiossa ollaan: eri positioissa on erilaiset siirtymät. Koska
> kuitenkin (10^6) % 7 = 1, tarvitsee positio muistaa vain "modulo 6",
> eli luvun seitsemäs numero käsitellään samalla tavalla kuin
> ensimmäinen, kahdeksas samalla tavoin kuin toinen jne.
> - -
> Samaan tapaan voi yleisemminkin tehdä deterministisen äärellisen
> automaatin, joka tunnistaa mielivaltaisen pituiset a:lla jaolliset
> luvut b-järjestelmässä (numerot käännettynä).
Ah, totta.
Kuinka pitkä tuollaisesta säännöllisestä lausekkeesta tulee? Ts.
säästääkö se verrattuna suoraan luetteloon? Tai säästää tietysti,
mutta miten pitkillä luvuilla?
Nimittäin alkuperäiseen tehtävään palatakseni: jaollisuus luvulla 31
vastaavasti laskien tarkoittaa, että vasta (10^30)%31 tuottaa halutun
tuloksen, ja automaatin vaatima tilojen lukumäärä taas kasvaa liiaksi
- hetussa on vain 9 merkkiä (ilman sitä tarkistetta siis), eikä päästä
hyödyntämään sitä, että 30 merkin jälkeen päästään ikäänkuin
hyppäämään taaksepäin.
Kalle Olavi Niemitalo
> Pahempi juttu on, että luvun eri positioilla on eri vaikutus jako-
> jäännökseen, joten automaatin täytyy pitää kirjaa siitäkin, missä
> positiossa ollaan: eri positioissa on erilaiset siirtymät.
Ei kai siitä tarvitse pitää kirjaa. Tehdään seitsemän tilaa 0...6
ja siirtymät: uusi = (vanha * 10 + syöte) % 7. Numerot sitten
syötetään tähän arvokkain ensin.
Jukka Kohonen
>Ei kai siitä tarvitse pitää kirjaa. Tehdään seitsemän tilaa 0...6
>ja siirtymät: uusi = (vanha * 10 + syöte) % 7. Numerot sitten
>syötetään tähän arvokkain ensin.
No niinpäs tietysti :-)
(Ja yleisesti n tilaa riittää n:llä jaollisuuden tsekkaamiseen.)
Vastaava säännöllinen lauseke onkin sitten "vähän" mutkikkaampi.
Kyllähän sen Kleenen lauseen avulla voi konstruoida mutta...
Jukka Kohonen
>Kuinka pitkä tuollaisesta säännöllisestä lausekkeesta tulee?
Melko pitkä.
Tätä voi kokeilla JFLAPilla <http://www.jflap.org>, joka osaa (muun
muassa) muuntaa äärellisen automaatin säännölliseksi lausekkeeksi.
Kuten todettua, mielivaltaisen pituisen luvun n:llä jaollisuuden voi
testata n-tilaisella automaatilla, jonka siirtymät noudattavat
yksinkertaista kaavaa: tilasta i numerolla d tilaan (b*i+d)%n, missä b
on lukujärjestelmän kantaluku.
3:lla jaollisuus 10-järjestelmässä onnistuu 3-tilaisella automaatilla.
JFLAP tuottaa siitä (hiukan käsin avustettuna) tällaisen säännöllisen
lausekkeen:
^([0369]|[147][0369]*[258]|([258]|[147][0369]*[147])([0369]|[258][0369]*[147])*([147]|[258][0369]*[258]))*$
joka näyttäisi toimivan ok.
7:llä jaollisuus onnistuu 7-tilaisella automaatilla, josta tuli 10315
merkkiä pitkä säännöllinen lauseke. Sekin näyttää kyllä toimivan :-)
Kalle Olavi Niemitalo
> Kleenen lause: Säännölliset kielet ovat tarkalleen kaikki äärellisten
> automaattien tunnistamat kielet.
Mikäs tämä "Kleenen lause" on englanniksi?
Mika Iisakkila
Kieltämättä tuo ylläoleva suomennos on vähän "aseet salaiset armeijan
ovat sukat pitkät harmaat" -tyyppinen. Kleenen teoreeman toinen osa on
kuitenkin enklanniksi "any language accepted by a finite automaton is
regular" ja ensimmäinen sisällöltään jotain "jokaista säännöllistä
lauseketta vastaa epädeterministinen äärellinen automaatti".
Vastaavuus molempiin suuntiin enivei.
Säännöllisestä lausekkeesta automaattiin pääsee jotakuinkin
koneellisesti Thompsonin algoritmilla ja jollain tuosta Kleenen
lauseesta johdetulla ominaisuudella, toisen suunnan menetelmistä ei
nyt muistu mitään mieleen.
--
http://www.hut.fi/u/iisakkil/ --Foo.
Sami Silvennoinen
Kaiketi se on "Kleene's Theorem", mutta nimitys ei näytä olevan
mitenkään vakiintunut (ei löydy Mathworldistä eikä Wikipediasta).
Ylläoleva lainaukseni on suomenkielisestä opintomonisteesta.
Automaattien ja formaalisten kielten teorian perusteoksessa
"Introduction to Automata Theory, Languages, and Computation" (Hopcroft
& Ullman 1979) todistetaan, että "- - the class of languages accepted by
finite automata is precisely the class of languages describable by
regular expressions.", mutta ei mainita mitään mistään Kleenen
lauseesta.
--
Sami
Jukka Kohonen
>Kalle Olavi Niemitalo <k...@iki.fi> wrote:
>> Sami Silvennoinen <sami.sil...@tut.fi> kirjoitti:
>> > Kleenen lause: Säännölliset kielet ovat tarkalleen kaikki äärellisten
>> > automaattien tunnistamat kielet.
>
>> Mikäs tämä "Kleenen lause" on englanniksi?
>
>Kaiketi se on "Kleene's Theorem", mutta nimitys ei näytä olevan
>mitenkään vakiintunut (ei löydy Mathworldistä eikä Wikipediasta).
Ei ehkä noista löydy, mutta kyllä nimitys on yleisesti käytössä.
Ks. esim. Google: "kleene's theorem" "regular expression"