display | more...
Proposition. Let L=L17 be the set of decimal representations of numbers divisible by 17 (the alphabet is {0,1,...,9}). Then L is a regular language.

Proof. We construct a FSA (with 17 states) recognising L. For simplicity of construction, we shall also recognise numbers with leading zeroes (and the empty string) as being divisible by 17; fixing this is left as an exercise for the reader. Our states shall be {r0, ..., r16}; after reading a word w, we shall be in state r_j, where j = w modulo 17. Clearly, for this to work, the initial state and the sole accepting state must be r0.

Consider a word w with j = w modulo 17. If a is one of the digits {0, 1, ..., 9}, then the string wa will represent the number 10*w+a; dividing by 17, we see that the remainder is (10*w+a) modulo 17 = (10*j+a) modulo 17. We can compute this once and for all (for instance, when w is divisible by 17 with remainder 3, tacking on a 1 at the end brings us to remainder 3*10+1 modulo 17 = 14; you might need to look at 20=17+3 and 201=17*11+14 to be convinced). In other words, for every 0≤j<17 and 0≤a<10, we need a transition from rj to r_10*j+a mod 17.

It is now easy to see that the resulting automaton, with 17 states and 170 transitions, recognises L. It is interesting to note the close parallel to the Myhill / Nerode Theorem; a simple modification of the above argument yields that 17 states are required in any automaton recognising L.

Log in or register to write something here or to contact authors.