- DFA reiškia deterministinius baigtinius automatus. Deterministinis reiškia skaičiavimo unikalumą. Baigtiniai automatai vadinami deterministiniais baigtiniais automatais, jei mašina skaito įvesties eilutę po vieną simbolį.
- DFA yra tik vienas konkrečios įvesties kelias iš dabartinės būsenos į kitą būseną.
- DFA nepriima nulinio judėjimo, t. y. DFA negali pakeisti būsenos be jokio įvesties simbolio.
- DFA gali būti kelios galutinės būsenos. Jis naudojamas kompiliatoriaus leksinėje analizėje.
Toliau pateiktoje diagramoje matome, kad iš įvesties a būsenos q0 yra tik vienas kelias, einantis į q1. Panašiai, nuo q0, yra tik vienas įvesties b kelias į q2.
Oficialus DFA apibrėžimas
DFA yra 5 eilučių rinkinys, toks pat, kaip aprašėme FA apibrėžime.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Perėjimo funkciją galima apibrėžti taip:
δ: Q x ∑→Q
Grafinis DFA vaizdavimas
DFA gali būti pavaizduotas digrafais, vadinamais būsenos diagrama. Kuriame:
- Valstybę vaizduoja viršūnės.
- Lankas, pažymėtas įvesties simboliu, rodo perėjimus.
- Pradinė būsena pažymėta rodykle.
- Galutinė būsena žymima dvigubu apskritimu.
1 pavyzdys:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Sprendimas:
Perėjimo schema:
Perėjimo lentelė:
| Dabartinė valstybė | Kita 0 įvesties būsena | Kita 1 įvesties būsena |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | 2 k | q1 |
| *2 k | 2 k | 2 k |
2 pavyzdys:
DFA su ∑ = {0, 1} priima viską, prasidedantį 0.
Sprendimas:
Paaiškinimas:
- Aukščiau pateiktoje diagramoje matome, kad davus 0 kaip DFA įvestį būsenoje q0, DFA pakeičia būseną į q1 ir visada pereina į galutinę būseną q1 pradėjus įvestį 0. Jis gali priimti 00, 01, 000, 001... .tt Ji negali priimti jokios eilutės, kuri prasideda skaičiumi 1, nes ji niekada nepateks į galutinę būseną eilutėje, prasidedančioje 1.
3 pavyzdys:
DFA su ∑ = {0, 1} priima viską, kas baigiasi 0.
Sprendimas:
Paaiškinimas:
Aukščiau pateiktoje diagramoje matome, kad 0 kaip DFA įvestis būsenoje q0, DFA pakeičia būseną į q1. Jis gali priimti bet kokią eilutę, kuri baigiasi 0, pavyzdžiui, 00, 10, 110, 100.... ir tt. Ji negali priimti jokios eilutės, kuri baigiasi 1, nes ji niekada nepateks į galutinę būseną q1 1 įvestyje, todėl eilutė, kuri baigiasi 1, nebus priimta arba bus atmesta.