„Minimálautomata” változatai közötti eltérés

* A<math>\mathfrak{R}</math>A, mert A állapothoz ugyanaz az A nyelv tartozik, a reláció tehát [[reflexív]]

* Ha A<math>\mathfrak{R}</math>B akkor B<math>\mathfrak{R}</math>A azaz A és B állapotok nyelvei azonosak, akkor B és A állapotok nyelvei is azonosak, tehát a reláció [[szimmetrikus]]

 

Fentiekből következik, hogy az <math>\mathfrak{R}</math> reláció ekvivalenciareláció, amely az automata állapotait diszjunkt ekvivalencia osztályokra osztja. Egy ekvivalencia osztály állapotai egymástól nem megkülönböztethetőek, így az állapotok összevonhatók. Ha minden ekvivalenciaosztály állapotait összevontuk, akkor a megmaradt ekvivalenciaosztályok jelentik a minimálautomata állapotait, így a különböző állapotok számát sikerült leredukálni.

:[[Kép:Min 1.png]]

 

 

:{Q₀,Q₁,Q₅} és a {Q₂,Q₃,Q₄,Q₆,Q₇,Q₈}.

 

Egy szimbólum beolvasása után látható, hogy a Q₀,Q₁,Q₅ állapotok nem tartoznak egy ekvivalenciaosztályba, mert például az ''b'' szimbólum a nem elfogadó Q₅ állapotból elfogadó állapotba viszi az automatát, így az '''1'''-es ekvivalenciaosztály a következő képen alakul:

 

A következő szimbólum beolvasása már nem okoz semmilyen változást. Az egyszerűbb ábrázolás miatt a {Q₂,Q₃,Q₄,Q₆,Q₇,Q₈} állapotokat egy közös Q₂ állapotba összevonva megadja a keresett minimálautomatát, amelynek állapotdiagramja a következő:

 

Lényeges, hogy a minimálautomata nem a nyelvtanhoz, nem az azt megvalósító automatához, hanem a nyelvhez tartozik. Minden szabályos nyelvhez – az izomorfiáktól eltekintve – egy és csakis egy minimálautomata konstruálható.

 

== Források ==