Why do all non-empty ω-regular languages have periodic members?

Question

I was learning about Bü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ü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)$).

Answer 1

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

Answer 2

It may be worth noting that referring to any particular automaton is not really needed to prove the statement in the title. The standard definition of an $\omega$-regular language is as a finite union

$L=A_1B_1^\omega\cup\dots\cup A_nB_n^\omega$,

where all $A_i$ and $B_i$ are regular. If $L$ is nonempty, then there is at least one $i$ with $A_i,B_i$ nonempty; picking any $u\in A_i,v\in B_i$, it is clear that $uv^\omega\in L$.

Answer 3

By definition, a run $r$ is accepting if there is a final state such that $q \in \text{Inf}(r)$.

EDIT (to please david-richerby).

The standard definition of an accepting run says that a run $r$ is accepting if there is a final state such that $q \in \text{Inf}(r)$.