Keskustelu: Yleinen keskustelu: Säännöllisen lausekkeen minimointi

Osaisiko kukaan auttaa säännöllisen lausekkeen minimoimisessa? Olisi annettu seuraava lauseke: a(a_*|_*|_)_*|(b) . Itse ymmärrän tämän seuraavasti: ensiksi on merkki 'a', jonka jälkeen tulee 'a' ja tyhjiä merkkijonoja TAI tyhjiä merkkijonoja TAI tyhjä merkkijono ja lopuksi joko tyhjiä merkkijonoja TAI 'b'.
Minimoituna a(a|ab|b|_), mutta tämä ei ole oikein. Missä mahtaa mennä pieleen?

Minusta looginen tulkinta olisi, että merkkijono on muotoa a(a_*|_*|_)_* tai muotoa (b). Tällöin vastaava lyhyempi lauseke olisi a(a|_)|b.

Tässä siis ilmeisesti _ tarkoittaa tyhjää merkkijonoa.

Eli tarkistin hyväksyy seuraavat merkkijonot:

aa     b
a b
aab

ja hylkää seuraavat:

a ba
aabb
 a  ab

Antin lausekkeesta vielä. Pitääkö sulkujen sisällä tulla vielä toistomerkinnät merkkien perään, jotta tunnistus olisi vastaava kuin alkuperäinen?

Kuinka tuosta mahtaa saada sitten deterministisen automaatin? Se kun ei salli epsilon-siirtymää(tyhjää merkkijonoa)?

Eli Teuron mallin mukaan tekisin näin. Mutta tämä ei siis ole oikea vastaus. Eli pitäisi siis saada noi tyhjät merkit hävitettyä jotenkin.

q1 a q2
q2 a q4
q2 _ q3
q3 b q5
q4 _ q4
q4 b q5
(q1 initial, q5 final)

Tuossa tapauksessa molemmat epsilon-siirtymät ovat melko turhia. Tilasta 2 voisi siirtyä suoraan tilaan 5 merkillä b. Tilassa 4 taas ei ole hyötyä tarjota epsilon-siirtymää samaan tilaan 4.

Teuro kirjoitti:

Pitääkö sulkujen sisällä tulla vielä toistomerkinnät merkkien perään, jotta tunnistus olisi vastaava kuin alkuperäinen?

Tyhjä merkkijono tarkoittaa yleensä näissä puheissa nimenomaan merkkijonoa, jonka pituus on nolla merkkiä. Niinpä toistomerkinnällä ei ole merkitystä. Jos se kuitenkin tarkoittaisi välilyöntiä (kuten ilmeisesti tulkitsit), toistomerkintä olisi toki tarpeen.

Höh. Poistin tyhjät merkkijonot eli jäi vain:

q1 a q2
q2 a q4
q4 b q5
q2 b q5
(q1 initial, q5 final)

Palautteena tuli että väärä määrä tiloja, eikä hyväksy tyhjää merkkijonoa. Mutta kuinka voidaan hyväksyä tyhjämerkkijono, jos tarkoitus tehdä DFA?
(tehtävänanto: Construct a minimal deterministic finite automaton corresponding to the given regular expression.)

Jos DFA:n alkutila on myös lopputila, se hyväksyy tyhjän merkkijonon.

Onko työn alla edelleen lauseke a(a_*|_*|_)_*|(b)? En ymmärrä, millä tulkinnalla se hyväksyisi tyhjän merkkijonon.

Metabolix kirjoitti:

Jos se kuitenkin tarkoittaisi välilyöntiä (kuten ilmeisesti tulkitsit), toistomerkintä olisi toki tarpeen.

Joo huomaa etten ole juuri näitä tutkinut ja luulin todella tyhjän olevan välilyönti.

Alkuperäinen lauseke a(a_*|_*|_)_*|(b) on siis edelleen työn alla.
Mutta jos alkutilan laittaa myös lopputilaksi niin eihän se silloin noudata annettua säännöllistä lauseketta, sillä ensinhän pitää joka tapauksessa tulla 'a'.

Saamani palaute kokonaisuudessaan oli siis seuraava: 'Given automaton has a different number of states than the minimal one. Also, given automaton doesn't accept the empty string.'

Benu87 kirjoitti:

Mutta jos alkutilan laittaa myös lopputilaksi niin eihän se silloin noudata annettua säännöllistä lauseketta, sillä ensinhän pitää joka tapauksessa tulla 'a'.

Juuri tämän vuoksi en ymmärrä, miksi automaatin pitäisi hyväksyä tyhjä merkkijono.

Mistä järjestelmästä saat noita palautteita? Pystynkö minä käyttämään järjestelmää?

Tämä on on luultavasti koulun oma systeemi - Stratum. Tämä generoi jokaiselle opiskelijalle omat tehtävät.

Mutta tehtävästä: Kolmen tilan kokoinen kaavio olisi haettu koko, mutta eriasia kuinka sen saa rakennettua oikein. Eli pitäisi kai saada tehtyä 'tyhjä', 'a', 'aa' ja 'ab' merkkijonot.

Kokeilin nyt tällaista:
#Initial state:
q1
#Final states:
q3
q1
q2
#Transitions:
q1 a q2
q2 b q3
q2 a q1

Mutta ei. Tilojen määrä on oikein, mutta siirtymät eivät, eikä myöskään salli 'aba'. Kuinka ihmeessä tuo voi edes sallia merkkijonon jossa on 'a' b:n jälkeen. Taitaa olla alkuperäisen lausekkeen tulkinta hieman pielessä.

a(a_*|_*|_)_*|(b) on nähdäkseni yksinkertaistettuna aa?_*|b

Eli a_*, aa_* tai b. Hyväksyttäviä ovat siten mm. a, aa, b, a__, aa_ ja a____.

Benu87 kirjoitti:

ensinhän pitää joka tapauksessa tulla 'a'

Ei, jos on pelkkä b.

Viime kerralla kun yritin niin sain seuraavan palautteen:
"Given automaton has the same number of states, but different transitions than the minimal one. Also, given automaton doesn't accept string 'aba'."

Chimanin versiokaan ei hyväksy tätä merkkijonoa. Eli jollain menetelmällä tuo automaatti haluaa että a voisi olla myös b:een jälkeen.

Täytyy pistää proffalle palautetta että tätä on mahdoton ratkaista. Tenttiin pääsy kun on vain tästä tehtävästä kiinni. Nimittäin pitää tehdä kaikki esitehtävät ja tämä on ainut mikä on jäänyt roikkumaan.

Onko _ sitten mikä tahansa merkki tuossa tehtävänannossa? Tällöin yksinkertaistettu muoto olisi: a_*|b

'_' on tyhjä merkkijono eli epsilon. Tarkistin ohjeista.

Eihän tuo lauseke voi mitenkään hyväksyä merkkijonoa "aba", koska lausekkeen ainoa b on aivan sen lopussa.

Tarkista nyt vielä sadannen kerran, että olet kopioinut tehtävänannossa olevan lausekkeen oikein ja että yrität lähettää vastausta oikeaan tehtävään. Jos kaikki on varmasti kunnossa, kannattanee seuraavaksi kysyä järjestelmän tekijältä, onko tehtävässä tai sen tarkistuksessa jokin virhe.

# Assignment:

a(a_*|_*|_)_*|(b)

Ja viimeinen palaute:
Given automaton has the same number of states, but different transitions than the minimal one.
Also, given automaton doesn't accept string 'aba'.

Kysyn huomenna asiasta ylläpidolta.

Nyt sain uuden lausekkeen, joka oli sitten helppo ratkaista. Kiitoksia kuitenkin.