Zero-run lower bound for a linear-feedback shift register
= Zero-run lower bound for a linear-feedback shift register
If an output prefix contains $d$ consecutive zeros followed by a one, no register of degree at most $d$ can generate it: the all-zero state would have been reached and would remain zero forever.