NFA

E632951

automaton computational model nondeterministic finite automaton state machine

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.

Try in SPARQL Jump to: Surface forms Disambiguation Statements Elicitation Referenced by

All labels observed (3)

Label	Occurrences
NFA canonical	2
Nondeterministic Finite Automaton	1
position-based NFA construction	1

How this entity was disambiguated

This entity first appeared as the object of triple T6991396 — resolving that mention is where its identity was fixed. The disambiguator weighed these candidate entities and picked the highlighted one (or “None”, minting a new entity). This is how homonymy is resolved: the same surface form can point to different entities.

NED1 Entity disambiguation (via context triple) gpt-5-mini-2025-08-07

Target entity: NFA
Context triple: [Thompson's algorithm for regular expression matching, output, NFA]

A. NFA
NFA is a common abbreviation for the National Firearms Act, a U.S. federal law regulating certain classes of firearms and related devices.
B. DFA
DFA is an online advertising management and ad-serving platform originally developed by DoubleClick and later integrated into Google's marketing and ad technology stack.
C. DFSA
The DFSA is the independent financial services regulator for the Dubai International Financial Centre, overseeing and enforcing standards for banking, securities, insurance, and related financial activities.
D. DFAE
DFAE is the French abbreviation for Switzerland’s Federal Department of Foreign Affairs, the government ministry responsible for the country’s foreign policy and international relations.
E. FSM
FSM is the three-letter ISO 3166-1 alpha-3 country code for the Federated States of Micronesia, a Pacific island nation.
F. None of above. chosen
G. Unsure - the case is ambiguous/there is not enough information to decide.

NED2 Entity disambiguation (via description) gpt-5-mini-2025-08-07

Target entity: NFA
Target entity description: 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.

A. NFA
NFA is a common abbreviation for the National Firearms Act, a U.S. federal law regulating certain classes of firearms and related devices.
B. DFA
DFA is an online advertising management and ad-serving platform originally developed by DoubleClick and later integrated into Google's marketing and ad technology stack.
C. DFSA
The DFSA is the independent financial services regulator for the Dubai International Financial Centre, overseeing and enforcing standards for banking, securities, insurance, and related financial activities.
D. DFAE
DFAE is the French abbreviation for Switzerland’s Federal Department of Foreign Affairs, the government ministry responsible for the country’s foreign policy and international relations.
E. FSM
FSM is the three-letter ISO 3166-1 alpha-3 country code for the Federated States of Micronesia, a Pacific island nation.
F. None of above. chosen

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 ⓘ linked to: NFA
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 ⓘ 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 ⓘ

How these facts were elicited

Referenced by (4)

Full triples — surface form annotated when it differs from this entity's canonical label.

Thompson's algorithm for regular expression matching → output → NFA ⓘ

Thompson's algorithm → outputType → NFA ⓘ

NFA → fullName → Nondeterministic Finite Automaton ⓘ

linked to: NFA

Glushkov construction → alsoKnownAs → position-based NFA construction ⓘ