Back to DFSA's

The tutorial six exercise looks challenging, particularly because I've been taking a longer break than intended due to the long weekend. I will attempt question 1.

Devise a DFSA that accepts the language of finite binary strings whose length is a multiple of 3. Explain why it is correct.

I assume any DFSA that accepts this language, must have 3 states. I say this because the question should be reworded as the following:

Devise a DFSA that accepts the language L = {x |  len(x)%3==0}. Explain why it is correct.

We can see that this function f(x) = len(x)%3 can have only 3 possible outcomes for an arbitrary string x and a corresponding arbitrary integer i:

 

          1 iff len(x) = 3i+1

f(x) =  2 iff len(x) = 3i +2

      0 iff len(x) = 3i

 

Because of this close relationship to f(x), I assume the DFSA will have 3 states. As to what they will be, I shall post more on that later.

 

Thanks for reading.