En NFA kan ha null, ett eller mer enn ett trekk fra en gitt tilstand på et gitt inngangssymbol. En NFA kan også ha NULL-trekk (trekk uten inngangssymbol). På den annen side har DFA ett og bare ett trekk fra en gitt tilstand på et gitt inngangssymbol.

Trinn for å konvertere NFA til DFA:

Trinn 1: Konverter den gitte NFA til dens tilsvarende overgangstabell
For å konvertere NFA til dens ekvivalente overgangstabell, må vi liste opp alle tilstandene, inndatasymbolene og overgangsreglene. Overgangsreglene er representert i form av en matrise, der radene representerer gjeldende tilstand, kolonnene representerer inngangssymbolet, og cellene representerer neste tilstand.

Trinn 2: Opprett DFAs startstatus
DFAs starttilstand er settet med alle mulige starttilstander i NFA. Dette settet kalles epsilon-lukkingen av NFAs starttilstand. Epsilon-lukkingen er settet av alle tilstander som kan nås fra starttilstanden ved å følge epsilon(?)-overganger.

SIM-kort satt inn men ingen tjeneste android

Trinn 3: Lag DFAs overgangstabell
DFAs overgangstabell ligner på NFAs overgangstabell, men i stedet for individuelle tilstander, representerer radene og kolonnene sett med tilstander. For hvert inngangssymbol inneholder den tilsvarende cellen i overgangstabellen epsilon-lukkingen av settet med tilstander oppnådd ved å følge overgangsreglene i NFAs overgangstabell.

Trinn 4: Opprett DFAs endelige tilstander
DFAs endelige tilstander er settene med stater som inneholder minst én slutttilstand fra NFA.

Trinn 5: Forenkle DFA
DFA oppnådd i de foregående trinnene kan inneholde unødvendige tilstander og overganger. For å forenkle DFA kan vi bruke følgende teknikker:

• Fjern utilgjengelige tilstander: Stater som ikke kan nås fra starttilstanden, kan fjernes fra DFA.
• Fjern døde stater: Stater som ikke kan føre til en endelig tilstand kan fjernes fra DFA.
• Slå sammen ekvivalente tilstander: Stater som har samme overgangsregler for alle inngangssymboler kan slås sammen til en enkelt tilstand.

Trinn 6: Gjenta trinn 3-5 til ingen ytterligere forenkling er mulig
Etter å ha forenklet DFA, gjentar vi trinn 3-5 til ingen ytterligere forenkling er mulig. Den endelige oppnådde DFA er den minimerte DFA som tilsvarer den gitte NFA.

Eksempel: Tenk på følgende NFA vist i figur 1.

år inn i kvartaler

Følgende er de ulike parameterne for NFA. Q = { q0, q1, q2 } ? = (a, b) F = {q2}? (Overgangsfunksjon til NFA)

et eksempel på et åpen kildekode-os er

Trinn 1: Q' = ? Trinn 2: Q' = {q0} Trinn 3: For hver tilstand i Q', finn tilstandene for hvert inngangssymbol. For øyeblikket er tilstanden i Q' q0, finn trekk fra q0 på inngangssymbolet a og b ved å bruke overgangsfunksjonen til NFA og oppdater overgangstabellen til DFA. ?’ (Overgangsfunksjon for DFA)

Nå vil { q0, q1 } bli betraktet som en enkelt tilstand. Siden oppføringen ikke er i Q', legg den til Q'. Så Q' = { q0, { q0, q1 } } Nå, bevegelser fra tilstand { q0, q1 } på forskjellige inngangssymboler er ikke til stede i overgangstabellen til DFA, vi vil beregne det slik: ?' , a ) = ? (q0, a) ? ? ( q1, a ) = { q0, q1 } ?’ ( { q0, q1 }, b ) = ? (q0, b) ? ? ( q1, b ) = { q0, q2 } Nå skal vi oppdatere overgangstabellen til DFA. ?’ (Overgangsfunksjon for DFA)

Nå vil { q0, q2 } bli betraktet som en enkelt tilstand. Siden oppføringen ikke er i Q', legg den til Q'. Så Q' = { q0, { q0, q1 }, { q0, q2 } } Nå, trekk fra tilstand {q0, q2} på forskjellige inngangssymboler er ikke til stede i overgangstabellen til DFA, vi vil beregne det slik: ?' ( { q0, q2 }, a ) = ? (q0, a) ? ? ( q2, a ) = { q0, q1 } ?’ ( { q0, q2 }, b ) = ? (q0, b)? ? ( q2, b ) = { q0 } Nå skal vi oppdatere overgangstabellen til DFA. ?’ (Overgangsfunksjon for DFA)

Siden det ikke er generert noen ny tilstand, er vi ferdige med konverteringen. Den endelige tilstanden til DFA vil være tilstand som har q2 som sin komponent, dvs. {q0, q2}. Følgende er de forskjellige parameterne for DFA. Q’ = { q0, { q0, q1 }, { q0, q2 } ? = ( a, b ) F = { { q0, q2 } } og overgangsfunksjon ?’ som vist ovenfor. Den endelige DFA for NFA ovenfor er vist i figur 2.

Merk : Noen ganger er det ikke lett å konvertere regulære uttrykk til DFA. Først kan du konvertere regulære uttrykk til NFA og deretter NFA til DFA.

Spørsmål : Antall tilstander i den minimale deterministiske endelige automaten som tilsvarer det regulære uttrykket (0 + 1)* (10) er ____________.

Løsning : Først skal vi lage en NFA for uttrykket ovenfor. For å lage en NFA for (0 + 1)*, vil NFA være i samme tilstand q0 på inngangssymbol 0 eller 1. Så for sammenkobling, vil vi legge til to trekk (q0 til q1 for 1 og q1 til q2 for 0) som vist i figur 3.

10 av 50

Denne artikkelen er bidratt av Sonal Tuteja.