- DFA viittaa deterministisiin äärellisiin automaateihin. Deterministisyys viittaa laskennan ainutlaatuisuuteen. Äärillisiä automaatteja kutsutaan deterministisiksi äärellisiksi automaateiksi, jos koneelle luetaan syötemerkkijono symboli kerrallaan.
- DFA:ssa on vain yksi polku tietylle syötteelle nykyisestä tilasta seuraavaan tilaan.
- DFA ei hyväksy nollasiirtoa, eli DFA ei voi muuttaa tilaa ilman syötettä.
- DFA voi sisältää useita lopputiloja. Sitä käytetään Compilerin Lexical Analysisissä.
Seuraavassa kaaviossa voimme nähdä, että tilasta q0 syötteelle a on vain yksi polku, joka menee q1:een. Vastaavasti q0:sta tulolle b on vain yksi polku q2:een.
DFA:n virallinen määritelmä
DFA on kokoelma viisi monikkoa, jotka ovat samat kuin kuvailimme FA:n määritelmässä.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Siirtymäfunktio voidaan määritellä seuraavasti:
δ: Q x ∑→Q
DFA:n graafinen esitys
DFA voidaan esittää digrafeilla, joita kutsutaan tilakaavioiksi. Jossa:
- Valtiota edustavat kärjet.
- Syötemerkillä merkitty kaari näyttää siirtymät.
- Alkutila on merkitty nuolella.
- Lopullinen tila on merkitty kaksoisympyrällä.
Esimerkki 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Ratkaisu:
Siirtymäkaavio:
Siirtymätaulukko:
| Nykyinen valtio | Seuraava tila tulolle 0 | Seuraava syöttötila 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Esimerkki 2:
DFA, jossa ∑ = {0, 1}, hyväksyy kaikki 0:lla alkavat.
Ratkaisu:
Selitys:
- Yllä olevasta kaaviosta voidaan nähdä, että annetulla 0:lla DFA:n syötteenä tilassa q0 DFA muuttaa tilan q1:ksi ja siirtyy aina lopulliseen tilaan q1, kun aloitustulo on 0. Se voi hyväksyä 00, 01, 000, 001... .jne. Se ei voi hyväksyä merkkijonoa, joka alkaa 1:llä, koska se ei koskaan mene lopulliseen tilaan 1:llä alkavassa merkkijonossa.
Esimerkki 3:
DFA, jossa ∑ = {0, 1} hyväksyy kaikki, jotka päättyvät 0:aan.
Ratkaisu:
Selitys:
Yllä olevasta kaaviosta voimme nähdä, että kun DFA on syötetty arvoon 0 tilassa q0, DFA muuttaa tilan q1:ksi. Se voi hyväksyä minkä tahansa merkkijonon, joka päättyy 0:aan, kuten 00, 10, 110, 100... jne. Se ei voi hyväksyä merkkijonoa, joka päättyy 1:een, koska se ei koskaan mene lopulliseen tilaan q1 yhdellä syötteellä, joten merkkijonoa, joka päättyy 1:een, ei hyväksytä tai se hylätään.