Nondeterministic finite automaton

URI: https://gptkb.org/entity/Nondeterministic_finite_automaton
GPTKB entity
Statements (52)
Predicate Object
gptkbp:instanceOf gptkb:Technical_Machine
gptkb:Mathematical_model
gptkbp:abbreviation gptkb:NFA
gptkbp:allows Regular languages
gptkbp:category gptkb:Formal_languages
gptkb:Automata_theory
gptkb:Finite_automata
Nondeterministic models
gptkbp:closed gptkb:Kleene_star
gptkb:intersection
gptkb:Union
Complementation
Concatenation
gptkbp:complexity Can be exponentially more succinct than DFA
gptkbp:component Accept states (F)
Input alphabet (Σ)
Start state (q₀)
States (Q)
Transition function (δ)
gptkbp:definedIn 5-tuple (Q, Σ, δ, q₀, F)
gptkbp:describedBy "Finite Automata and Their Decision Problems"
gptkbp:equivalentTo gptkb:Deterministic_finite_automaton
gptkbp:field gptkb:Automata_theory
gptkb:Theoretical_computer_science
gptkb:Formal_language_theory
gptkbp:hasLanguage Regular language
gptkbp:hasProperty Can be simulated by DFA
Multiple possible transitions for a given input
gptkbp:hasTransition From one state to multiple states for same input
Symbol transition
ε-move (epsilon transition)
gptkbp:includesState Accepting state
Non-accepting state
gptkbp:introduced gptkb:Dana_Scott
gptkb:Michael_O._Rabin
gptkbp:introducedIn 1959
gptkbp:limitation Cannot recognize non-regular languages
No memory beyond current state
gptkbp:mayInclude ε-transitions
gptkbp:relatedTo gptkb:Technical_Machine
gptkb:Pushdown_automaton
Regular grammar
gptkbp:simulation gptkb:Subset_construction_(powerset_construction)
gptkbp:usedFor Pattern matching
Lexical analysis
Regular expression matching
gptkbp:usedIn Text processing
Compiler design
Automated verification
gptkbp:bfsParent gptkb:NFA
gptkbp:bfsLayer 6
https://www.w3.org/2000/01/rdf-schema#label Nondeterministic finite automaton