Mulla on tällainen lauseke: ab|a*_*a|b. Tämä täytyisi muuttaa deterministiseksi lausekkeeksi ja minimoida. Mitähän a*_*a tarkoittaa?
Tarkoittanet deterministiseksi automaatiksi?
Lausekkeen muoto on minusta erikoinen. Onko jossain nähtävillä alkuperäinen tehtävänanto?
Osa a*_*a voisi tarkoittaa: ensin mikä tahansa määrä a-merkkiä, sitten mikä tahansa määrä _-merkkiä, lopuksi yksi a-merkki.
Tehtävänanto oli seuraava: Construct a minimal deterministic finite automaton corresponding to the given regular expression
Alaviiva vastaa epsilonia eli tyhjää merkkijonoa
Epsilonin esiintyminen lausekkeen osana olisi melkoinen kompa, koska sillä ei ole merkitystä lopputuloksen kannalta. Toisin sanoen lauseke olisikin ab|a*a|b.
Ylipäätään tää minimoiminen on hieman hakusessa. Tosta ei nyt tullu mitään, joten skippasein sen. Toinen minimoimistehtävä olis tallainen.
# Initial state
q1
# Final states
q2
q5
q6
# Transitions
q1 a q2
q1 b q3
q2 a q4
q2 b q5
q3 a q6
q3 b q4
q4 a q4
q4 b q4
q5 a q4
q5 b q4
q6 a q4
q6 b q4
Kun oon piirtäny sen kuvan tästä, niin riittääkö että minimoidussa on vain reitit lopputiloihin?
Benu87 kirjoitti:
Kun oon piirtäny sen kuvan tästä, niin riittääkö että minimoidussa on vain reitit lopputiloihin?
En ymmärrä, mitä tarkoitat. Minimoitu automaatti on mahdollisimman pieni automaatti, joka kuitenkin hyväksyy (ja hylkää!) täsmälleen samat merkkijonot kuin alkuperäinen. Vähempi ei riitä.
Aihe on jo aika vanha, joten et voi enää vastata siihen.