   DESKTOP

# Non-Deterministic Finite Automata

7/24/2010 8:00:17 PM
##### 2.2 NON-DETERMINISTIC FINITE AUTOMATA If the basic finite automata model is modified in such a way that from a state on an input symbol zero, one or more transitions are permitted, then the corresponding finite automata is called a "non-deterministic finite automata" (NFA). Therefore, an NFA is a finite automata in which there may exist more than one paths corresponding to x in Σ* (because zero, one, or more transitions are permitted from a state on an input symbol). Whereas in a DFA, there exists exactly one path corresponding to x in Σ*. Hence, an NFA is nothing more than a finite automata: in which δ defines mapping from Q � Σ to 2Q (to take care of zero, one, or more transitions). For example, consider the finite automata shown below: where: The transition diagram of this automata is: Figure 1: Transition diagram for finite automata that handles several transitions. ### Acceptance of Strings by Non-deterministic Finite Automata Since an NFA is a finite automata in which there may exist more than one path corresponding to x in Σ*, and if this is, indeed, the case, then we are required to test the multiple paths corresponding to x in order to decide whether or not x is accepted by the NFA, because, for the NFA to accept x, at least one path corresponding to x is required in the NFA. This path should start in the initial state and end in one of the final states. Whereas in a DFA, since there exists exactly one path corresponding to x in Σ*, it is enough to test whether or not that path starts in the initial state and ends in one of the final states in order to decide whether x is accepted by the DFA or not. Therefore, if x is a string made of symbols in Σ of the NFA (i.e., x is in Σ*), then x is accepted by the NFA if at least one path exists that corresponds to x in the NFA, which starts in an initial state and ends in one of the final states of the NFA. Since x is a member of Σ* and there may exist zero, one, or more transitions from a state on an input symbol, we define a new transition function, δ1, which defines a mapping from 2Q � Σ* to 2Q; and if δ1 ({q0},x) = P, where P is a set containing at least one member of F, then x is accepted by the NFA. If x is written as wa, where a is the last symbol of x, and w is a string made of the remaining symbols of x then: For example, consider the finite automata shown below: where: If x = 0111, then to find out whether or not x is accepted by the NFA, we proceed as follows:  Since δ1 ({q0}, 0111) = {q1, q2, q3}, which contains q3, a member of F of the NFA—, hence, x = 0111 is accepted by the NFA. Therefore, if M is a NFA, then the language accepted by NFA is defined as: L(M) = {x | δ1 ({q0} x) = P, where P contains at least one member of F }. var sc_project=11388663; var sc_invisible=1; var sc_security="7db37af3"; var scJsHost = (("https:" == document.location.protocol) ? "https://secure." : "http://www."); document.write("<sc"+"ript type='text/javascript' src='" + scJsHost+ "statcounter.com/counter/counter.js'></"+"script>"); Other

 Top 10 REVIEW - First look: Apple Watch

- 3 Tips for Maintaining Your Cell Phone Battery (part 1)

- 3 Tips for Maintaining Your Cell Phone Battery (part 2)     