NFA
E632951
NFA (Nondeterministic Finite Automaton) is a theoretical model of computation used in automata theory and formal language processing to recognize regular languages, allowing multiple possible transitions for a given state and input symbol.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
automaton
ⓘ
computational model ⓘ nondeterministic finite automaton ⓘ state machine ⓘ |
| acceptingStatesSymbol | F ⓘ |
| acceptsIf | there exists at least one computation path ending in an accepting state ⓘ |
| alphabetSymbol | Σ ⓘ |
| applicationDomain |
lexical analysis
ⓘ
pattern matching ⓘ |
| canBeConvertedTo | DFA ⓘ |
| cannotRecognize | non-regular languages ⓘ |
| closureProperty |
closed under Kleene star
ⓘ
closed under complement ⓘ closed under concatenation ⓘ closed under intersection ⓘ closed under union ⓘ |
| contrastedWith | deterministic finite automaton ⓘ |
| conversionMethod | subset construction ⓘ |
| equivalentTo | DFA ⓘ |
| formalLanguageClass | regular language ⓘ |
| fullName | Nondeterministic Finite Automaton NERFINISHED ⓘ |
| hasComplexityProperty | equivalent DFA may have up to 2^n states for n-state NFA ⓘ |
| hasComponent |
finite set of states
ⓘ
input alphabet ⓘ set of accept states ⓘ start state ⓘ transition function ⓘ |
| hasProperty |
finite number of states
ⓘ
may have epsilon transitions ⓘ multiple possible next states for a state-symbol pair ⓘ nondeterministic transitions ⓘ set of accepting states ⓘ single start state ⓘ |
| hasSemantics | existential choice over transitions ⓘ |
| hasVariant |
NFA without epsilon transitions
ⓘ
epsilon-NFA ⓘ |
| introducedInContextOf | regular languages ⓘ |
| isDefinedOver | finite alphabet ⓘ |
| lessExpressiveThan |
Turing machine
NERFINISHED
ⓘ
pushdown automaton ⓘ |
| mathematicallyDefinedAs | 5-tuple (Q, Σ, δ, q0, F) ⓘ |
| recognizes | regular languages ⓘ |
| startStateSymbol | q0 ⓘ |
| stateSetSymbol | Q ⓘ |
| studiedIn | introductory theory of computation courses ⓘ |
| transitionFunctionType | Q × Σ → P(Q) ⓘ |
| usedIn |
automata theory
ⓘ
formal language theory ⓘ theoretical computer science ⓘ |
Referenced by (2)
Full triples — surface form annotated when it differs from this entity's canonical label.