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
- 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
- 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