- DFA označuje deterministické konečné automaty. Deterministický odkazuje na jedinečnost výpočtu. Konečné automaty se nazývají deterministické konečné automaty, pokud stroj čte vstupní řetězec jeden symbol po druhém.
- V DFA existuje pouze jedna cesta pro konkrétní vstup z aktuálního stavu do dalšího stavu.
- DFA nepřijímá nulový přesun, tj. DFA nemůže změnit stav bez jakéhokoli vstupního znaku.
- DFA může obsahovat více konečných stavů. Používá se v Lexikální analýze v kompilátoru.
Na následujícím diagramu vidíme, že ze stavu q0 pro vstup a vede pouze jedna cesta do q1. Podobně z q0 existuje pouze jedna cesta pro vstup b směřující do q2.
Formální definice DFA
DFA je sbírka 5-ti stejných, jak jsme popsali v definici FA.
Q: finite set of states ∑: finite set of the input symbol q0: initial state F: final state δ: Transition function
Přechodovou funkci lze definovat jako:
δ: Q x ∑→Q
Grafické znázornění DFA
DFA může být reprezentován digrafy nazývanými stavový diagram. Ve kterém:
- Stav je reprezentován vrcholy.
- Oblouk označený vstupním znakem ukazuje přechody.
- Počáteční stav je označen šipkou.
- Konečný stav je označen dvojitým kroužkem.
Příklad 1:
Q = {q0, q1, q2} ∑ = {0, 1} q0 = {q0} F = {q2} Řešení:
Schéma přechodu:
Přechodová tabulka:
| Současný stát | Další stav pro vstup 0 | Další stav vstupu 1 |
|---|---|---|
| →q0 | q0 | q1 |
| q1 | q2 | q1 |
| *q2 | q2 | q2 |
Příklad 2:
DFA s ∑ = {0, 1} přijímá vše začínající 0.
Řešení:
Vysvětlení:
- Ve výše uvedeném diagramu můžeme vidět, že na dané 0 jako vstupu do DFA ve stavu q0 DFA změní stav na q1 a vždy přejde do konečného stavu q1 na začátku vstupu 0. Může přijmout 00, 01, 000, 001... .atd. Nemůže přijmout žádný řetězec začínající 1, protože nikdy nepřejde do konečného stavu na řetězci začínajícím 1.
Příklad 3:
DFA s ∑ = {0, 1} přijímá všechny končící na 0.
Řešení:
Vysvětlení:
Ve výše uvedeném diagramu můžeme vidět, že na dané 0 jako vstupu do DFA ve stavu q0, DFA změní stav na q1. Může přijmout jakýkoli řetězec, který končí 0, například 00, 10, 110, 100 atd. Nemůže přijmout žádný řetězec, který končí 1, protože nikdy nepřejde do konečného stavu q1 na 1 vstupu, takže řetězec končící 1 nebude přijat nebo bude odmítnut.