DFA design (alphabet "a" and "b"): the number "a" in a line must be a multiple of 3, and the line does not contain "aba",

Question

Here is the problem:

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

• It seems difficult.
• Finding a regex seems complicated for it, so I can't follow this path to convert a regex to DFA
• So, I decided to solve the first part of the problem: Accept a line whose number "a" is a multiple of 3. It's quite simple, you just need 3 states: 1,2,3 with 1 as start, if there is an input "a", you go to the next, if it is "b" you remain in that state, and the start state is also the final state. But here, in this exercise, these 3 states will actually be 3 'big' states. Then the problem becomes the construction of the internal elements of these "big states" and their interaction.

I had no choice but to use guesswork to come to a decision. Here's what I came up with (1,2,3 - completion states, 3 - initial state, and also 7 and 9 both go to 1 if input “a” is accepted): I also used DFA minimization on this, and found out that it already minimal. However, the textbooks give another solution:

But I do not understand how it is right! I just can’t understand :( And I don’t even know if my solution is 100% consistent. Please help me, thank you very much :)

Answer 1

. , . , Python :

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

accepts . . - 100 000 , 1 1000, DFA . , , True.

:

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