minimalizacja automatów niezupełnych

1 Minimalizacja automatów niezupełnych . Automatem zredukowanym nazywamy automat, który jest zdolny do wykonywania tej samej pracy, którą może wykonać dany automat, przy czym ma on mniejszą liczbę stanów. Automat  Mmin  nazywamy  automatem minimalnym  odpowiadającym automatowi  M , jeśli nie istnieje automat zredukowany o mniejszej liczbie stanów. Automat niezupełny to taki, który ma nieokreślone niektóre stany lub/i wyjścia (w tabeli występują kreski „ - „).Automat niezupełny może mieć kilka automatów minimalnych lub może nie mieć żadnego, (czyli sam jest swoim automatem minimalnym). Wyznaczenie automatu minimalnego odbywa się w procesie minimalizacji. Przykład : Stany nast ępne Wyj ścia Stan obecny 0 1 0 1 1 3 2 0 0 2 - 2 - 1 3 - 4 - 1 4 7 5 1 1 5 6 - 1 - 6 - - 0 0 7 6 6 1 1 1 .Konstruujemy tablicę trójkątną ułatwiającą porównanie stanów: 2 3 4 5 6 7 1 2 3 4 5 6 2 . Porównujemy stany wpisując do tabeli  x  w kratki, które odpowiadają stanom, które nie mogą być połączone gdyż mają różne wyjścia.(np. stan 1 ma na wyjściu 00 a stan 2 -1,czyli nie można ich połączyć) 2 X 3 X 4 X 5 X 6 X X X X 7 X X 1 2 3 4 5 6 3 .Wpisujemy  V  w kratki dla których wyjścia są identyczne, czyli: x ∀ jeśli λ(x,p) i λ(x,q) są określone, to λ(x,p) = λ(x,q) ; oraz: a)stany są identyczne b)jeden ze stanów jest nieokreślony, albo para stanów następnych jest taka sama jak para stanów obecnych 2 2 X 3 X 4 X 5 X V V 6 V X X X X 7 X V X 1 2 3 4 5 6 4 .W pozostałe kratki wpisujemy pary stanów następnych, jeśli porównywane stany mają te same wyjścia (wypisujemy pary stanów, które są warunkiem połączenia porównywanych stanów) 2 X 3 X (2,4) 4 X (2,5) (4,5) 5 X V V (6,7) 6 V X X X X 7 X (2,6) (4,6) (5,6)(7,6) V X 1 2 3 4 5 6 5. Sprawdzamy kratki w których wypisane były stany warunkowe. Jeżeli któryś z warunków jest nie spełniony (jego kratka jest oznaczona  X -em) to sprawdzane pole również oznaczamy przez  X . Jeżeli żaden z warunków nie jest niespełniony to kratkę oznaczamy  V . 2 X 3 X (2,4) V 4 X (2,5) V (4,5) V 5 X V V (6,7)  X 6 V X X X X 7 X (2,6) X (4,6) X (5,6)(7,6) X V X 1 2 3 4 5 6 Kratki oznaczone V odpowiadają parom należącym do relacji  niesprzeczności stanów ~ ; tzn. że: 1. Nie istnieje takie słowo dla którego litery wyjściowe końcowe są określone i różne od ... zobacz całą notatkę