nondeterministic finite automaton

URI: https://gptkb.org/entity/nondeterministic_finite_automaton
GPTKB entity
Statements (33)
Predicate Object
gptkbp:instanceOf Technical Machine
gptkbp:abbreviation gptkb:NFA
gptkbp:allows regular language
gptkbp:closed gptkb:Kleene_star
gptkb:intersection
Union
complementation
concatenation
gptkbp:computationalPower same as deterministic finite automaton
gptkbp:contrastsWith gptkb:deterministic_finite_automaton
gptkbp:convertedTo gptkb:deterministic_finite_automaton
gptkbp:describedBy "Finite Automata and Their Decision Problems"
gptkbp:field automata theory
theoretical computer science
gptkbp:hasAcceptStates set of accept states
gptkbp:hasEpsilonTransition yes
gptkbp:hasInputAlphabet input alphabet
gptkbp:hasStartState start state
gptkbp:hasTransition multiple possible next states
gptkbp:hasTransitionFunction transition function
https://www.w3.org/2000/01/rdf-schema#label nondeterministic finite automaton
gptkbp:includesState set of states
gptkbp:introduced gptkb:Dana_Scott
gptkb:Michael_O._Rabin
gptkbp:introducedIn 1959
gptkbp:minimization not always unique
gptkbp:stateExplosion conversion to DFA may cause exponential growth
gptkbp:usedIn lexical analysis
pattern matching
regular expression matching
gptkbp:bfsParent gptkb:Automata_theory
gptkb:deterministic_finite_automaton
gptkbp:bfsLayer 5