Non-deterministic Finite Automata

A nondeterministic finite automata is a quintuple <Q,å,d,q0,F>; where:

• Q is a finite set of states;
• å is a finite set of input symbols;
• d is the, possibly partial, transition function
• d:A transition function that takes a state in Q and an input symbol in I as arguments and returns a subset of Q.
•  q0 element of Q is called the initial state;
• F contained in Q is called the set of final states.

         The above definition states that a nondeterministic finite automaton  can exhibit several different transition sequences for a given state and a given input.

An input string is accepted by a nondeterministic finite automaton if and only if at least one of the possible transition sequences, defined by the input, leads to a final state.

          As language recognizer devices, nondeterministic automata are not more powerful than their deterministic counterpart, indeed they accept the same class of languages, that is to say they are equivalent. However, they are very often more convenient to use. In many cases, the most direct formalization of a problem is in terms of a nondeterministic automaton.

Examples:

Q)   Construct an NFA to accept all strings terminating in 01   Ans1

Q)   Construct an NFA to accept those strings containing three consecutive zeroes  Ans:2

Ans:1

Ans:2

       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. This distinguishes it from thedeterministic finite automaton (DFA), where the next possible state is uniquely determined. Although the DFA and NFA have distinct definitions, it may be shown in the formal theory that they are equivalent, in that, for any given NFA, one may construct an equivalent DFA, and vice-versa: this is the powerset construction. Both types of automata recognize only regular languages. Non-deterministic finite state machines are sometimes studied by the name subshifts of finite type. Non-deterministic finite state machines are generalized by probabilistic automata, which assign a probability to each state transition.

Formal Definition

       Two similar types of NFAs are commonly defined: the NFA and the NFA with ε-moves. The ordinary is defined as a 5-tuple, (Q, Σ, T, q₀,F), consisting of

• a finite set of states Q
• a finite set of input symbols Σ
• a transition function T : Q × Σ → P(Q).
• an initial (or start) state q₀ ∈ Q
• a set of states F distinguished as accepting (or final) states F ⊆ Q.

Here, P(Q) denotes the power set of Q. The NFA with ε-moves (also sometimes called NFA-epsilon or NFA-lambda) replaces the transition function with one that allows the empty string ε as a possible input, so that one has instead

T : Q × (Σ ∪{ε}) → P(Q).

It can be shown that ordinary NFA and NFA with epsilon moves are equivalent, in that, given either one, one can construct the other, which recognizes the same language.