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)$

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---

---