Why do all non-empty ω-regular languages have periodic members? I was learning about B&uuml;chi Automata and couldn't understand a part where they were describing "Non-empty $\omega$-regular languages contain periodic strings"


  Let $A$ be a B&uuml;chi automaton and $s ∈ L^\omega(A)$. There is an accepting run $r$ of $A$ on $s$ such that $q ∈ \text{Inf}(r)$, for some $q$. Then, there exist finite strings $s_0$ and $s_1$ such that $s_0s_1$ is a prefix of $s$, and such that $A$, after processing $s_0$ is in $q$, and after processing $s_0s_1$ is also in $q$. Then, the periodic string $s' = s_0s_1s_1s_1 \dotsm$ is accepted by $A$ since there is a run on $s'$ that contains $q$ infinitely many times.


I bolded the part I'm having trouble understanding.
Why is it that we can say after running a prefix like $s_0$ we are in an accept state $q$?
It seems to me a prefix could easily end in some not accepting state (i.e not in $\text{Inf}(r)$).
Actually, it doesn't say that $q$ is an accepting state, though it should do!  $\mathrm{Inf}(r)$ is the set of states visited infinitely often during the run&nbsp;$r$.  The acceptance condition of B&uuml;chi automata is that $\mathrm{Inf}(r)$ contains an accepting state.

The correct proof is as follows, with explanation added. Note also that, while your title says that the automaton is deterministic, the proof applies to nondeterministic automata, too, since it talks about the existence of a run with a particular property, rather than saying that the unique run has that property.

Let $A$ be a B&uuml;chi automaton and let $s\in L^\omega(A)$. Since $A$ accepts&nbsp;$s$, there must be a run&nbsp;$r$ of&nbsp;$a$ on&nbsp;$s$ that has an accepting state $q\in \mathrm{Inf(r)}$ because a B&uuml;chi automaton accepts if, and only if, some accepting state is visited infintely often. Let $s_0$&nbsp;be any prefix of&nbsp;$s$ such that $A$&nbsp;is in state&nbsp;$q$ after reading&nbsp;$s_0$.  Since $r$ visits&nbsp;$q$ infinitely often, it must return to&nbsp;$q$ when processing&nbsp;$s$, say after processing the prefix&nbsp;$s_0s_1$.  In particular, if the automaton is in state&nbsp;$q$ and reads string&nbsp;$s_1$, there is a run in which it returns to&nbsp;$q$. Therefore, the automaton has a run that visits&nbsp;$q$ infinitely often when processing the string $s_0\,{s_1}^\omega = s_0s_1s_1s_1\dots$.