Deterministic Finite Automaton
GPTKB entity
Statements (50)
| Predicate | Object |
|---|---|
| gptkbp:instanceOf |
Technical Machine
Mathematical model |
| gptkbp:abbreviation |
gptkb:DFA
|
| gptkbp:acceptStatesSymbol |
F
|
| gptkbp:allows |
Regular languages
|
| gptkbp:closed |
gptkb:Kleene_star
gptkb:intersection Union Complementation Concatenation |
| gptkbp:contrastsWith |
gptkb:Nondeterministic_Finite_Automaton
|
| gptkbp:formalDefinition |
5-tuple (Q, Σ, δ, q0, F)
|
| gptkbp:hasApplication |
Natural language processing
Control systems Model checking Compiler design Digital circuit design Finite state machine modeling Network protocol analysis Protocol verification String matching algorithms Text search |
| gptkbp:hasComponent |
Finite set of states
Input alphabet Set of accept states Start state Transition function |
| gptkbp:hasProperty |
Deterministic transitions
No epsilon transitions One transition per symbol per state |
| https://www.w3.org/2000/01/rdf-schema#label |
Deterministic Finite Automaton
|
| gptkbp:inputAlphabetSymbol |
Σ
|
| gptkbp:introduced |
gptkb:Walter_Pitts
gptkb:Warren_McCulloch |
| gptkbp:introducedIn |
1943
|
| gptkbp:limitation |
Cannot recognize non-regular languages
|
| gptkbp:minimizationAlgorithm |
gptkb:Hopcroft's_algorithm
gptkb:Moore's_algorithm |
| gptkbp:relatedTo |
gptkb:Pushdown_automaton
Technical Machine Regular expressions |
| gptkbp:startStateSymbol |
q0
|
| gptkbp:stateSetSymbol |
gptkb:Q
|
| gptkbp:transitionFunctionSymbol |
δ
|
| gptkbp:usedFor |
Pattern matching
Lexical analysis |
| gptkbp:usedIn |
gptkb:Formal_language_theory
Computer science |
| gptkbp:bfsParent |
gptkb:DFA
|
| gptkbp:bfsLayer |
6
|