Mathematical Foundation of Computer Science

DHARM

INTRODUCTION TO LANGUAGES AND FINITE AUTOMATA 183

Thus, δ-head is the transition function which is a mapping of a state (∈ Q) and a string
of input symbols (∈ Σ*) to power set of Q or P(Q).

7.3.4 Properties of δ-head

Let NFA N is in current state q and its tape contains a string x shown in Fig. 7.18 then,
behavior of δ-head over string x is determine as follows:

............x............

q NFA
N
Fig. 7.18
I. If x is a null string (∈) then,
δ$(q, ∈) = {q};
such that if input symbol is a null string then state remains unchanged.
II. If string x is composed of two/more symbols, then decompose string x into substring
y and a single symbol a such that, x = y a then,
$δ(q, x) = δ$(q, y a);
= δ( δ$(q, y), a) (using definition of δ and δ$)
Further, assume that δ$(q, y) = {p 1 , p 2 , p 3 , ......., pi}, that is, from the state q NFA
might be reaches to these possible states after consuming the string y, that is shown in
Fig. 7.19.

q

y

y

y

p 1

p 2

pi

a

a

: :

:

r 1

r 2

rj

a

Fig. 7.19

Thus, δ($δ(q, y), a) = δ({p 1 , p 2 , p 3 , ......., pi}, a);

= δ(p 1 , a) ∪ δ(p 2 , a) ∪ δ(p 3 , a) ∪ ............∪ δ(pi, a)