Automata accepting primitive words (Q1103732): Difference between revisions

Let X be a finite alphabet, \(| X| \geq 2\). A word w over X is said to be primitive if \(w=u\) n implies \(u=w\) and \(n=1\). In this paper, properties of sets of primitive words accepted by finite automata are studied. If a given n-state automaton accepts a primitive word at all it accepts a primitive word whose length does not exceed 3(n-1). On the other hand, it accepts infinitely many primitive words if and only if it accepts at least one primitive word whose length is no less than n. In particular, it follows that for a given automaton the questions of whether it accepts any primitive words and whether it accepts infinitely many primitive words are decidable. In the final section of the paper, the authors focus on the following problem: Among those automata with n states accepting only finitely many primitive words, what is the maximal number \(\vartheta_ n\) of primitive words accepted and what is the maximal number \(\eta_ n\) of primitive words which are roots of accepted words. The surprising result is \[ \vartheta_ n = \eta_ n = \begin{cases} 0, & \text{ if \(n=1,\)} \\ 1, & \text{ if \(n=2,\)} \\ | \{x|\quad | x| \leq n-2, x \text{ is primitive}\}|, & \text{ if \(n\geq 3\).}\end{cases} \]