Designing a DFA (alphabet 'a' and 'b') : The number of 'a' in the string must be a multiple of 3, and the string does not contain 'aba'

Question

Here is the problem:

And here is my line of reasoning when I first came upon it:

• This one seems difficult
• Finding a regular expression for it seems tricky, so i cannot follow this path to convert the regular expression to a DFA
• So I decided to solve the first part of the problem: Accept a string whose number of 'a' is a multiple of 3. This is quite easy, you just need 3 states: 1,2,3 with 1 as the start state, if there is an input 'a', you go to the next one, if it's 'b' you stay at that state, and the start state is also the finishing state. But here in this exercise, these 3 states would actually be 3 'big' states. Then the problem becomes designing the internals of these 'big states and how they interact.

I had no choice but to use guesswork in order to arrive at a solution. Here is what I came up with (1,2,3 are finishing states, 3 is the start state, and also 7 and 9 both goes to 1 if an input 'a' is received): I also used DFA minimization on this one, and found out that it is already minimal. However, the textbooks gives another solution:

But I don't understand how it is correct! I just can't figure it out :(. And I don't even know if my solution is 100% correct. Please help me, thank you very much :)

Answer 1

Your answer seems to be correct. I haven't carefully proved it, but the logic is fairly clear. Furthermore, I wrote a Python program to test it:

def accepts(transitions,initial,accepting,s):
    state = initial
    for c in s:
        state = transitions[state][c]
    return state in accepting

dfa = {1:{'a':4, 'b':2},
       2:{'a':10, 'b':3},
       3:{'a':4, 'b':3},
       4:{'a':7, 'b':5},
       5:{'a':10, 'b':6},
       6:{'a':7, 'b':6},
       7:{'a':1, 'b':8},
       8:{'a':10, 'b':9},
       9:{'a':1, 'b':9},
       10:{'a':10, 'b':10}}

def dfaTest(s):
    return accepts(dfa,3,{1,2,3},s)

def valid(s):
    return s.count('a') % 3 == 0 and not 'aba' in s

import random

tests = [''.join(random.choice(['a','b']) for j in range(100)) for i in range(1,1001)]

print(all(valid(s) == dfaTest(s) for s in tests))

The operation of the function accepts is explained in this answer. I tailored it to match your diagram. To stress-test it I generated 100,000 random inputs whose length range from 1 to 1000 and then compared the output from the DFA with a direct verification of the condition. Every time I run this code, the output is a satisfying True.

To test individual strings:

>>> dfaTest('ababba')
False
>>> dfaTest('abbabba')
True