DFA Problem # 2

Problem:
A run in string is a substring of length at least two, as long as possible and consisting
entirely of the same symbol. For instance, the string abbbaab contains a run of of b’s of
length three and run of a’s of length two. Find dfa for the following language on {a, b}.
L = {w: w contains no runs of length less than four}


Solution:
This one is a bit more fun. It sounds simple, but once you start playing with it a bit you notice that there are a couple of pitfalls. If you just start placing nodes on the canvas and trying to plug in arrows, you will have a bit of a problem. The easiest way to do this one is to start from the beginning: either an 'a' or a 'b'.

The problem is to accept strings of arbitrary length where each character is repeated a MINIMUM of 4 times in succession. All other strings fail. So lets start with just setting accept states for 'aaaa...' and 'bbbb...'.

Next, lets introduce the trap. Strings like, 'ab...', 'aab...', 'aaab...' will NEVER be accepted assuming that the leading character in these situations is in fact the a and that no a's precede these strings. In other words, once these strings are encountered fall into an unrecoverable trap. The two traps in the diagram could logically be combined into one, but I left them separate for easy of reading the diagram (crossing lines gets hard to read).

Almost done! All that is left to do is to solve 

d(q5, a) = ?

d(q8, b) = ? 

Easy! 

If the state is q5 and an 'a' is encountered, start looking for 4 consecutive a's. 

If the state is q8 and a 'b' is encountered, start looking for 4 consecutive b's. 

DONE!