Question:
Define a DFA that accepts all strings over {0,1} such that every block of five consecutive positions contains at least two 0s. Please read the question carefully. Ask yourselves: Does this allow e (epsilon (empty string)) to be accepted? How about 0101? Such English descriptions are found in various books, and I want to make sure you know how to read and interpret.
Instructor Hint: "The "blocks of 5" DFA can be programmatically generated without much trouble. I did it both ways (by hand and programmatically). Because I'm good with Emacs and Keyboard Macros, I could do even the 'by hand' mechanically and quite fast. But programmatic is less error-prone and compact."
I'm drawing this thing out, and I think I'm doing it wrong, as it is getting out of control.
My sketch of the DFA before I make it in python:
However, this isn't right, because index 2, 3, 4, 5, and 6 constitute a block of five consecutive positions, so I need to account for at least two zeroes in that. Oh, great, and I have been thinking it needs two 1s, not two 0s. Am I going about this the entirely wrong way? Because the way I'm thinking, this is going to have a huge amount of states.
(goes back to drawing this large DFA)
If you want to do it the old school way:
def check(s):
buffer = s[:5]
i = 5
count0, count1 = 0, 0
while i < len(s):
if len(buffer) == 5:
first = buffer[0]
if first == '0':
count0 -= 1
else:
count1 -= 1
buffer = buffer[1:]
buffer += s[i]
if buffer[-1] == '0':
count0 += 1
else:
count1 += 1
if count0 < 2:
return "REJECT"
i += 1
if buffer.count('0') >= 2:
return "ACCEPT"
else:
return "REJECT"
A slightly smarter way:
def check(s):
return all(ss.count('0')>=2 for ss in (s[i:i+5] for i in xrange(len(s)-4)))
The verbose code of the above method:
def check(s):
subs = (s[i:i+5] for i in xrange(len(s)-4))
for sub in subs:
if sub.count('0') < 2:
return "REJECT"
return "ACCEPT"
Haven't tested this code, but it should likely work. Your professor probably wants the third method.
Hope this helps