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.

---

W przypadku tak prostego automatu wystarczy metoda bezpośrednia. Stosowne obliczenia pokazane są na planszy. Najpierw z par tworzymy trójki: 1,2,3; 1,2,5; 1,3,5; 2,3,5. Z uzyskanych czterech trójek powstaje zbiór czteroelementowy: 1, 2, 3, 5. W celu uzyskania wszystkich zbiorów MKZ uzupełniamy tę „czwórkę” tymi parami zgodnymi, które nie zawierają się w dotychczas obliczonych zbiorach zgodnych (czyli w 1, 2, 3, 5).

---

Zgodnie z dotychczasowymi informacjami kolejnym etapem minimalizacji jest selekcja zbiorów zgodnych spełniających odpowiedni warunek pokrycia i zamknięcia. Dla porządku na planszy zapisany jest cały algorytm minimalizacji. Skoncentrujmy się na wyjaśnieniu warunków pokrycia i zamknięcia. Otóż pokrycie wymaga, aby każdy stan realizowanego automatu był elementem co najmniej jednej wybranej klasy. Natomiast zamknięcie wymaga, aby dla każdej litery wejściowej wszystkie następniki (stany następne) danej klasy były zawarte w jednej z wybranych klas.

---

Minimalnym zbiorem klas stanów zgodnych, spełniającym warunek pokrycia jest zbiór $\{\{1,2,3,5\},\{4,6\}\}$.

---

Zbiór ten nie jest jednak zamknięty, gdyż warunkami dla klasy $\{1,2,3,5\}$ są $\{3,6\}$ i $\{2,4\}$, które nie są spełnione, gdyż żadna z tych klas nie jest zawarta w żadnej z obu klas zbioru minimalnego.

---

Ponieważ następnikami klasy $\{4,6\}$ są klasy $\{1,2\}$ i $\{3,5\}$, więc spróbujmy rozbić klasę $\{1,2,3,5\}$ na klasy $\{1,2\}$ i $\{3,5\}$. Na podstawie tablicy trójkątnej stwierdzamy, że klasy te nie mają warunków zamknięcia. Jeśli zatem utworzymy zbiór $\{\{1,2\},\{3,5\},\{4,6\}\}$, to wszystkie klasy będące warunkami zamknięcia dla klas tego zbioru są zawarte w pewnych jego klasach. Zatem zbiór $MK{Z}_{opt}=\{\{1,2\},\{3,5\},\{4,6\}\}$, jest zamknięty i pełny, a więc jest minimalnym zbiorem klas zgodnych dla tego automatu. Konstrukcja automatu minimalnego pokazana jest na planszy.

---

Dokonamy minimalizacji liczby stanów automatu podanego w tablicy na planszy. Najpierw wypełniamy odpowiednią tablicę trójkątną. Następnie na podstawie par sprzecznych zaznaczonych krzyżykami eliminujemy pary zgodne warunkowo. Powstałe nowe krzyżyki zaznaczono kolorem czerwonym. W rezultacie uzyskujemy pary zgodne: $(1,3)$, $(1,7)$, $(2,5)$, $(2,8)$, $(3,4)$, $(3,5)$, $(3,6)$, $(4,5)$, $(4,6)$, $(4,7)$, $(5,7)$, $(5,8)$, $(6,7)$, $(6.8)$.

---

Z uzyskanych par zgodnych obliczamy (najłatwiej metodą bezpośrednią) maksymalne klasy zgodności: $\{2,5,8\}$, $\{3,4,5\}$, $\{3,4,6\}$, $\{4,5,7\}$, $\{4,6,7\}$, $\{1,3\}$, $\{1,7\}$, $\{6,8\}$.

---

W celu sprawdzenia warunku pokrycia i zamknięcia tworzymy tablicę następników stanów zawartych w poszczególnych klasach zgodności. Zbiory następników odczytujemy z tablicy przejść wyjść i zapisujemy w dwóch wierszach w zależności od wartości sygnału wejściowego $x$. Przykładowo dla zbioru zgodnego $2,5,8$ stany następne przy $x=0$ są odpowiednio Parser nie mógł rozpoznać (błąd składni): {\displaystyle 3, 3, –\,} natomiast przy $x=1$ stany następne dla $2,5,8$ są $1,-.-.$

---

---

---

---

---

---

---

---