Nondeterministic finite automaton

Nondeterministic finite automaton

In automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is uniquely determined by its source state and input symbol, and * reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article.

Comment
enIn automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is uniquely determined by its source state and input symbol, and * reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article.
Depiction
NFAexample.svg
NFASimpleExample.svg
NFASimpleExample Runs10.gif
NFASimpleExample Runs1011.gif
Relatively small NFA.svg
Thompson-or.svg
Has abstract
enIn automata theory, a finite-state machine is called a deterministic finite automaton (DFA), if * each of its transitions is uniquely determined by its source state and input symbol, and * reading an input symbol is required for each state transition. A nondeterministic finite automaton (NFA), or nondeterministic finite-state machine, does not need to obey these restrictions. In particular, every DFA is also an NFA. Sometimes the term NFA is used in a narrower sense, referring to an NFA that is not a DFA, but not in this article. Using the subset construction algorithm, each NFA can be translated to an equivalent DFA; i.e., a DFA recognizing the same formal language.Like DFAs, NFAs only recognize regular languages. NFAs were introduced in 1959 by Michael O. Rabin and Dana Scott, who also showed their equivalence to DFAs. NFAs are used in the implementation of regular expressions: Thompson's construction is an algorithm for compiling a regular expression to an NFA that can efficiently perform pattern matching on strings. Conversely, Kleene's algorithm can be used to convert an NFA into a regular expression (whose size is generally exponential in the input automaton). NFAs have been generalized in multiple ways, e.g., , finite-state transducers, pushdown automata, alternating automata, ω-automata, and probabilistic automata.Besides the DFAs, other known special cases of NFAsare unambiguous finite automata (UFA)and self-verifying finite automata (SVFA).
Is primary topic of
Nondeterministic finite automaton
Label
enNondeterministic finite automaton
Link from a Wikipage to another Wikipage
Alphabet (computer science)
Alternating finite automaton
Automata theory
Big O notation
Category:Finite automata
Closed under
Dana Scott
Deterministic finite automaton
Empty string
File:NFAexample.svg
File:NFASimpleExample.svg
File:NFASimpleExample Runs10.gif
File:NFASimpleExample Runs1011.gif
File:Relatively small NFA.svg
File:Thompson-or.svg
Finite-state machine
Finite-state transducer
Formal language
Function (mathematics)
Input symbol
Introduction to Automata Theory, Languages, and Computation
Kleene's algorithm
Kleene closure
Michael O. Rabin
Nondeterministic algorithm
Nondeterministic Turing machine
N-tuple
Power set
Powerset construction
Probabilistic automaton
PSPACE
Pushdown automaton
Recursion (computer science)
Regular expression
Regular language
Regular languages
Self-verifying finite automaton
Set (mathematics)
Set data structure
Set union
State (computer science)
State transition function
State transition table
Subset construction algorithm
Theory of computation
Thompson's construction
Thompson's construction algorithm
Two-way nondeterministic finite automaton
Unambiguous finite automaton
Ω-automaton
SameAs
4oHmE
Automa a stati finiti non deterministico
Autómata finito no determinista
Automate fini non déterministe
Autòmat finit no determinista
Deterministik olmayan sonlu durum makinesi
Ikke-deterministisk endelig tilstandsmaskin
m.02 w6j
Máquina de estados finitos não determinística
Nedeterministički konačni automat
Nedeterministički konačni automat
Nedeterministički konačni automat
Nemdeterminisztikus véges állapotú gép
Nichtdeterministischer endlicher Automat
Niedeterministyczny automat skończony
Nondeterministic finite automaton
Q617295
Μη ντετερμινιστικό πεπερασμένο αυτόματο
Недетерминированный конечный автомат
Недетерминистички коначни аутомат
Недетермінований скінченний автомат
אוטומט סופי לא דטרמיניסטי
آلة محدودة الحالات غير قطعية
اتوماتون تعیین‌ناپذیر متناهی
非決定性有限オートマトン
非确定有限状态自动机
비결정적 유한 상태 기계
Subject
Category:Finite automata
Thumbnail
Relatively small NFA.svg?width=300
WasDerivedFrom
Nondeterministic finite automaton?oldid=1121857081&ns=0
WikiPageLength
29717
Wikipage page ID
653406
Wikipage revision ID
1121857081
WikiPageUsesTemplate
Template:Clarify span
Template:Color
Template:Diagonal split header
Template:Formal languages and grammars
Template:Isbn
Template:Reflist
Template:Rp
Template:Short description
Template:Strings