More on Regular Sets
Here is another example of a regular set that is a little harder than the example given last time. Consider the set $$\left\{ {x \in {{\left\{ {0,1} \right\}}^*}|x{\mkern 1mu} represents{\mkern 1mu} a{\mkern 1mu} multiple{\mkern 1mu} of{\mkern 1mu} three{
- PDF / 497,909 Bytes
- 6 Pages / 439.37 x 666.142 pts Page_size
- 45 Downloads / 265 Views
{x E {O, 1} * I x represents a multiple of three in binary}
(4.1)
(leading zeros permitted, f represents the number 0). For example, the following binary strings represent multiples of three and should be accepted:
Binary
Decimal equivalent
o
o 3
11 110
6 9
1001
12 15 18
1100 1111 10010
Strings not representing multiples of three should be rejected. Here is an automaton accepting the set (4.1): -+
OF 1 2
o
1
2 1
0 2
1fT1
D. C. Kozen, Automata and Computability © Springer Science+Business Media, Inc. 1997
20
Lecture 4
The states 0, 1, 2 are written in boldface to distinguish them from the input symbols 0, 1.
d_1_x__O_yo1
°
1
°
In the diagram, the states are 0, 1, 2 from left to right. We prove that this automaton accepts exactly the set (4.1) by induction on the length of the input string. First we associate a meaning to each state:
if the number represented by the string scanned so far is l mod 3 1 mod 3 2 mod 3
then the machine will be in state
°
°
1 2
Let #x denote the number represented by string x in binary. For example,
#e=O, #0=0,
#11 =3, #100
=4,
and so on. Formally, we want to show that for any string x in {O, 1}*,
6(0, x) 6(0, x) 6(0, x)
= °iff #x == °mod 3, = 1 iff #x == 1 mod 3,
(4.2)
= #x mod 3.
(4.3)
= 2 iff #x == 2 mod 3,
or in short,
6(0, x)
This will be our induction hypothesis. The final result we want, namely (4.2), is a weaker consequence of (4.3), but we need the more general statement (4.3) for the induction hypothesis. We have by elementary number theory that
#(xO)
= 2(#x) + 0,
1 Here a mod n denotes the remainder when dividing a by n using ordinary integer division. We also write a == b mod n (read: a is congruent to b modulo n) to mean that a and b have the same remainder when divided by nj in other words, that n divides b - a. Note that a == b mod n should be parsed (a == b) mod n, and that in general a == b mod n and a b mod n mean different things. For example, 7 == 2 mod 5 but not 7 = 2 mod 5.
=
More on Regular Sets
#(x1)
21
= 2(#x) + 1,
or in short,
#(xc)
= 2(#x) + c
(4.4)
for c E {O,1}. From the machine above, we see that for any state q E {O, 1, 2} and input symbol c E {O, 1},
6(q, c)
= (2q+c) mod 3.
(4.5)
This can be verified by checking all six cases corresponding to possible choices of q and c. (In fact, (4.5) would have been a great way to define the transition function formally-then we wouldn't have had to prove it!) Now we use the inductive definition of 8 to show (4.3) by induction on Ixl. Basis
For x
= 10, 8(0,10)=0 =#10
= #€ mod 3.
by definition of 6 since #€
=0
Induction step
Assuming that (4.3) is true for x E {O, 1} *, we show that it is true for xc, where c E {O,1}.
8(0, xc) = 6(8(0,x),c) =6(#x mod 3,c) = (2(#x mod 3) + c) mod 3 = (2(#x) + c) mod 3
= #xcmod3
definition of 8 induction hypothesis by (4.5) elementary number theory by (4.4).
Note that each step has its reason. We used the definition of 6, which is specific to this automaton; the definition of 8from 6, which is the same for all automat
Data Loading...
