„Minimálautomata” változatai közötti eltérés
| [ellenőrzött változat] | [ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Nincs bevezető sablon |
a →Elméleti redukció: egyértelműsítés |
||
24. sor:
* A<math>\mathfrak{R}</math>A, mert A állapothoz uyanaz 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]]
* A<math>\mathfrak{R}</math>B <math>\cap</math> B<math>\mathfrak{R}</math>C, akkor A<math>\mathfrak{R}</math>C, azaz ha A és B állapotok nyelvei azonosak, és B és C állapotok nyelvei is, akkor A és C állapot nyelvei is, tehát a reláció [[tranzitív reláció|tranzitív]].
Fentiekből következik, hogy az <math>\mathfrak{R}</math> reláció ekvivalenciareláció, amely az automata állapotait diszkjunkt ekvilalencia osztályokra osztja. Egy ekvivalencia osztály állapotai egymástól nem megkülönböztethetőek, így az állapotok összevonhatók. Ha minden ekvivalenciosztá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.
| |||