Mathematical Foundation of Computer Science

DHARM

178 MATHEMATICAL FOUNDATION OF COMPUTER SCIENCE

Let automata M is in state q, after reading the string x (tape cells entries contains the
string x) automaton reaches to state p. This situation is shown in Fig. 7.14 (a) and (b).

x M q x M p

()a

()b
Fig. 7.14
So, the behavior of δ-head over string x is given as,
δ$ (q, x ) = p;
where x is a string might be of single alphabet.

7.2.3.2 Properties of δ-head

From any state q,
I. If input string is a null string (∈) then automaton state remains unchanged i.e.,
$δ (q, ∈) = q, ∀ q ∈ Q
If the string is of single symbol string or of length one then δ-head and δ are same i.e.,
assume string x = a then,
$δ (q, x) = δ (q, a) = p;

x

M

q

x

M

p

Þ

II. If string is not of single symbol string then assume string x is formed by a alphabet a

and substring y, i.e., x = ay, then

$δ (q, a y) = $δ (δ (q, a), y) ;

For example if x = 1011 then a = 1 and remaining string y = 011.