6
$\begingroup$

I am currently learning about Büchi automata and have a combinatorial question about the acceptance condition.

Let $A=(Q,\Sigma,\delta,q_0,F)$ be a (nondeterministic finite) Büchi automaton and $w=w_1w_2w_3\ldots$ an infinite word over $\Sigma$. Suppose that for each natural number $n$ there exists a run

$q_0 \xrightarrow{w_1} q_1 \xrightarrow{w_2} q_2 \xrightarrow{w_3} \cdots$

that contains at least $n$ occurrences of a final state.

Does that imply the existence of an accepting run for $w$, i.e. one with infinitely many final states? I expect that the answer is no, but cannot find a counterexample. Hints would be appreciated.

$\endgroup$
5
$\begingroup$

Consider $\Sigma = \{0,1\}$ and $w = 1101001000100001\ldots$, i.e., there is an increasing number of zeros between two ones. Now consider the automaton with states $q_0, q_1$, and $q_A$ where $q_A$ is the only accepting state. On input $0$, always stay in the current state. On input $1$ allow the following transitions: In state $q_0$, either stay in $q_0$ or go to state $q_A$; in state $q_A$, go to $q_1$; in state $q_1$, stay in $q_1$.

If the transition $q_0 \to q_A$ happens at a position in $w$ that is followed by $n$ zeros, $q_A$ will occur exactly $n+1$ times in that run. Since $w$ contains $n$ consecutive zeros for all $n$ but no infinite sequence of zeros, this is a counterexample to your statement.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.