Keskustelu: Yleinen keskustelu: Apua tietojenkäsittelyteorian tehtävään

Eli ongelma on seuraavanlainen: pitäis muodostaa säännöllinen lauseke, joka kuvaa seuraavan kielen: { w in {a,b}* | w contains the substring aa or bb (or both) }.

Havainnollistetaan tehtävää: esimerkiksi lauseke ab* kuvaa kielen {a, ab, abb, abbb,...}.

Eli pitäs muodostaa lauseke joka kuvaa kaikki mahdolliset aakkoston {a,b} merkkijonot, joista jokainen sisältää osajonot aa tai bb tai molemmat.

Idea: merkkijonon alussa saa olla mitä tahansa, sitten jossain vaiheessa pitää tulla aa tai bb ja sitten lopussa saa taas olla mitä tahansa.

Okei, oiskohan tää oikein: (a|b)*(aa)|(bb)(a|b)*

| tarkoittaa yhdistettä (unionia)
* on Kleenen tähti

Hyvältä näyttää, mutta muuta keskiosa muotoon (aa|bb), jotta yhdiste ei ulotu liian pitkälle.

Kiitos nopeista vastauksista!

Seuraava ongelma:
{ w in {0,1}* | the number of 1's in w is a multiple of 2 or 3 (possibly zero) }

Ajattelin jotain tähän tyyliin: (0|(11|111))* mutta siinä kaikki ykköset on peräkkäin, ne pitäis saada olemaan missä järjestyksessä tahansa...

Talvella juuri koulussa näitä vastaavia pyöriteltiin. En ole ihan varma, mutta veikkaisin, että jotenkin näin: (0*((10*1)|(10*10*1))0*)*

Yllä olevissa lausekkeissa on vikana, että ykkösiä voi tulla esim. viisi kappaletta.

Minä tekisin ensin erikseen parillisen ja kolmella jaollisen ykkösten määrän tunnistavat lausekkeet ja lopuksi yhdistäisin ne.

Oiskohan tässä järkeä: (0*10*10*)*|(0*10*10*10*)*|0*

Ainakin minusta lauseke on nyt oikein.

On oikein, vaikkakin tuossa on myös monta ylimääräistä nollaa.
0*((10*1)*|(10*10*1)*)0*

Seuraava pähkinä: {w in {0,1}* | w loppuu eri merkkiin kuin alkaa}

Ajattelin jotain tämmöstä: 0(0|1)*1|1(0|1)*0 mutta kun tuossa on unioni niin myös kummatkin osalauseet voi tapahtua, joka ei olisi sallittua.

Minusta menisi näin:
(0(0|1)*1)* | (1(0|1)*0)*

Ulommaiset *:t sen takia, että myös tyhjä jono mahdollinen.

Palvy kirjoitti:

kummatkin osalauseet voi tapahtua, joka ei olisi sallittua.

Eihän se ole mahdollista. Ei se voi samaan aikaan alkaa 1:llä ja 0:lla.

TsaTsaTsaa kirjoitti:

Ulommaiset *:t sen takia, että myös tyhjä jono mahdollinen.

Loppuuko se silloin sinusta eri merkkiin kuin alkaa? Siinä vasta pulma...

Metabolix kirjoitti:

TsaTsaTsaa kirjoitti:

Ulommaiset *:t sen takia, että myös tyhjä jono mahdollinen.

Loppuuko se silloin sinusta eri merkkiin kuin alkaa? Siinä vasta pulma...

Tehtävänannon tietysti voi tulkita molemmilla tavoilla, mutta minä tulkitsisin sen niin, että tyhjä hyväksytään tuohon, koska jos sitä ei hyväksyttäisi, olisi tehtävänannossa selkeyden vuoksi voinut olla {w in {0,1}+ | ...}

MUOKS: Jos nyt ihan oikein muistan että tuo + tarkoittaa että vähintään yksi merkki.

Lisää pähkäiltävää. Pitäis muodostaa kielioppi, joka tuottaa seuraavanlaisen kielen: { w in {a,b}* | w contains "aba" as a substring}. Tietysti vois kokeilla muodostaa ensin äärellisen automaatin, joka tunnistaa kyseisen kielen...

No eikö tuo ole entistä helpompi tehtävä?
(a|b)*(aba)(a|b)*

Nyt tarvitaan (yhteydetön) kielioppi, ei säännöllinen lauseke :)

Jotenkin näin?

<sana> ::= <muu> "aba" <muu>
<muu> ::= "" | "a" <muu> | "b" <muu>

Tai vähän eri merkinnöin:

S -> XabaX
X -> aX | bX | ε

Tässä ε tarkoittaa tyhjää merkkijonoa.

Jeps jeps, samaan päädyin kun tein sen automaatin muodostamisen kautta..

Tarkastellaanpas aakkoston {a,b} palindromien muodostamaa
kieltä PAL = {w in {a,b}* | w = w^R}. Pitäis laatia kielen PAL tuottava yhteydetön kielioppi.

Itsellä ei tule mieleen vielä muuta kuin että eka merkki täytyy olla sama kuin vika merkki ja toka sama kuin tokavika jne. Jos joku keksisi vaikka vinkiksi, että miten tuon esittäisi säännöllisenä lausekkeena... älkää kertoko vielä kielioppia :)

Kielioppi syntyi alle minuutissa, mutta säännöllistä lauseketta en ainakaan tähän hätään osaa heittää (tuskin tuollaista onkaan). Saanet kieliopin aikaan, kun annan vihjeeksi, että yksinkertaisimmillaan palindromi voi olla tyhjä teksti tai yksittäinen merkki ja että pitemmässä palindromissa on aina molemmissa päissä sama merkki ja niiden välissä lyhyempi palindromi.

Kieli PAL ei ole säännöllinen. Siten ei ole säännöllistä lausekettakaan, joka sen tuottaisi.

Pekka Karjalainen kirjoitti:

Kieli PAL ei ole säännöllinen. Siten ei ole säännöllistä lausekettakaan, joka sen tuottaisi.

Tuota vähän epäilinkin...

Jos se kielioppi alkais esim. näin, niin olenko oikeilla jäljillä:

S -> XaX | XbX | YaY | YbY | e
.
.
.

Mitä nämä X ja Y ovat, mihin niitä tarvitaan? Millä tarkistat, että reunoissa olevat kaksi X:ää ovat keskenään samanlaiset?

Aloita mainitsemistani helpoista tapauksista ja lisää sitten se jälkimmäinen tapaus (tai siis kaksi tapausta, a:lla ja b:llä).

Ajattelin että:

X -> a | jotain
Y -> b | jotain

mutta ei toimi tuo oikein pidemmälle...

Jotenki näin sitten:

S -> e | a | b | aSa | bSb

Juuri noin. :)

S -> (S) | S, S | a

Keksiskö joku, miten tuosta kieliopista saa sellaisen lauseen, jolla on vähintään kaksi erilaista jäsennyspuuta?

Kelpaako "a, a, a"?

       S                  S
     / | \              / | \
    /  |  \            /  |  \
   /   |   \          /   |   \
  S    ,    S        S    ,    S
 /|­\   |    |        |­    |   /|\
S , S  |    |        |    |  S , S
| | |  |    |        |    |  | | |
a , a  ,    a        a    ,  a , a

No toihan oliki helppo.. hävettää ihan kun en ite keksiny :)

{w in {0,1}* | w ei sisällä osajonoa 010}

Säännöllinen lauseke tuosta?

Ajattelin jotain tämmöstä: 0* | (1* | (0*111*))*

Ei toimi, koska tuosta ei saa esim. jonoa 01.

Vinkki aluksi: Sanan keskiosa on sanallisesti kuvattuna sellainen, että siinä voi olla mielivaltaisen pitkiä nollien jonoja, mutta aina kun siinä esiintyy nollan jälkeinen ykkönen, tätä ykköstä pitää seurata toinen ykkönen. Pitää siis olla kaksi tai enemmän ykköstä peräkkäin. Tämän voi sanoa 111* kuten Palvy yllä, tai jos +-merkintä on käytössä, 11+ .

Vain sanan alussa tai lopussa voi olla yksinäinen ykkönen, koska siellä se ei ole nollien ympäröimä, mikä säännössä kielletään.

Ratkaisun rakentaminen pitäisi onnistua helposti, jos sen aloittaa säännöllisellä lausekkeella, joka kuvaa sanojen keskiosia ym. tavalla. Sitten pitää miettiä vain sanan alku & loppu.

1*(0* | 0*111*)*1*

Pari tähteä lienee turhia:
1*(0|0111*)*1*

EDIT: Vai toimisiko jopa ilman tuota toista nollaakin? 1*(0|111*)*1*

Minulla oli melkein samanlainen ratkaisu mielessä. Tuo TsaTsaTsaan jälkimmäisenä esittämä näyttää minusta nyt selkeimmältä tavalta.

Se mitä kohti johdattelin oli minulla näin:

1*(0*111*)*0*1*

Tällainenkin tuli nyt mieleen:

1*(0|11|111)*1*

En huomaa ainakaan, että yhdessäkään esitetyssä ratkaisussa olisi virhe.