En NFA kan ha noll, ett eller fler än ett drag från ett givet tillstånd på en given ingångssymbol. En NFA kan också ha NULL-drag (drag utan inmatningssymbol). Å andra sidan har DFA ett och endast ett drag från ett givet tillstånd på en given ingångssymbol.
Steg för att konvertera NFA till DFA:
Steg 1: Konvertera den givna NFA till dess motsvarande övergångstabell
För att konvertera NFA till dess motsvarande övergångstabell måste vi lista alla tillstånd, inmatningssymboler och övergångsregler. Övergångsreglerna representeras i form av en matris, där raderna representerar det aktuella tillståndet, kolumnerna representerar inmatningssymbolen och cellerna representerar nästa tillstånd.
Steg 2: Skapa DFA:s startläge
DFA:s startläge är uppsättningen av alla möjliga starttillstånd i NFA. Denna uppsättning kallas epsilon-stängningen av NFA:s startläge. Epsilon-stängningen är uppsättningen av alla tillstånd som kan nås från starttillståndet genom att följa epsilon (?) övergångar.
hur man visar en applikation på Android
Steg 3: Skapa DFA:s övergångstabell
DFA:s övergångstabell liknar NFA:s övergångstabell, men istället för enskilda tillstånd representerar raderna och kolumnerna uppsättningar av tillstånd. För varje ingångssymbol innehåller motsvarande cell i övergångstabellen epsilon-stängningen av uppsättningen av tillstånd som erhållits genom att följa övergångsreglerna i NFA:s övergångstabell.
Steg 4: Skapa DFA:s slutliga tillstånd
DFA:s sluttillstånd är de uppsättningar av stater som innehåller minst ett sluttillstånd från NFA.
Steg 5: Förenkla DFA
DFA som erhållits i de föregående stegen kan innehålla onödiga tillstånd och övergångar. För att förenkla DFA kan vi använda följande tekniker:
all caps genväg excel
- Ta bort oåtkomliga tillstånd: Tillstånd som inte kan nås från startläget kan tas bort från DFA.
- Ta bort döda tillstånd: Tillstånd som inte kan leda till ett slutligt tillstånd kan tas bort från DFA.
- Sammanfoga ekvivalenta tillstånd: Tillstånd som har samma övergångsregler för alla inmatningssymboler kan slås samman till ett enda tillstånd.
Steg 6: Upprepa steg 3-5 tills ingen ytterligare förenkling är möjlig
Efter att ha förenklat DFA upprepar vi steg 3-5 tills ingen ytterligare förenkling är möjlig. Den slutliga DFA som erhålls är den minimerade DFA som motsvarar den givna NFA.
Exempel: Tänk på följande NFA som visas i figur 1.
Följande är de olika parametrarna för NFA. Q = { q0, q1, q2 } ? = (a, b) F = {q2}? (NFAs övergångsfunktion)
Steg 1: Q’ = ? Steg 2: Q' = {q0} Steg 3: För varje tillstånd i Q', hitta tillstånden för varje ingångssymbol. För närvarande är tillståndet i Q' q0, hitta drag från q0 på ingångssymbolen a och b med hjälp av övergångsfunktionen för NFA och uppdatera övergångstabellen för DFA. ?’ (Övergångsfunktion för DFA)
Nu kommer {q0, q1} att betraktas som ett enda tillstånd. Eftersom posten inte är i Q', lägg till den i Q'. Så Q' = { q0, { q0, q1 } } Nu, flyttar från tillstånd { q0, q1 } på olika ingångssymboler finns inte i övergångstabellen för DFA, vi kommer att beräkna det som: ?' , a ) = ? (q0, a) ? ? ( q1, a ) = { q0, q1 } ?’ ( { q0, q1 }, b ) = ? (q0, b)? ? ( q1, b ) = { q0, q2 } Nu kommer vi att uppdatera övergångstabellen för DFA. ?’ (Övergångsfunktion för DFA)
t ff
Nu kommer { q0, q2 } att betraktas som ett enda tillstånd. Eftersom posten inte är i Q', lägg till den i Q'. Så Q' = { q0, { q0, q1 }, { q0, q2 } } Nu, drag från tillstånd {q0, q2} på olika inmatningssymboler finns inte i övergångstabellen för DFA, vi kommer att beräkna det som: ?' ( { q0, q2 }, a ) = ? (q0, a) ? ? ( q2, a ) = { q0, q1 } ?’ ( { q0, q2 }, b ) = ? (q0, b) ? ? ( q2, b ) = { q0 } Nu kommer vi att uppdatera övergångstabellen för DFA. ?’ (Övergångsfunktion för DFA)
Eftersom det inte genereras något nytt tillstånd är vi klara med konverteringen. Sluttillståndet för DFA kommer att vara tillstånd som har q2 som sin komponent, dvs. {q0, q2}. Följande är de olika parametrarna för DFA. Q’ = { q0, { q0, q1 }, { q0, q2 } ? = ( a, b ) F = { { q0, q2 } } och övergångsfunktion ?’ som visas ovan. Den slutliga DFA för ovanstående NFA har visats i figur 2.
Notera : Ibland är det inte lätt att konvertera reguljärt uttryck till DFA. Först kan du konvertera reguljärt uttryck till NFA och sedan NFA till DFA.
Fråga: Antalet tillstånd i den minimala deterministiska finita automaten som motsvarar det reguljära uttrycket (0 + 1)* (10) är ____________.
Lösning: Först kommer vi att göra en NFA för uttrycket ovan. För att göra en NFA för (0 + 1)*, kommer NFA att vara i samma tillstånd q0 på ingångssymbolen 0 eller 1. Sedan för sammanlänkning lägger vi till två drag (q0 till q1 för 1 och q1 till q2 för 0) som visas i figur 3.
Den här artikeln har bidragit från Sonal Tuteja.