- DFA refererer til deterministiske endelige automater. Deterministisk refererer til det unike ved beregningen. De endelige automatene kalles deterministiske endelige automater hvis maskinen leses en inngangsstreng ett symbol om gangen.
- I DFA er det bare én bane for spesifikke input fra gjeldende tilstand til neste tilstand.
- DFA godtar ikke nulltrekket, dvs. DFA kan ikke endre tilstand uten noe inndatategn.
- DFA kan inneholde flere slutttilstander. Det brukes i leksikalsk analyse i kompilator.
I det følgende diagrammet kan vi se at fra tilstand q0 for inngang a, er det bare én vei som går til q1. På samme måte, fra q0, er det bare én vei for inngang b som går til q2.
Formell definisjon av DFA
En DFA er en samling av 5-tupler samme som vi beskrev i definisjonen av FA.
java arv
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Overgangsfunksjon kan defineres som:
δ: Q x ∑→Q
Grafisk representasjon av DFA
En DFA kan representeres av digrafer kalt tilstandsdiagram. I hvilke:
- Staten er representert ved hjørner.
- Buen merket med et inndatategn viser overgangene.
- Starttilstanden er markert med en pil.
- Den endelige tilstanden er angitt med en dobbel sirkel.
Eksempel 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Løsning:
Overgangsdiagram:
Overgangstabell:
| Nåværende tilstand | Neste tilstand for inngang 0 | Neste inndatatilstand 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Eksempel 2:
DFA med ∑ = {0, 1} godtar alle som begynner med 0.
Løsning:
Forklaring:
tostring-metoden i java
- I diagrammet ovenfor kan vi se at på gitt 0 som input til DFA i tilstand q0, endrer DFA tilstand til q1 og går alltid til slutttilstand q1 ved start av inngang 0. Den kan akseptere 00, 01, 000, 001... .etc. Den kan ikke akseptere en streng som starter med 1, fordi den aldri vil gå til endelig tilstand på en streng som begynner med 1.
Eksempel 3:
DFA med ∑ = {0, 1} godtar alle som slutter med 0.
Løsning:
Forklaring:
I diagrammet ovenfor kan vi se at på gitt 0 som input til DFA i tilstand q0, endrer DFA tilstand til q1. Den kan godta hvilken som helst streng som ender med 0 som 00, 10, 110, 100 ... osv. Den kan ikke akseptere en streng som slutter med 1, fordi den aldri vil gå til den endelige tilstanden q1 på 1 inngang, så strengen som slutter med 1, vil ikke bli akseptert eller vil bli avvist.