Minimálautomata

Egy adott szabályos nyelv által meghatározott, teljesen meghatározott DFA akkor minimálautomata, ha az adott nyelvet megvalósító DFA-k közül a lehető legkevesebb átmeneti állapottal rendelkezik.

Mivel egy formális nyelvet több nyelvtan is generálhat, egy nyelvnek több automatája is lehet. Minimálautomatát csak determinisztikus automatából lehet készíteni, de ez nem súlyos korlátozás, hiszen minden nemdeterminisztikus automatából lehet vele ekvivalens, determinisztikus automatát készíteni.

Minimálautomata készítése

Egy automatából a következő feltételek fennállása esetén lehet minimálautomatát redukálni:

• Az automatának determinisztikusnak kell lennie
• Az automatának teljesen meghatározottnak kell lennie

Nem teljesen meghatározott az a determinisztikus véges állapotú automata, amelyben létezik olyan állapot-bejövő szimbólum pár, amelyre nincsen állapot átmenti szabály meghatározva.

Ha az adott automata átmeneti szabályait kiegészítjük egy speciális csapda állapottal, amelybe az automata akkor kerül, ha egy olyan állapot-bejövő szimbólum párt találunk, amelyhez nincs állapot változási szabály. A csapda állapot nem elfogadó állapot, és a csapda állapotot semmilyen bejövő szimbólum nem változtatja meg. Ez a megoldás biztosítja, hogy az automata minden, eddig nem beolvasható stringet beolvasson. Nyilvánvaló, hogy az így kibővített, teljesen specifikált automata ugyanazt a nyelvet fogadja el, mint a nem teljesen specifikált változata, így a két automata ekvivalens.

Elméleti redukció

Egy teljesen meghatározott determinisztikus automata minden állapotához rendeljük hozzá egy nyelvet, amelyet az eredeti automata akkor fogad el, ha a kiinduló állapota a vizsgált állapot lenne. Az eredeti automata által elfogadott nyelv természetesen ugyanaz marad.

Értelmezzünk egy ${\mathfrak {R}}$ relációt az automata állapotai között. A reláció akkor, és csak akkor igaz, ha a két állapothoz rendelt nyelv azonos. Az ${\mathfrak {R}}$ reláció tulajdonságai:

• A${\mathfrak {R}}$A, mert A állapothoz ugyanaz az A nyelv tartozik, a reláció tehát reflexív
• Ha A${\mathfrak {R}}$B akkor B${\mathfrak {R}}$A azaz A és B állapotok nyelvei azonosak, akkor B és A állapotok nyelvei is azonosak, tehát a reláció szimmetrikus
• A${\mathfrak {R}}$B $\cap$ B${\mathfrak {R}}$C, akkor A${\mathfrak {R}}$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.

Fentiekből következik, hogy az ${\mathfrak {R}}$ 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.

Az azonos ekvivalenciaosztályba tartozó állapotok megtalálása esetlegesen hosszadalmas eljárás lehet, de a lehetséges jelsorozatok száma nem lehet több, mint a $\sum$ ábácé halmaz számossága, ami megszámlálhatóan végtelen.

Példa

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$\rightarrow \infty$ á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 újabb szimbólum beolvasásával új állapotba jut az automata. Amennyiben újabb szimbólum beolvasásával nem növekszik az ekvivalenciaosztályok száma, akkor a jelenlegi ekvivalenciaosztályok száma éppen megegyezik a definíció szerinti ekvivalenciaosztályok számával, a feladatot véges lépésekben megoldottuk.

Induljunk ki a 0 ekvivalenciaosztályból: ekkor még egyetlen szimbólumot sem olvastunk be, az állapotdiagramró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 ekvivalenciaosztá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ó ekvivalenciaosztályt tovább már nem lehet bontani. Így véges lépésekben meg tudtuk oldani a feladatot.

Nézzük a következő állapotdiagrammal meghatározott automatát, amely Q₀ állapotból indul, az a és b szimbólumokból áll az ábécéje, és az állapotdiagramon az elfogadó állapotokat szürkével jelöltük:

Kiindulásként írjuk fel a két 0-s (elfogadó, visszautasító) ekvivalenciaosztályt

{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:

{Q₀} {Q₁} {Q₅} valamint {Q₂,Q₃,Q₄,Q₆,Q₇,Q₈}.

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ó. Bizonyítható – az ún. ellenautomata konstruálásával – hogy egy adott nyelvhez konstruált minimálautomatából csak egy létezhet.

Források

• Bach Iván. Formális nyelvek. Egyetemi tankönyv, második kiadás, Typotex Kiadó, 2001. 2.3. fejezet: Minimálautomata