Keskustelu: Yleinen keskustelu: säännöllistä lauseketta

Moro

Hakusessa on vain säännöllinen lauseke, mikä määrittelis aakkoston {a,b} kielen. Ja tähän kieleen kuuluis kaikki ne lauseet, joissa symbolijono/merkkijono ab esiintyy tasan kaksi kertaa.

Eka mulla oli mielessä (a,b)^2. siitähän tulisi (abab).
Sitte mä ajattelin b*(abab)^1b* eli tässä olis 0 tai enemmän b:ta alussa, sitten abab ja sitten 0 tai enemmän b:ta. Mutta olisko tuo eka kuvaukseni kaltainen?

Voisit mielellään joko selittää käyttämäsi merkintätavat tai käyttää merkintöjä, joita ohjelmoinnissa yleensä käytetään (ks. SL-haasteen ohjeet). Oletan, että pilkku on kirjoitusvirhe ja että ^N tarkoittaa toistoa N kertaa.

Kumpikaan lausekkeistasi ei ole kuvauksesi kaltainen, koska kumpikaan ei hyväksy esimerkiksi merkkijonoa babbaaba. Varmaan olisit voinut tällaisen esimerkin itsekin keksiä. Usein säännöllisen lausekkeen suunnittelu kannattaakin aloittaa muutamasta esimerkistä, joihin voi sitten testata lausekkeitaan.

Moi. Pilkku ei ole kirjoitusvirhe. Mutta kyllä, ^n tarkoittaa toistoa n kertaa.
ja * toistoa 0 tai useamman kerran.
Tämä ei ole oikeastaan koodausta, mutta jos joku kuitenkin valaisisi asiassa.

Hyvä huomio, esim. babbaaba pitäisi sitten tulla ja nyt kumpikaan yritykseni ei sitä tuota. Tämä taitaakin vaatia pidemmän lausekkeen. Mutta kokeillaan vielä:

b*(a)*(abab)^1b*(a)*

Tähän voi olla monta eri ratkaisua. Tuo on paras mitä keksin.

Pitäisikö lausekkeen hyväksyä merkkijono abaab? Tuo lauseke ei taida hyväksyä sitä.

Normaalia säännöllisten lausekkeiden syntaksia käyttäen toimisi kai

b*(a+b+){2}a*

Kyllä tuo merkkijono abaab käy, koska siinähän ab esiintyy kaksi kertaa.

Mutta "Normaalia säännöllisten lausekkeiden syntaksia..." - kyllä, juuri sillä!
Eli tässä b*(a+b+){2}a* on siis

b 0 tai useamman kerran (a+b+) potenssiin 2 ja sitten a 0 tai useamman kerran.

Mutta tuo + tarkoittaa ainakin kerran. Pitäisi olla todellakin niin, että tähän kieleen kuuluu kaikki ne lauseet, joissa merkkijono ab esiintyy täsmälleen kahdesti. Ja tämän mukaanhan ab ei tarvitsisi olla peräkkäin, vaan siten, että ab esiintyy kaksi kertaa.

En ole ihan varma, että toteuttaako tuo b*(a+b+){2}a* vaatimukseni?

slalomiaBe kirjoitti:

En ole ihan varma, että toteuttaako tuo b*(a+b+){2}a* vaatimukseni?

Kokeile. Näin äkkiä päässä ajateltuna tuo Grezin lause pitäisi toimia ihan oikein. Jos sen ei ole pakko olla juuri säännöllinen lause, niin esim. php:llä saisit toteutettua sen näinkin selkeästi ja yksinkertaisesti:

if (substr_count($lause, 'ab') == 2)

Tai pythonilla:

if lause.count('ab') == 2:

php ja python ovat mulle aika vieraita. Haluan sen säännöllisenä lausekkeena. Mutta jos kukaan en enää esitä muuta ratkaisua, niin sitten se on tuo Grezin
b*(a+b+)^2 a*

Eli keskellä oleva (a+b+) potenssiin 2. Kyllä tuo alkaa tuntua sopivalta.

slalomiaBe kirjoitti:

Kyllä tuo alkaa tuntua sopivalta.

Ei lausekkeita tehdä sen mukaan, mikä "tuntuu sopivalta". Lausekkeet voi (ja usein pitääkin) täysin järkiperäisesti vahvistaa oikeiksi (tai vääriksi). Eikö tämä ole tullut opiskelusi yhteydessä esiin?

Esimerkiksi tässä tapauksessa lausekkeen voi muodostaa loogisesti näin:

1. Tarvitaan kaksi ab:tä, joiden välissä voi olla jotain muuta. Lauseke on siis muotoa (X)ab(X)ab(X), missä X on jokin lauseke, joka hyväksyy merkkijonot, joihin ei sisälly osajono ab.
2. Selvästikään X ei voi sisältää a:ta, jonka jälkeen tulisi b, joten kaikki mahdolliset b:t ovat sen alussa ja a:t sen lopussa. Tämän ehdon täyttää lauseke b*a*.
3. Koko ratkaisu on näin ollen (b*a*)(ab)(b*a*)(ab)(b*a*) eli ilman sulkuja b*a*abb*a*abb*a*.
4. Koska a*a ja aa* tarkoittavat samaa kuin a+, lauseke voidaan kirjoittaa lyhyemmin muodossa b*a+b+a+b+a*.
5. Nähdään, että a+b+ toistuu tässä kaksi kertaa, eli tarvittaessa lauseke voidaan muuttaa muotoon b*(a+b+){2}a*, mutta tämä ei lyhennä lauseketta.

slalomiaBe kirjoitti:

Eli keskellä oleva (a+b+) potenssiin 2.

Potenssi on tässä aika outo ilmaus. Silloinhan lausekkeen keskiosa olisi (a+b+) kertaa (a+b+), vaikka oikeasti keskiosa on 2 kertaa (a+b+).

slalomiaBe kirjoitti:

Pilkku ei ole kirjoitusvirhe.

Mitä (a,b)^2 sitten tarkoittaa? Selityksesi perusteella se tarkoittaisi samaa kuin (ab)^2, mutta jos pilkulla on jokin merkitys, näin ei varmaan voi olla.

slalomiaBe kirjoitti:

Tämä ei ole oikeastaan koodausta,

Se ei muuta miksikään sitä, että merkinnöistä pitää jotenkin sopia. Ohjelmoinnissa yleiset merkinnät ovat sikäli hyviä, että niitä lähes kaikki ovat tottuneet käyttämään, mutta toki voit käyttää muitakin, kunhan selität ne.

Ok, ei tietenkään sopivalta - vaan tarkoitin, että itsekin uskon, että Grezin ehdotus on täysin oikein.

Kyllä tuo "(a+b+) kertaa (a+b+)" on oikein.

Eli säännöllinen lauseke, mikä määrittelee aakkoston {a,b} kielen. Ja tähän kieleen kuuluu kaikki ne lauseet, joissa symbolijono/merkkijono ab esiintyy tasan kaksi kertaa on tällöin

b*(a+b+)(a+b+)a*

slalomiaBe kirjoitti:

Kyllä tuo "(a+b+) kertaa (a+b+)" on oikein.

Lauseke varmasti onkin oikein, juurihan itsekin perustelin sen. Pointtini oli, että ei ole mielekästä väittää, että lausekkeessa on "(a+b+) kertaa (a+b+)", koska lausekkeessa ei taatusti ole tällaista kertolaskua – vai paljonko laskun "(a+b+) kertaa (a+b+)" tulos sinusta on? Ethän varmaan väitä myöskään, että lauseke (a)(b)(c)(d) tarkoittaa "a kertaa b kertaa c kertaa d" tai että lauseke a+b tarkoittaa "a plus b". Jos säännöllinen lauseke pitää pukea sanoiksi, ymmärrettävämpää on selittää, mitä se tekee tai millaisen kielen se kuvaa.

Tosiaan kannattaa huomata, että on monia erilaisia tapoja merkitä säännöllisiä lausekkeita. Ohjelmoinnissa käytettyä "tavallista" tapaa näkee harvoin alan kirjallisuudessa.

"Yhteenlasku" ja "kertolasku" ovat järkeviä tulkintoja, kunhan ne kohdistuvat joukkoihin. Säännölliset lausekkeet voidaan ajatella joukoiksi, koska jokainen lauseke kuvaa jonkin joukon. Yhteenlasku on joukkojen yhteenlasku, jossa mukaan tulevat kaikki alkiot joukoista. Kertolasku muistuttaa joukkojen karteesista tuloa. Siinä merkkijonon alkuosa valitaan vasemmasta joukosta ja loppuosa valitaan oikeasta joukosta.

Esimerkiksi lauseke a+b+c vastaa joukkoa {a, b, c} ja lauseke (a+b)(c+d) vastaa joukkojen {a, b} ja {c, d} kertolaskua eli joukkoa {ac, ad, bc, bd}. Tietenkin on sekoittavaa, että "tavallisessa" merkintätavassa + tarkoittaa toistoa eli sen merkitys on täysin toinen.

Antti Laaksonen kirjoitti:

Esimerkiksi lauseke a+b+c vastaa joukkoa {a, b, c}

Mutta jos noudatetaan tuota tulkintaa merkinnöistä, lauseke b*(a+b+)^2a* ei ole oikea ratkaisu alussa esitettyyn ongelmaan, vaan se aukeaakin nähdäkseni muotoon b*(a+b+aa+bb+ab+ba+)a* eli vielä pidemmin b*aa*+b*ba*+b*aaa*+b*bba*+b*aba*+b*baa*+b*a*, eikä näistä vaihtoehdoista yhdessäkään ole kahta ab:tä.

Jotain yhtenäistä logiikkaa pitäisi nyt noudattaa edes yhden viestin ajan.

Mielestäni "kertolasku" on aika huono analogia säännöllisten lausekkeiden peräkkäisille joukoille ihan sen takia, että kertolaskussa tekijöiden paikka on vaihdettavissa.

Kuitenkin säännöllisissä lausekkeissa (a)(b) tarkoittaa ihan eri asiaa kuin (b)(a)

Ja kun kerran kertolasku ei toimi, niin en mielelläni käyttäisi sitten potenssiakaan, vaikkakin toki potenssissa kantaluku on sama eikä sinänsä ole mitään merkitystä vaikka sitä vaihtaisikin.

Grez kirjoitti:

Mielestäni "kertolasku" on aika huono analogia säännöllisten lausekkeiden peräkkäisille joukoille ihan sen takia, että kertolaskussa tekijöiden paikka on vaihdettavissa.

Vaihdannaisuus ei päde yleisesti kertolaskussa. Esimerkiksi matriisien kertolaskussa AB ei ole välttämättä sama kuin BA.