I am studying Paz's "Introduction to Probabilistic Automata", and there is an exercise I cannot solve:
Ex. 11, p. 170: Prove that the number of nonregular events of the form $\{x \mid p^A(x) > \lambda\}$, where $A$ is a given $n$-state probabilistic automaton over a single letter is $\leq n$. ($p^A(x)$ is the probability of acceptance of $x$).
I can rephrase it, for instance, as:
Let $M$ be a stochastic matrix of dimension $n \times n$ and $a$ be a letter. There are at most $n$ different values of $\lambda \in [0,1]$ for which $\{a^k \mid (1, 0, \ldots, 0)M^k(0,\ldots,0,1)^{\mbox{T}} > \lambda\}$ is nonregular.
or, alternatively:
For a stochastic matrix $M$ of dimension $n \times n$, there are at most $n$ different values of $\lambda \in [0,1]$ such that $\{k \mid (1, 0, \ldots, 0)M^k(0,\ldots,0,1)^{\mbox{T}} > \lambda\}$ is not expressible as $F\cup C$ where $F$ is a finite set and $C = c_0 + c_1\mathbb{N}$.
I am strongly interested in the form those nonregular languages may have, so this could be a good start. Any help?
Hint: show $\lim_{k\to\infty}(1,0,\dots,0)M^{pk+i}(0,\dots,0,1)^T$ exists for each integer $1\leq i\leq p$, where $p$ is the period of the accepting state (taking $p=1$ if the accepting state is transient).