< previous page page_38 next page >
Page 38
To find out what to do next, put yourself in the position of having to detect the string
aba
in a very long
input string. As a finite automaton you can only read one letter at a time, so imagine that you are
constrained to view the input string one letter at a time through a peephole. If you are reading
a b,
then you are not interested, but as soon as you read an
a
you are: you make a mental note ‘I have just
read an
a
.’ If you read a
b
next, then you get even more interested: you make a mental note ‘I have
just read
ab;
’ if instead you read an
a,
then you simply stay in the ‘I have just read an
a
’ state. The next
step is the crucial one: if you read an
a,
then you have located the string
aba,
you do not care what
letters you read next; if on the other hand you read
a b,
then it takes you back to the ‘uninterested’
state. We see now that the four states on our spine correspond to: ‘uninterested,’ ‘just read an
a,
’ ‘just
read
ab
’ and ‘success!’ The automaton we require is therefore the following one:
Our example above can be used to formulate a general principle for constructing automata that
recognise languages of the form
A
*
xA
* where .
Proposition 2.4.3
Let A be an alphabet and a string of length n. The language A
*
xA
*
can be
recognised by an automaton with n
+1
states
.
Proof The first step is to construct the spine as we did in our example. If
x
=
a
1
…an,
then this spine will
have
n
+1 states: the first one is initial, the last is terminal, and the transitions are labelled in turn
ai
for
i
=1,…,
n;
the last state also carries a loop labelled
A
.
Because we read an input string from left to right, each of these
n
+1 states is really storing which
prefix
of
x
we have read in the input: from the first state representing
ε
to the last representing
x
itself. To
work out where to put the missing transitions, suppose that we are in the state corresponding to the
prefix
y
of
x,
where
y
=
a
1…
ai
and that the next letter of the input string we read is
a
. There are two
cases to consider.
(Case 1): suppose that
a
=
ai
+1
,
that is
ya
is also a prefix of
x
. Then we simply move to the next state
to the right along the spine.
(Case 2): suppose that
a
≠
ai
+1. It is tempting to think that we have to go back to the initial state, but
this is not necessarily so. The string
ya
is not a prefix of
x;
however we can always find a
suffix
of
ya
that is a
prefix
of
x;
we do not exclude the possibility that this suffix could be
ε
. Choose the
longest
suffix
z
of
ya
that is a prefix of
x
. The transition we require is then
< previous page page_38 next page >