Mathematical Foundation of Computer Science

DHARM

182 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

l More state transitions means, there is the possibility of two/more transitions from
a state on that single symbol or there are 2/more transitions arc exit from that
state.
So a NFA can be defined by these five tuples by,
N = (Q, Σ, δ, q 0 , F)
where transition function (δ) is the mapping of a state with an input symbol to power set of Q,
it means that function returns a state that will be in the power set of state Q.
δ: Q × S → P(Q)
Note. Transition function returns the state/s that is in power set of Q, so set of final state F is also
the subset of power set of Q. Power set includes all subset of Q including Φ (no state element). Φ defines
no state transition on any symbol.
Why δ returns the state that is in power set, the reason is due to dynamic nature of automata NFA.
The transition arc on single symbol fall on either in one state(qi)/two state (qi, qj)/more states(qi,.........
ql) or possibly no state transition (Φ). These possibilities of set of states are included only in the power set
of Q.

7.3.2 Representation

The representation of a NFA is similar to a DFA representation that is, we can represent the

NFA either through a state diagram or through transition table (TT). I personally feel that

state diagram representation provides a comprehensive view of the automata at a moment. So

I always prefer state diagram over transition table representation. In the Fig. 7.17 we construct

a NFA that accepts all the strings which contains the substring 011 or a pattern of symbols 011.

q 0 q 2 q 3

1

q 1

0 1

0, 1 0, 1

N

Fig. 7.17

Above NFA N can be represented by following tuples,

N = ({q 0 , q 1 , q 2 , q 3 }, {0, 1}, δ, q 0 , {q 3 })

And transition functions δ are define as follows,

· δ(q 0 , 0) = {q 0 } and δ (q 0 , 0) = {q 1 };

So, δ(q 0 , 0) = {q 0 , q 1 } [∴ There are two exit arcs from a state q 0 on symbol 0]

· δ(q 0 ,1) = {q 0 };

· δ(q 1 , 0) = Φ; [∴ no transition is defined on input symbol 0 from state q 1 ]

· δ(q 1 , 1) = {q 2 };

· δ(q 2 , 0) = Φ;

· δ(q 2 , 1) = {q 3 };

· δ(q 3 , 0) = {q 3 };

· δ(q 3 , 1) = {q 3 };

7.3.3 δ-head

Like δ-head of DFA, δ-head of NFA defines the behavior of the transition function over an
arbitrary string. Assume that if the string is defined over alphabet Σ, then set of all possible
strings are Σ. The δ-head is defined as,
δ$^ : Q × Σ → P(Q)