„Minimálautomata” változatai közötti eltérés
| [nem ellenőrzött változat] | [nem ellenőrzött változat] |
Tartalom törölve Tartalom hozzáadva
a Gyakori helyesírási hibák javítása kézi ellenőrzéssel |
|||
33. sor:
Az előbbiekben meghatározott ekvivalenciaosztályba sorolás véges számú lépésben is elvégezhető.
Vezessük be egy olyan reláció családot, amelyben két állapotot ''i ekvivalensnek'' nevezünk, ha legfeljebb ''i'' hosszúságú jelsorozattal nem különböztethetők meg. Az eredeti ekvivalencia az '''i'''<math>\rightarrow\infty</math> átmenettel áll elő. Ha ismerjük az állapottér '''i''' ekvivalens ekvivalenciaosztályait, akkor az '''i+1''' ekvivalenciaosztályokat könnyen meghatározhatjuk, mert ami nem volt '''i''' ekvivalens, az nyilván nem lehet, és nem is lesz '''i+1''' ekvivalens sem. Ezért elegendő csak azokat az '''i''' ekvivalens osztályokat vizsgálni, ahol egynél több állapot szerepel, és ahonnan egy
Induljunk ki a '''0''' ekvivalenciaosztályból: ekkor még egyetlen szimbólumot sem olvastunk be, az állapotdiagrammról viszont szemmel meg tudjuk különböztetni az elfogadó és visszautasító állapotokat, tehát két ekvivalenciaosztályt már meg is tudtunk határozni. Most növeljük a beolvasott szimbólumok számát addig, amíg az ekvivalenciosztályok száma nem nő tovább. Ez előbb-utóbb be is következik, mivel az állapotok száma véges, és egyetlen állapotot tartalmazó ekvivalenciosztályt tovább már nem lehet bontani. Így véges lépésekben meg tudtuk oldani a feladatot.
| |||