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=[log_{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})\neq (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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle k,l\,} odpowiadająca klatce Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{\{1,2,3,5\}, \{4,6\}\}} .

---

Zbiór ten nie jest jednak zamknięty, gdyż warunkami dla klasy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{1,2,3,5\}} są Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{3,6\}} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{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 Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{4,6\}} są klasy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{1,2\}} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{3,5\}} , więc spróbujmy rozbić klasę Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{1,2,3,5\}} na klasy Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{1,2\}} i Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \{3,5\}} . Na podstawie tablicy trójkątnej stwierdzamy, że klasy te nie mają warunków zamknięcia. Jeśli zatem utworzymy zbiór Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle \Big\{\{1,2\}, \{3,5\}, \{4,6\}\Big\}} , to wszystkie klasy będące warunkami zamknięcia dla klas tego zbioru są zawarte w pewnych jego klasach. Zatem zbiór Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle MKZ_{opt} = \Big\{\{1,2\}, \{3,5\}, \{4,6\}\Big\}} , 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: Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (1,3)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (1,7)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (2,5)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (2,8)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (3,4)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (3,5)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (3,6)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (4,5)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (4,6)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (4,7)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (5,7)} , Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle (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ć (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 3, 3, –\,} natomiast przy $x=1$ stany następne dla $2,5,8\,$ są $1,-.-.\,$

---

Na tej planszy tablicę następników zapisujemy w formie uproszczonej. Na przykład poprzednio obliczone następniki: Parser nie mógł rozpoznać (SVG (MathML może zostać włączone przez wtyczkę w przeglądarce): Nieprawidłowa odpowiedź („Math extension cannot connect to Restbase.”) z serwera „https://wazniak.mimuw.edu.pl/api/rest_v1/”:): {\displaystyle 3, 3, –\,} zapiszemy po prostu jako $3\,$. Analizując wypisane w tak zmodyfikowanej tablicy następniki łatwo zauważyć, że zbiory $\{2,5,8\}$, $\{4,6,7\}$ oraz $\{1,3\}$ spełniają warunek pokrycia i zamkniętości. Na planszy podana jest również konstrukcja tablicy przejść-wyjść automatu minimalnego o stanach wewnętrznych $A,B,C\,$.

---

Celem kolejnego przykładu jest omówienie całego procesu syntezy automatu tj. począwszy od etapu syntezy abstrakcyjnej. Naszym zadaniem będzie zaprojektowanie układu sekwencyjnego tzw. detektora sekwencji. Opis działania tego układu podany jest na planszy. Celem etapu syntezy abstrakcyjnej jest zapisanie działania automatu w formie tablicy lub grafu przejść wyjść. Zazwyczaj konstruowanie grafu jest wygodniejsze. W przypadku detektora sekwencji w pierwotnym grafie wyróżnić należy $7\,$ stanów. Przykładowo: w stanie $1\,$ po pojawieniu się sygnału wejściowego $x=0$ automat przechodzi do stanu $2\,$ , a po pojawieniu się $x=1$ automat przechodzi do stanu $3\,$. W obu przypadkach generowany na wyjściu automatu sygnał $y\,$ może być dowolny, co symbolicznie zaznaczono „kreską”. Właściwa sekwencja jest wykrywana po przejściu przez stany $1,2,4\,$ i tylko wtedy na wyjściu automatu generowany jest sygnał o wartości $1\,$. W pozostałych przypadkach odpowiedź automatu jest $0\,$.

---

Na podstawie uzyskanego w ten sposób grafu automatu łatwo utworzyć odpowiednią tablicę przejść wyjść. Łatwo spostrzec, że w utworzonej tablicy stany $5,6\,$ i $7\,$ (zacienione na czerwono) są sobie równoważne i w takim razie można je zredukować do jednego stanu. W tej sytuacji upraszcza się zarówno tablica przejść wyjść automatu jak też jego graf.

---

I jest zrozumiałe, że dalszej syntezie poddamy taki częściowo już zminimalizowany automat. Po wypełnieniu odpowiedniej tablicy trójkątnej i wykreśleniu zgodnej warunkowo pary $2,3\,$ stwierdzamy, że w tym automacie jest dużo par zgodnych. Ale pary sprzeczne są tylko dwie. Warto więc liczyć maksymalne klasy zgodne metodą wg par sprzecznych.

---

Obliczone pary sprzeczne zapisujemy w postaci wyrażenia boolowskiego typu iloczyn (koniunkcja) dwuskładnikowych sum $(2\lor 3)(4\lor 5)$, które po wymnożeniu uzyskuje postać $24\lor 25\lor 34\lor 35$ Odejmując od zbioru $S=\{1,2,3,4,5\}$ wszystkich stanów zbiory zapisane poszczególnych składnikach uzyskujemy rodzinę wszystkich MKZ: $\{1,3,5\}$ $\{1,3,4\}$ $\{1,2,5\}$ $\{1,2,4\}$

---

Warunek pokrycia spełniają dwa zbiory: $\{1,3,5\}$ oraz $\{1,2,4\}$. Niestety nie spełniają one warunku zamknięcia. Dobierając trzeci zbiór, a mianowicie $\{1,2,5\}$ uzyskujemy spełnienie obu warunków. Na tej podstawie tworzymy tablicę przejść wyjść automatu minimalnego.

---

Dla tak uzyskanego automatu należy dokonać kodowania stanów a następnie wykonać syntezę kombinacyjną. Warto jednak zauważyć, że uzyskany automat minimalny był już realizowany na planszach od $16\,$ do $22\,$ w module $7\,$.

---