Build the 101 sequence detector as a state machine. Read a bit string and, for each bit, output 1 if the last three bits read (including this one) are 1, 0, 1, and 0 otherwise. Matches may overlap.
Input
One line: a string of 1 to 1000 bits.
Output
One line: the output bits, as long as the input.
Examples
Example 1 · Input
1101011
Expected output
0001010
Example 2 · Input
101
Expected output
001
Prompts inside input() are ignored when checking, so input("n: ") is fine.
Hints
Hint 1
Keep a state: how much of 101 you have just seen (nothing, 1, or 10).
Hint 2
Reading 1 in the state 10 completes a match: output 1, and the new state is 1 (that 1 can start the next match).
Hint 3
Write the transitions as a table (a dictionary) and follow it bit by bit.
Solution
Show one correct solution (try it yourself first)
bits = input().strip()
table = {
("S0", "0"): ("S0", "0"), ("S0", "1"): ("S1", "0"),
("S1", "0"): ("S2", "0"), ("S1", "1"): ("S1", "0"),
("S2", "0"): ("S0", "0"), ("S2", "1"): ("S1", "1"),
}
state, out = "S0", ""
for b in bits:
state, o = table[(state, b)]
out += o
print(out)