|
In the theory of computation, a nondeterministic finite state machine or nondeterministic finite automaton (NFA) is a finite state machine where for each pair of state and input symbol there may be several possible next states. Non-deterministic finite state machines are sometimes studied by the name subshifts of finite type. The theory of computation is the branch of computer science that deals with whether and how efficiently problems can be solved on a computer. ...
Fig. ...
In mathematics, subshifts of finite type are used to model dynamical systems, and in particular are the objects of study in symbolic dynamics and ergodic theory. ...
Intuitive explanations
A NFA consumes a string of input symbols. For each input symbol it transforms to a new state until all input symbols have been consumed.
It is non-deterministic because it may encounter a situation where there are multiple transformations out of a state by using the same letter. For NFA-lambda (also known as NFA-epsilon) it is also possible to transform to a new state without consuming any input symbols. For example, if it is in state 1, with the next input symbol an a, it can move to state 2 without consuming any input symbols and can enter state 3 by consuming an a. It is unable to determine the correct state to enter, or rather it enters both states.
Transformations to new states without consuming an input symbol are called lambda transitions or epsilon transitions. They are usually labelled with the Greek letter λ or ε.
When the last input symbol is consumed the NFA accepts if and only if there is some set of transitions it could make that will take it to an accepting state. Equivalently, it rejects if no matter what choices it makes it would not end in an accepting state.
Formal definition A nondeterministic finite state automaton (NFA) is a 5-tuple, (S, Σ, T, s0, A), consisting of In mathematics, a tuple is a finite sequence of objects (a list of a limited number of objects). ...
- a finite set of states (S)
- a finite set of input symbols (Σ)
- a transition function (T : S × (Σ ∪{ε}) → P(S)).
- a set of states s0 distinguished as initial (or start) states (s0 ⊆ S)
- a set of states A distinguished as accepting (or final) states (A ⊆ S)
where P(S) is the power set of S, ε is the empty string, and Σ is the input symbol alphabet. In mathematics, a set can be thought of as any collection of distinct things considered as a whole. ...
Partial plot of a function f. ...
In mathematics, given a set S, the power set (or powerset) of S, written or 2S, is the set of all subsets of S. In axiomatic set theory (as developed e. ...
In computer programming and some branches of mathematics, strings are sequences of various simple objects. ...
Let M be an NFA such that M = (S, Σ, T, s0, A), and X be a string over the alphabet Σ. M accepts the string X if there exist both a representation of X of the form x1x2 ... xn, xi ∈ (Σ ∪{ε}), and a sequence of states r0,r1, ..., rn, ri ∈ S, meeting the following conditions:
- r0 ∈ s0
- ri ∈ T(ri-1, xi ), for i = 1, ..., n
- rn ∈ A.
The machine starts in an arbitrary initial state and reads in a string of symbols from its alphabet. The automaton uses the transition relation T to determine the next state using the current state, and the symbol just read or the empty string. However, "the next state of an NFA depends not only on the current input event, but also on an arbitrary number of subsequent input events. Until these subsequent events occur it is not possible to determine which state the machine is in" [1]. If, when the automaton has finished reading, it is in an accepting state, the NFA is said to accept the string, otherwise it is said to reject the string.
The set of all strings accepted by an NFA is the language the NFA accepts. This language is a regular language. A regular language is a formal language (i. ...
For every NFA a deterministic finite state machine (DFA) can be found that accepts the same language. Therefore it is possible to convert an existing NFA into a DFA for the purpose of implementing a (perhaps) simpler machine. This can be performed using the powerset construction which may lead to an exponential rise in the number of necessary states. In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. ...
In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. ...
In the theory of computation, the powerset construction is a standard method for converting a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) which recognizes the same formal language. ...
Implementation There are many ways to implement a NFA: - Convert to the equivalent DFA. In some cases this may cause exponential blowup in the size of the automaton and thus auxiliary space proportional to the number of states in the NFA (as storage of the state value requires at most one bit for every state in the NFA)
- Keep a set data structure of all states which the machine might currently be in. On the consumption of the last input symbol, if one of these states is a final state, the machine accepts the string. In the worst case, this may require auxiliary space proportional to the number of states in the NFA; if the set structure uses one bit per NFA state, then this solution is exactly equivalent to the above.
- Create multiple copies. For each n way decision, the NFA creates up to n − 1 copies of the machine. Each will enter a separate state. If, upon consuming the last input symbol, at least one copy of the NFA is in the accepting state, the NFA will accept. (This, too, requires linear storage with respect to the number of NFA states, as there can be one machine for every NFA state.)
- Explicitly propagate tokens through the transition structure of the NFA and match whenever a token reaches the final state. This is sometimes useful when the NFA should encode additional context about the events that triggered the transition. (For an implementation that uses this technique to keep track of object references have a look at Tracematches.)
In computer science, the set is a collection of certain values without any particular order. ...
Example The following example explains a NFA M, with a binary alphabet, which determines if the input contains an even number of 0s or an even number of 1s.
M = (S, Σ, T, s0, A) where
- Σ = {0, 1},
- S = {S0, S1, S2, S3, S4},
- s0 = {S0},
- A = {S1, S3}, and
- The transition function T can be defined by this state transition table:
| 0 | 1 | ε | | S0 | {} | {} | {S1, S3} | | S1 | {S2} | {S1} | {} | | S2 | {S1} | {S2} | {} | | S3 | {S3} | {S4} | {} | | S4 | {S4} | {S3} | {} | The state diagram for M is: In Automata Theory, a state transition table is a table describing the transition function T of a finite automaton. ...
State diagrams are used to graphically represent finite state machines. ...
-
 M can be viewed as the union of two DFAs: one with states {S2, S1} and the other with states {S3, S4}. This is an example of a NFA state diagram that I made using Visio. ...
In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. ...
The language of M can be described by the regular language given by this regular expression: A regular language is a formal language (i. ...
In computing, a regular expression (abbreviated as regexp or regex, with plural forms regexps, regexes, or regexen) is a string that describes or matches a set of strings, according to certain syntax rules. ...
See also In quantum computing, quantum finite automata or QFA are a quantum analog of probabilistic automata. ...
In the theory of computation, a deterministic finite state machine or deterministic finite automaton (DFA) is a finite state machine where for each pair of state and input symbol there is one and only one transition to a next state. ...
References - Michael Sipser. Introduction to the Theory of Computation. PWS, Boston. 1997. ISBN 0-534-94728-X. Section 1.2: Nondeterminism, pp.47–63.
|
Feeds |
Contact