Automata for languages derived from an automaton by number of state visits
Starting with an automaton for $L$ with state set $Q$, starting state $s_0$, transition function $\delta$, and accepting states $F$, here is how to construct automata $M_1,M_0$ for $L_1$ and $L_0$. The state set of both is $Q \times \{0,1\}$. The starting state is $(s_0,0)$. The transition function is given by
$$
\delta'((s,x),a) = \begin{cases} (\delta(s,a),x) &amp; \text{ if } \delta(s,a) \neq q, \\ (\delta(s,a),1-x) &amp; \text{ if } \delta(s,a) = q. \end{cases}
$$
The accepting states of $M_1$ are $F \times \{1\}$, and of $M_0$ are $F \times \{0\}$.

In words, in addition to remember the original state, the new automaton also remembers the parity of the number of times that $q$ has been visited. Acceptance is determined accordingly.