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 :)

I think it should be noted for those viewers who are of the `OMG we shouldn't help you with your homework! -1!` mindset, that this question is not asking for a solution, but asking ***HOW*** the answer given was achieved. — Martin, Jan 01 '17 at 14:35
The textbook solution is incorrect, it accepts "aabbaa", with 4 "a"s. — liori, Jan 01 '17 at 14:42
@Martin You are completely right! I have carefully given my line of thoughts to show everyone how I came up with my proposed solution, so that people would not say I'm just asking others to do my homework :D — Dang Manh Truong, Jan 01 '17 at 14:50
The textbook solution also doesn't accept certain strings that it should accept, such a `aaab`. Arrows from state 6 are missing. — John Coleman, Jan 01 '17 at 14:50

score 2 · Accepted Answer · edited May 23 '17 at 12:24

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

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'

1 Answers1