TC Moduł 8

Minimalizacja liczby stanów automatu

---

Jak wiadomo automat $A=<S,V,Y,\delta ,\lambda >$, w którym zbiór $S$ stanów wewnętrznych $S$ ma liczność $|S|$ może być zrealizowany na co najmniej $p=[lo{g}_2|S|]$ przerzutnikach. Zatem każde zmniejszenie liczby stanów, ale takie, aby automat z punktu widzenia obserwatora zewnętrznego wykonywał taką samą pracę jest bardzo korzystne ze względu na złożoność (a tym samym koszt) jego realizacji. Proces redukowania liczby stanów automatu, ale w taki specjalny sposób, aby nie zmniejszyło to możliwości funkcjonalnych automatu nazywa się minimalizacją liczby stanów automatu. Przykład minimalizacji automatu podany jest na planszy. Automat opisany tablicą przejść wyjść z lewej strony planszy ma 6 stanów wewnętrznych, zatem wymaga do swojej realizacji 3 przerzutników. Automat ten można jednak zminimalizować (na razie nie wiadomo w jaki sposób) do postaci opisanej tablicą z prawej strony planszy. Zminimalizowany automat ma 3 stany, a więc do jego realizacji wystarczą tylko 2 przerzutniki.

---

Proces minimalizacji automatu polega na wyznaczaniu relacji zgodności na zbiorze stanów wewnętrznych $S$. Następnie dla tak wyznaczonych par zgodnych obliczane są Maksymalne Klasy Zgodności. W ostatnim etapie minimalizacji dokonuje się selekcji minimalnej liczby zbiorów zgodnych spełniających tzw. warunek pokrycia i zamknięcia.

---

Dwa stany wewnętrzne $S_i$, $S_j$ są zgodne, jeżeli dla każdego wejścia $v$ mają one niesprzeczne stany wyjść, a ich stany następne są takie same lub niesprzeczne. Dwa stany wewnętrzne $S_i$, $S_j$ są zgodne warunkowo, jeżeli ich stany wyjść są niesprzeczne oraz dla pewnego $v\in V$ para stanów następnych do $S_i$, $S_j$ (ozn. $S_k$, $S_l$): $(S_i,S_j)\ne (S_k,S_l)$ Stany $S_i$, $S_j$ są sprzeczne, jeżeli dla pewnego $v\in V$ ich stany wyjść są sprzeczne. Dla automatu podanego na planszy, którego stany wewnętrzne są oznaczone liczbami naturalnymi 1 do 6, para 2, 4 jest zgodna, para 1, 3 jest zgodna warunkowo, a para 5, 6 jest sprzeczna.

---

Ze względu na to, że para zgodna warunkowo może – po dalszej analizie – okazać się parą zgodną albo sprzeczną w obliczaniu wszystkich par zgodnych posługujemy się tzw. tablicą trójkątną.

---

Przykładowa tablica trójkątna dla automatu o 5 stanach ma 4 kolumny oznaczone 1 do 4 oraz 4 wiersze oznaczone (od góry) 2 do 5. W rezultacie uzyskujemy tablicę, której kratki wypełniamy symbolami $v$, gdy analizowana para jest zgodna, $x$, gdy dana para jest sprzeczna lub w kratce zapisujemy parę (lub pary) stanów następnych w przypadku zgodności warunkowej.

---

Sposób wypełnienia tablicy trójkątnej dla przykładowego automatu (jest to automat z planszy 2) wyjaśniamy na niniejszej planszy. Jak widać para 1, 2 jest zgodna, kratkę o współrzędnych 1, 2 wypełniamy znaczkiem $v$; para 1, 3 jest zgodna pod warunkiem zgodności pary 3, 6 i dlatego w odpowiedniej kratce wpisujemy 3, 6; z kolei para 1, 4 ma sprzeczne wyjścia, zatem wypełniamy ją symbolem $x$ itd.

---

Ogólnie: w tablicy trójkątnej należy wpisać wszystkie warunki oraz wykreślić klatki odpowiadające stanom o sprzecznych wyjściach. Następnie należy wykreślić wszystkie klatki, w których jako warunek (lub jeden z warunków) wpisana jest para $k,l$ odpowiadająca klatce $(k,l)$ wykreślonej na poprzednim etapie. Dla wszystkich nowo wykreślonych klatek należy sprawdzić, czy odpowiadające im pary stanów występują w niewykreślonych klatkach jako warunki. Czynność wykreślania klatek prowadzi się aż do uzyskania sytuacji, gdy wszystkie pary określające warunki odpowiadają klatkom niewykreślonym. W tak uzyskanej tablicy wszystkie klatki niewykreślone, bez względu na ich zawartość, odpowiadają parom stanów zgodnych

---

Dysponując zbiorem wszystkich par zgodnych przystępujemy do wyznaczenia rodziny Maksymalnych Klas Zgodności. Dla potrzeb obliczania rodziny MKZ możemy stosować jedną z trzech metod omówionych w module 6.

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---