- DFA hänvisar till deterministiska finita automater. Deterministisk hänvisar till det unika i beräkningen. De finita automaterna kallas deterministiska finita automater om maskinen läses en inmatningssträng en symbol i taget.
- I DFA finns det bara en väg för specifik inmatning från det aktuella tillståndet till nästa tillstånd.
- DFA accepterar inte nollrörelsen, dvs. DFA:n kan inte ändra tillstånd utan något inmatningstecken.
- DFA kan innehålla flera sluttillstånd. Det används i Lexical Analysis i Compiler.
I följande diagram kan vi se att från tillstånd q0 för ingång a, finns det bara en väg som går till q1. På liknande sätt, från q0, finns det bara en väg för ingång b som går till q2.
Formell definition av DFA
En DFA är en samling av 5-tupler samma som vi beskrev i definitionen av FA.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Övergångsfunktion kan definieras som:
δ: Q x ∑→Q
Grafisk representation av DFA
En DFA kan representeras av digrafer som kallas tillståndsdiagram. I vilken:
- Staten representeras av hörn.
- Bågen märkt med ett inmatningstecken visar övergångarna.
- Utgångsläget är markerat med en pil.
- Sluttillståndet betecknas med en dubbel cirkel.
Exempel 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Lösning:
Övergångsdiagram:
Övergångstabell:
| Nuvarande tillstånd | Nästa tillstånd för ingång 0 | Nästa tillstånd för inmatning 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Exempel 2:
DFA med ∑ = {0, 1} accepterar alla som börjar med 0.
Lösning:
Förklaring:
- I diagrammet ovan kan vi se att på given 0 som ingång till DFA i tillstånd q0 ändrar DFA tillstånd till q1 och går alltid till sluttillstånd q1 vid start av ingång 0. Den kan acceptera 00, 01, 000, 001... .etc. Den kan inte acceptera någon sträng som börjar med 1, eftersom den aldrig kommer att gå till sluttillstånd på en sträng som börjar med 1.
Exempel 3:
DFA med ∑ = {0, 1} accepterar alla som slutar med 0.
Lösning:
Förklaring:
I diagrammet ovan kan vi se att vid given 0 som indata till DFA i tillstånd q0, ändrar DFA tillstånd till q1. Den kan acceptera vilken sträng som helst som slutar med 0 som 00, 10, 110, 100...etc. Den kan inte acceptera någon sträng som slutar med 1, eftersom den aldrig kommer att gå till sluttillståndet q1 på 1 ingång, så strängen som slutar med 1 kommer inte att accepteras eller kommer att avvisas.