non-deterministic finite automaton

URI: https://gptkb.org/entity/non-deterministic_finite_automaton
GPTKB entity
Statements (28)
Predicate Object
gptkbp:instanceOf Technical Machine
gptkbp:abbreviation gptkb:NFA
gptkbp:allows regular language
gptkbp:canHaveEpsilonTransitions true
gptkbp:canTransitionToMultipleStates true
gptkbp:convertedTo gptkb:deterministic_finite_automaton
gptkbp:equivalentTo gptkb:deterministic_finite_automaton
gptkbp:field automata theory
theoretical computer science
gptkbp:hasAcceptStates set of accept states
gptkbp:hasLanguageRecognitionPower regular languages
gptkbp:hasStartState start state
gptkbp:hasStateExplosionProblem true
gptkbp:hasSubsetConstruction powerset construction
gptkbp:hasTransitionFunction transition function
https://www.w3.org/2000/01/rdf-schema#label non-deterministic finite automaton
gptkbp:includesState set of states
gptkbp:inputAlphabet finite alphabet
gptkbp:introduced gptkb:Dana_Scott
gptkb:Michael_O._Rabin
gptkbp:introducedIn 1959
gptkbp:isLessEfficientThan deterministic finite automaton (for simulation)
gptkbp:isMathematicalModelOf computation
gptkbp:usedIn lexical analysis
pattern matching
regular expression matching
gptkbp:bfsParent gptkb:Technical_Machine
gptkbp:bfsLayer 4