Citat:
Ursprungligen postat av Alligator_Gunde
Har en uppgift där man har en automat som känner igen ett reguljärt språk.
Vi ska skriva upp ett reguljärt språk för uttrycket. Det ska skrivas om till enklare form som ändå betyder samma sak och sedan ska uttrycket ritas och den ska göra samma sak.
http://tinypic.com/view.php?pic=izm2ro&s=6
Det naiva sättet är ju att skriva (0 u 1+0)(0 u 1+(01+)*0)(0 u 1)* genom att bara följa vägarna man kan ta.
Men varför inte minimera automaten direkt och skriva ner detta språk? Detta föreslår jag att vi gör genom särskiljandealgoritmen:
Döp om "s_i" till "i".
Generation 1: {0, 1, 2, 4, 5} är icketerminerande, medan {3} är terminerande.
Generation 2: {0, 1, 4} driver in i {0, 1, 2, 4, 5} via 0, medan {2, 5} driver in i {3}. {3} är ju bara en nod, så vi behöver inte kolla.
Generation 3: {0, 1} driver via 0 in i {0, 1, 4} medan {4} driver in i {2, 5}
Generation 4: Vi ser att {0, 1} eller {2, 5} inte särskiljer tecken
Så vi kan rita en DFA utifrån noderna {0, 1}, {2, 5}, {3} och {4} genom att börja i {0, 1} och beskriva varje teckens drivning. Vi erhåller en automat då (som är minimal)
Se bild:
http://i50.tinypic.com/m8hcec.jpg