Jak wiadomo automat , w którym zbiór stanów wewnętrznych ma liczność może być zrealizowany na co najmniej 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 . 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ą zgodne, jeżeli dla każdego wejścia mają one niesprzeczne stany wyjść, a ich stany następne są takie same lub niesprzeczne.
Dwa stany wewnętrzne , są zgodne warunkowo, jeżeli ich stany wyjść są niesprzeczne oraz dla pewnego para stanów następnych do , (ozn. , ):
