Chapter 3: The Theory of Automata iii, 77
3.5 ACCEPTABILITY OF A STRING BY A FINITE
AUTOMATON
Definition 3.4 A stling x is accepted by a finite automaton
M = (Q, .L 8, C/o' F)
if D(qo, x) =q for some q E F.
This is basically the acceptability of a string by the final state.
Note: A final state is also called an accepting state.
EXAMPLE 3.5
Consider the finite state machine whose u'unsition function 0 is given by Table 3.1
in the form of a transition table. Here, Q = {CI(), qi. q2> q3}, L = {O, I},
F = {qo}. Give the entire sequence of states for the input string 110001.
TABLE 3.1
State
Transition Function Table for Example 3.5
Input
o
Solution
(--:\
-7 ~/
q,
q2
q3
Hence.
l
l
8{qo, 110101) = D(C/I.IOIOI)
I
..v
= 0(% 0101)
l
= D(q~, 101)
l
= 8(q3,Ol)
l
= D(q], 1)
= 8(qo, ..1\)
J
1
a
1
a
j
qo ~ qj ~ qo ~ q~ ~ q3 ~ qj ~ qo
The symbol l indicates that the current input symbol is being processed by the
machine.