2.3 TRANSFORMING NFA TO DFA

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 & pound ; * (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 2 ^Q (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 2.2: Transition diagram for finite automata that handles several transitions.

2.2.1 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, ₁ , which defines a mapping from 2 ^Q — * to 2 ^Q ; and if ₁ ({ q }, 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 ₁ ({ q }, 0111) = { q ₁ , q ₂ , q ₃ }, which contains q ₃ , 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 ₁ ({ q } x ) = P , where P contains at least one member of F }.