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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
6
$\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.

Improve this answer
$\endgroup$

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.