Voisiko joku auttaa alla olevan säännöllisen kielen suunnittelussa?
Eli tehtävä olisi:
{w in {a,b}* | w contains equally many a's and b's (mod 3) }
Eli tehtävä olisi:
{w in {a,b}* | w contains equally many a's and b's (mod 3) }
Regular expressions and automata
.......
6400
0Äänestä
Muut lukivat myös
Odottaa vastausta
Näihin keskusteluihin ei ole vielä vastattu. Ole ensimmäinen.
Vastaukset 6
Vanhimmat
Tjaa, olisko
A0 = {}
A1 = { ab, ba }
A2 = { aabb, abab, abba, baab, baba, bbaa }
A3 = { kaikki merkkijonot missä 3 a:ta ja b:tä }
jolloin merkkijonot ovat muotoa
w in (A0 | A1 | A2) A3*
Sen jälkeen vielä todistus vastaoletukseen perustuen.
Esittämässäsi kielessä ei voi olla alussa neljää a-merkkiä peräkkäin, koska se alkaa jollain joukkojen A0-A3 jäsenestä. Kuitenkin kieleen w (alkup. viestissä) kuuluu myös sana aaaabbbb, koska a- ja b-merkkien määrä on 1 mod 3 kumpaisenkin.
Lisäksi A0:n pitäisi kai olla {a,b}.
A0 = {} tietenkin. Viimeisen kommenttini voitte unohtaa.
Vähän hankala selittää sanallisesti kuva, joka olisi helppo piirtää. Yritän parhaani.
Miten siis piirtää tilakone? Ajattelen näin.
Meillä on 3x3 erilaista mahdollista tilaa. A-merkkien määrä voi olla 0,1 tai 2 mod 3 ja vastaavasti B-merkkien määrä voi olla 0,1 tai 2 mod 3. Merkitään näitä pareja (x,y), missä x ja y ovat molemmat väliltä 0-2 ja x on a-merkkien määrä, sekä y b-merkkien. Pareja on siis yhteensä yhdeksän erilaista.
Alkutilanne on pari (0,0) ja se on myös yksi lopputiloista, koska parin luvut ovat samat. Siitä lähtee kaksi nuolta. Jos syöte on a, siirrytään tilaan (1,0), jossa a-merkkien määrä on 1 mod 3. B taas vie tilaan (0,1).
Jokaisesta parista (t,s) pääsee siis tilaan (t 1,s) tai (t,s 1), missä lasku on mod 3. Ja tilat (0,0), (1,1), (2,2) ovat lopputiloja. Tämä on varmasti helppo piirtää, jos selitykseni oli tarpeeksi hyvä.
Tämä automaatti siis hyväksyy määritelmän kielen. Nyt se pitäisi muuttaa regexpiksi. Siihen on olemassa mekaaninen menettely. Enpä nyt kuitenkaan osaa sitä käydä läpi noin vain.
Automaatin olemassaolo ainakin osoittaa, että kieli on säännöllinen. Tietenkään tämä ei ole formaali todistus vielä.
Hei!
tiedän kyllä minkälainen tuon automaatin pitäisi olla, mutta siitä tuntuu olevan aika vaikea muodostaa tuota regular expressionia.
Tässä tehtävässä ei tarvitse tehdä todistuksia.
Tämä ei ollut hirveän helppo tehtävä, ja ei oikeastaan kuulu matematiikkaan, vaan tietojenkäsittelyteoriaan. Tämä automaatti on kolmitilainen, joista ensimmäinen on hyväksyvä tila. Toiseen tilaan päästään a:lla ja siitä pois b:llä. Kolmannesta tilasta päästään toiseen tilaan a:lla ja sinne päästään toisesta tilasta a:lla. Ekasta tilasta päästään kolmanteen tilaan B:llä ja sieltä pois ensimmäiseen a:lla. Automaatissa voidaan kiertää äärettömän määrän kierroksia, kunhan päästään hyväksyvään alkutilaan.
Kiitos kuitenkin avuliaisuudesta auttamisen suhteen.