Ff, build a deterministic finite-state machine that accepts all bit strings in which the the third-to-last bit is a 1, and that rejects all other bit strings. this problem is a bit tricky, and we’ll discuss it in class, so we encourage you to consult the lecture notes.

this problem requires at least eight states. you may use more states if necessary (there’s no penalty for doing so), but if you have time, try to get as close to the minimum as possible!

here are four examples of strings that should be accepted:

0101
100
0101000100
1101
here are three strings that should be rejected:

10
001
011011