Prove that the transition monoid of the minimal DFA of \(L\) is the syntactic monoid of \(L\).

Use the transition monoid to define what a counter should be.

Let us assume that \(A = (Q, q_0, \delta, F)\) is the minimal DFA of \(L\) and that the syntactic monoid of \(L\) is aperiodic. Using the hint, we know that \(\delta_w^n\) is eventually constant for all \(w \in \Sigma^*\). As a consequence, if \(q \in Q\) is such that \(\delta(q, w^n) = q\), then \((\delta_w)^{kn}(q) = q\) for all \(k \in \mathbb{N}\). If \(k\) is large enough, then \(\delta_w^{kn} = \delta_w^{kn+1}\), and therefore \(\delta_w(q) = \delta_w (\delta_w^{kn})(q) = \delta_w^{kn} (q) = q\). We have proven that \(A\) has no counters.

Assume that the minimal DFA \(A = (Q, q_0, \delta, F)\) recognising \(L\) is counter-free. Let \(w \in \Sigma^*\). We will prove that the sequence \(\delta_w^n\) is eventually constant. Let \(q \in Q\), there exists \(i < j\) such that \(\delta_w^i(q) = \delta_w^j(q)\). Let \(q' :=\delta_w^i(q)\), then \(\delta_w^{j-i}(q') = q'\). Since \(A\) is counter-free, we conclude that \(\delta_w(q') = q'\). In particular, the sequence \(\delta_w^n(q)\) is eventually constant. Now, because \(Q\) is finite, the sequence \(\delta_w^n\) is itself eventually constant. And because there are finitely many functions \(\delta_w\) there exists a uniform bound \(N_0\) such that \(\delta_w^n = \delta_w^m\) for all \(n,m \geq N_0\) and all \(w \in \Sigma^*\).

If \(A\) is a counter-free automaton that recognises \(L\), then the minimal DFA recognising \(L\) is also counter-free.