Treść zadania Minimalny automat rozpoznający język LR = {w " {a, b, c} :
|w|a a" |w|b a" |w|c (mod 2)}.
Rozwiązanie Jest to język, w którym liczba liter a ma taką samą parzy-
stość jak liczba liter b, jak liczba liter c. Jeden z pierwszych pomysłów jaki się
nasuwa to zrobienie automatu ze stanami q000, q001, q010, q011, itd. Po wczytaniu
a do x w qxyz dodajemy 1 (mod 2), b i c podobnie. Jednak taki automat nie
będzie minimalny, co wyszło by przy dowodzeniu (niżej).
Stan q011 oznacza, że parzystość liczby wczytanych liter b i parzystość liczby
wczytanych liter c jest taka sama, inna niż parzystość liczby wczytanych liter
a. Można zauważyć, że ten stan jest tożsamy ze stanem q100 - parzystość liczby
wczytanych liter a jest inna niż ta dla b i c.
Minimalny automat to M = (Q, Ł, , q000, F ), gdzie:
" Q = {qxyz : x + y + z d" 1} = {q000, q001, q010, q100}
" Ł = {a, b, c}
" : Q Ł Q
(q000, a) = q100
(q001, a) = q010
(q010, a) = q001
(q100, a) = q000
(q000, b) = q010
(q001, b) = q100
(q010, b) = q000
(q100, b) = q001
(q000, c) = q001
(q001, c) = q000
(q010, c) = q100
(q100, c) = q010
" F = {q000}
Akceptujemy słowo, gdy parzystość liczby wczytanych liter a, b i c się zgadza.
Dowodzenie minimalności Aby udowodnić minimalność tego automatu
posłużymy się algorytmem z wykładu (i ćwiczeń). Robimy w nim tabelkę
ze stanami i oznaczamy (tutaj oznaczę symbolem X) pary stanów (qx, qy) "
1
(Q Q \ F ) *" (Q \ F Q), czyli pary takie, że pierwszy ze stanów należy do
stanów akceptujących, a drugie nie i odwrotnie. Tabelka jest symetryczna, więc
możemy zrobić tylko połowę (względem przekątnej).
q000 q001 q010 q100
q000 X X X
q001
q010
q100
Kolejnym krokiem jest oznaczenie par, do których możemy dojść jeśli zasto-
sujemy funkcję do obu stanów w parze z tym samym symbolem. Np. para
(q000, q001) po wczytaniu a przechodzi na q100 oraz q010, zatem możemy oznaczyć
parę (q010, q100) (bo symetria).
q000 q001 q010 q100
q000 X X X
q001
q010 X
q100
Następnie spójrzmy na parę (q000, q100). Gdy wczytamy b, dostaniemy parę
(q001, q010). A gdy z (q000, q010) wczytamy a, dostaniemy (q001, q100).
q000 q001 q010 q100
q000 X X X
q001 X X
q010 X
q100
W ten sposób oznaczyliśmy wszystkie możliwe pary. Zatem automat jest
minimalny. Gdyby się zdarzyło, że nijak nie można dojść do pewnej pary to (o
2
ile dobrze pamietam) oznacza to, że te dwa stany można skleić. Jak widać pary
tych samych stanów (na przekątnej) nie zostały oznaczone, bo algortym nam
pokazał, że są to te same stany, możemy je skleić.
3
Wyszukiwarka
Podobne podstrony:
t15 Egzamin praktyczny 2016 CZERWIECEgzamin Czerwiec E12PKC pytania na egzaminEgzamin 08 zbior zadan i pytanpatomorfologia pytania egzamin opisowydydaktyka egzamin sciagapytania rynek finansowy egzaminobsługa pojazdu EgzaminOEiM AiR Przykladowy Egzaminwięcej podobnych podstron