NFA or DFA accepting # of positions of 4k between 0's

Question

Left is the given solution, but it fails for 01110(shouldn't be true) and 010000 (should be true). If we do it like the right one like I did, then there might not be 1 in it so it fails because 000000 shouldn't be in it, how do I manage to do that?

Answer 1

From context, I think "separated by a number of positions that is a multiple of four" must mean that the number of things between the 0s must have a length that's a multiple of four, rather than the positions of two 0s differing by four. So, 011110 would be a string in the language, rather than 01110, since there are four 1s between the 0s in the first case, rather than 4 - 0 = 4 in the second case.

Given that, I agree the NFA on the left is incorrect: it accepts 01110 when it should not.

Note though that 000000 should be accepted, in particular, because:

• the substring 00 has zero symbols between the two 0s and zero is a multiple of four
• the string 000000 can be written 0(0000)0 and it's clear there are four 0s between the 0s on the ends, and four is a multiple of four

The NFA on the right seems correct since:

• it can deal with any prefix by looping on the initial state
• it can see 0 when it needs to
• it can see another 0 immediately afterwards or else any number of symbols, four at a time, and then a following 0
• it can deal with any suffix by looping on the final state