- DFA označuje deterministické konečné automaty. Deterministický odkazuje na jedinečnosť výpočtu. Konečné automaty sa nazývajú deterministické konečné automaty, ak stroj číta vstupný reťazec po jednom symbole.
- V DFA existuje iba jedna cesta pre konkrétny vstup z aktuálneho stavu do nasledujúceho stavu.
- DFA neakceptuje nulový presun, t. j. DFA nemôže zmeniť stav bez akéhokoľvek vstupného znaku.
- DFA môže obsahovať viacero konečných stavov. Používa sa v Lexikálnej analýze v kompilátore.
Na nasledujúcom diagrame vidíme, že zo stavu q0 pre vstup a vedie len jedna cesta do q1. Podobne z q0 existuje len jedna cesta pre vstup b smerujúca do q2.
Formálna definícia DFA
DFA je súbor 5-tich rovnakých ako sme opísali v definícii FA.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Prechodovú funkciu možno definovať ako:
δ: Q x ∑→Q
Grafické znázornenie DFA
DFA môže byť reprezentovaná digrafmi nazývanými stavový diagram. V ktorom:
- Stav je reprezentovaný vrcholmi.
- Oblúk označený vstupným znakom zobrazuje prechody.
- Počiatočný stav je označený šípkou.
- Konečný stav je označený dvojitým kruhom.
Príklad 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Riešenie:
Schéma prechodu:
Prechodová tabuľka:
| Súčasný štát | Ďalší stav pre vstup 0 | Ďalší stav vstupu 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Príklad 2:
DFA s ∑ = {0, 1} akceptuje všetky začínajúce 0.
Riešenie:
Vysvetlenie:
dynamické pole java
- Vo vyššie uvedenom diagrame môžeme vidieť, že na danej 0 ako vstupe do DFA v stave q0 DFA zmení stav na q1 a vždy prejde do konečného stavu q1 na štartovacom vstupe 0. Môže akceptovať 00, 01, 000, 001... .atď. Nemôže akceptovať žiadny reťazec, ktorý začína 1, pretože nikdy neprejde do konečného stavu na reťazci začínajúcom 1.
Príklad 3:
DFA s ∑ = {0, 1} akceptuje všetky končiace na 0.
Riešenie:
Vysvetlenie:
Vo vyššie uvedenom diagrame môžeme vidieť, že na danej 0 ako vstupe do DFA v stave q0, DFA zmení stav na q1. Môže akceptovať akýkoľvek reťazec, ktorý končí 0, napríklad 00, 10, 110, 100... atď. Nemôže akceptovať žiadny reťazec, ktorý končí na 1, pretože nikdy neprejde do konečného stavu q1 na 1 vstupe, takže reťazec končiaci na 1 nebude akceptovaný alebo bude odmietnutý.