L3

Theory of Computation
Nondeterministic Finite Automata (NFA)

We solve complex problems by developing a model which help us thinking more
clearly about solving them and sometimes simplify their solution methods. The
problem is how to model them in the study of computation. We define a model as
a collection of precisely stated interacting ideas that focus on a particular aspect or
part of our subject matter. For many computing systems, we may have unknown
inputs, unknown internal parameters or to complex components to model. In DFA,
some states of the machine can not be determined uniquely by the input symbol
and the present state. It means that the path DFA follows is not determined by the
input string. This leads to the idea of nondeterministic finite automation (NFA). It is
defined by the quintuple (Q, Σ, δ, q0 , F) , where, Q be a finite set of states, Σ be an
input alphabet, δ be a transition function, q0Q be a start state and F ⊆ Q be a set
of final states. It has the ability to be in several states at once. Transition from a
state on an input symbol can be to any set of states, i.e. δ :Q x (Σ {}) 2Q . In an NFA,
the set (q, λ) may be empty. This means that there is no transition defined for this
specific input symbol λ. We accept if any sequence of choices leads to a final state.
This does not imply that DFA is probabilistic. To be probabilistic means that the
state transitions should have input along with some probability distribution whose
sum should be 1.0. If it is more than 1.0 then it is called a weighted DFA. 1
Nondeterminism may be viewed as a kind of parallel computation wherein multiple
processes or threads can be running concurrently. When an NFA splits to follow
several choices, it corresponds to process forking into several children each
proceeding separately. If at least one of these processes are accepted then entire
computation is accepted. This variation is fully justified because it does not
increasing the computational power of automata and is easier to design. In order
for a DFA to be NFA the following condition must apply for some state q and input
x, i.e. | (q, x) | > 1.
δ can be extended to process strings as follows:
Basis: δ(q, ) = {q}
Induction: δ(q, wa) = the union over all states p in δ(q, w) of δ(p, a)
A string w is accepted by an NFA if δ(q0, w) contains at least one final state. The
language of the NFA is the set of strings it accepts. It is always possible to convert a
NFA to a DFA. Some conversion may require exponentially more states in DFA.
is used for an empty string, i.e. a string whose length is zero.
2
Example (1) There are two transitions labeled a out of q0 This is NFA. The language
accepted by it is L(A) = { xn | n There are two accept states { q3 , q5 }.
Example (2)
Suppose we are in q1 and input is 1. After reading this symbol, NFA splits into
multiple copies of itself and follows all the possibilities in parallel. Each copy of NFA
takes one of the possible ways to proceed and continue as before. If there are
subsequent choices, NFA splits again. If the next input symbol does not appear on
any of the arrows exiting the state occupied by a copy of NFA, that copy dies along
with the branch of the computation associated with it. Finally, if any one of these
copies of the NFA is in an accept state at the end of the input, the NFA accepts 3 the
input string. In the above diagram, state q1 has one exiting arrow for 0 but it has
two for 1. q2 has 1 for 0 but non for 1. It also has a label with . Thus, in an NFA,
a state may have zero, one or many exiting arrows for each alphabet symbol.
Another way to think of NFA as a tree of possibilities. The root of the tree
corresponds to start of the computation. Consider 010110 and process it by
NFA given above. It accepts all strings that contain either 101 or 11 as a
substring.
4
Example (3) Consider the following NFA
It has a -transition. Some transitions, such as, δ(q2, 0) is unspecified in the graph.
This is to be interpreted as a transition to the empty set, that is, δ(q2, 0) = . The NFA
accepts strings , 1010, and 101010, but not 110 and 10100. Note that for 10 there
are two alternative walks, one leading to q0, the other to q2. Even though q2 is not a
final state, the string is accepted because one walk leads to a final state.
Example (4) which of the strings 00, 01001, 10010, 000, 0000 are accepted by the
following NFA.
5
Walk.
Let us define what we mean by a walk in a graph. A sequence of edges in a graph is
said to be a walk from vi to vn if we have (vi , vj) , (vj , vk) , …., (vm , vn). The length of
the walk is the total number of edges in going from vi to vn . A walk in which no
edge is repeated is said to be a path. It is a simple path if no vertex is repeated.
Example (5)

L3

Uploaded by

Copyright:

Available Formats

L3

Uploaded by

Document Information

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

L3

Uploaded by

Copyright:

Available Formats

Theory of Computation

Nondeterministic Finite Automata (NFA)

You might also like