automatafinite-automatadfanfaautomata-theory

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


enter image description here

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?


Solution

  • 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 NFA on the right seems correct since: