Undecidability and Finite Automata

Abstract

Using a novel rewriting problem, we show that several natural decision problems about finite automata are undecidable (i.e., recursively unsolvable). In contrast, we also prove three related problems are decidable. We apply one result to prove the undecidability of a related problem about k-automatic sets of rational numbers.

1 Introduction

Starting with the first result of Turing [16], computer scientists have assembled a large collection of natural decision problems that are undecidable (i.e., recursively unsolvable); see, for example, the book of Rozenberg and Salomaa [12].

Although some of these results deal with relatively weak computing models, such as pushdown automata [2, 6], few, if any, are concerned with the very simplest model: the finite automaton. One exception is the following decision problem, due to Engelfriet and Rozenberg [5, Theorem 15]: given a finite automaton M with an input alphabet of both primed and unprimed letters (i.e., an alphabet $\varSigma \cup \varSigma '$, where $\varSigma ' = \{ a' : a \in \varSigma \}$), decide if M accepts a word w where the primed letters, after the primes have been removed, form a word identical to that formed by the unprimed letters. This problem was also mentioned by Hoogeboom [7]. This problem is easily seen to be undecidable, as it is a disguised version of the classical Post correspondence problem [10].

In this paper we start by proving a novel lemma on rewriting systems. In Sect. 3, this lemma is then applied to give a new example of a natural problem on finite automata that is undecidable. In Sect. 4 we prove that a related problem on the so-called k-automatic sets of rational numbers is also undecidable. In Sect. 5 we prove the undecidability of yet another problem about finite automata. Finally, in Sect. 5 we show that it is decidable if a finite automaton accepts two distinct conjugates.

2 A Lemma on Rewriting Systems

For our purposes, a rewriting system S over an alphabet $\varSigma$ consists of a finite set of context-free rules of the form $\ell \rightarrow r$, where $\ell , r \in \varSigma ^*$. Such a rewriting rule applies to the word $\alpha \ell \beta \in \varSigma ^*$, and converts it to $\alpha r \beta$. We indicate this by writing $\alpha \ell \beta \Longrightarrow \alpha r \beta$. We use $\Longrightarrow ^*$ for the reflexive, transitive closure of $\Longrightarrow$ (so that $\gamma \Longrightarrow ^*\zeta$ means that there is a sequence of 0 or more rules taking the word $\gamma$ to $\zeta$). A rewriting system is said to be length-preserving if $|\ell | = |r|$ for all rewriting rules $\ell \rightarrow r$.

Many undecidable decision problems related to rewriting systems are known [3]. However, to the best of our knowledge, the following one is new.

REWRITE-POWER

Instance: An alphabet $\varSigma$ containing the symbols a and b (and possibly other symbols), and a length-preserving rewriting system S.

Question: Does there exist an integer $n \ge 1$ such that $a^n \Longrightarrow ^* b^n$?

Lemma 1

The decision problem REWRITE-POWER is undecidable.

Proof

The standard approach for showing that a rewriting problem is undecidable is to reduce from the halting problem, by encoding a Turing machine M and simulating its computation using the rewriting rules; for example, see [3].

The difficulty with applying that approach in the present case is the lack of asymmetry, i.e., the fact that the initial word consists of all a’s. Because there is no distinguished symbol with which to start the simulation, unwanted parallel simulations of M could occur at different parts of the word.

To deal with this difficulty, we construct a rewriting system that permits multiple simulations of M to arise, but employs a delimiter symbol $ to ensure that they do not interfere with each other. Each simulation works on its own portion of the word, and changes it to b’s (ending by changing the delimiter symbol as well) only if M halts.

Here are the details. We use the one-tape model of Turing machine from Hopcroft and Ullman [8], where $M = (Q, \varOmega , \varGamma , \delta , q_0, \mathtt{B}, q_f)$. Here Q is the set of states of M, with $q_0 \in Q$ the start state and $q_f \in Q$ the unique final state. Let $\varOmega$ be the input alphabet and $\varGamma$ the tape alphabet, with $\mathtt{B} \in \varGamma$ being the distinguished blank symbol. Let $\delta$ be the (partial) transition function, with domain $Q \times \varGamma$ and range $Q \times \varGamma \times \{L, R\}$. We assume without loss of generality that M halts, i.e., M has no next move, iff it is in state $q_f$. We also assume that $a, b, \$ \not \in \varGamma$.

We construct our length-preserving rewriting system mimicking the computations of M as follows. Let $\varSigma = \varGamma \cup Q \cup \{a,b,\$\}$. Let S contain the following rewriting rules:

$$\begin{aligned} aa&\rightarrow \$ q_0 \end{aligned}$$

(1)

$$\begin{aligned} a&\rightarrow \mathtt{B} \end{aligned}$$

(2)

$$\begin{aligned} q_i c&\rightarrow d q_j \quad \text { if } (q_j, d, R) \in \delta (q_i, c) \text { with } c, d \in \varGamma \end{aligned}$$

(3)

$$\begin{aligned} f q_i c&\rightarrow q_j f d \quad \text { if } (q_j, d, L) \in \delta (q_i, c) \text { and } f \in \varGamma \end{aligned}$$

(4)

$$\begin{aligned} q_f c&\rightarrow c q_f \quad \text { for all } c \in \varGamma \end{aligned}$$

(5)

$$\begin{aligned} c q_f&\rightarrow q_f b \quad \text { for all } c \in \varGamma \end{aligned}$$

(6)

$$\begin{aligned} \$ q_f&\rightarrow bb \end{aligned}$$

(7)

Rule (1) starts a new simulation. Each simulation has its own head symbol $q_i$ and left end-marker $, and never moves the head symbol past an a, b, or $. This ensures that the simulations are kept separate from each other. Rule (2) converts an a to a blank symbol, available for use in a simulation. Rules (3) and (4) are used to simulate the transitions of M. Once a simulation reaches $q_f$ (meaning that M has halted), its head can be moved to the right using rule (5), past all of the symbols it has read, and then back to the left using rule (6), changing all of those symbols to b’s. Finally, the simulation can be stopped using rule (7).

We argue that M halts when run on a blank tape iff $a^n \Longrightarrow ^* b^n$ for some $n \ge 1$.

If M halts when run on a blank tape, then there is some number of tape cells k which it uses. Let $n = k+2$. Then S can use rule (1) to start a simulation with the two a’s at the left end of the word, use rule (2) to convert the k remaining a’s to blank cells, and run the simulation using rules (3) and (4). Eventually M halts in the final state $q_f$. At that point, S can move the head to the right end of the word using rule (5), convert all k tape cells to b’s using rule (6), and then convert the end-marker $ and tape head to b’s with rule (7). Thus we have $a^n \Longrightarrow ^* b^n$.

For the other direction, if the initial word $a^n$ is ever transformed into $b^n$, it means that one or more simulations were run, each of which operated on a portion of the word without interference from the others. The absence of interference can be deduced from the shape of the rules. There is only one occurrence of the marker $ in the left-hand sides of the rules, namely as the leftmost symbol in the left-hand side of rule (7). Furthermore, $ can only be rewritten to b which does not occur in any left-hand side.

Each simulation runs M on a blank tape, and uses a number of tape cells bounded by the length of its portion of the word. Since every portion of the word was transformed into b’s, M halted in every one of the simulations (otherwise the word would still contain one or more head symbols and end-markers). The completion of any one of these simulations is enough to show that M halts when run on a blank tape.

Therefore M halts when run on a blank tape iff there exists an $n \ge 1$ such that $a^n \Longrightarrow ^* b^n$, completing the reduction from the halting problem. Since the halting problem is undecidable, REWRITE-POWER is also undecidable.    $\square$

3 An Undecidable Problem on Finite Automata

Our model of finite automaton is the usual one (e.g., [8]). We now consider a decision problem on finite automata. To state it, we need the notion of the product of two words of the same length. Let $\varSigma , \varDelta$ be alphabets, and let $w \in \varSigma ^*$, $x \in \varDelta ^*$, with $|w| = |x|$. Then by $w \times x$ we mean the word over the alphabet $\varSigma \times \varDelta$ whose projection $\pi _1$ over the first coordinate is w and whose projection $\pi _2$ over the second coordinate is x. More precisely, if $w = a_1 a_2 \cdots a_n$ and $x = b_1 b_2 \cdots b_n$, then $w \times x = [a_1, b_1] [a_2, b_2] \cdots [a_n, b_n]$. In this case $\pi _1 (w\times x) = w$ and $\pi _2(w\times x) = x$. For example, if $y = [\mathtt{t,h}] \, [\mathtt{e,o}] \, [\mathtt{r,e}] \, [\mathtt{m,s}],$ then $\pi _1(y) = \mathtt{term}$ and $\pi _1 (y) = \mathtt{hoes}$. To simplify notation, we often write ${w \atopwithdelims [] x}$ in place of $w \times x$. For example,

$$ \bigg [ \begin{array}{cc} \mathtt{cat} \\ \mathtt{dog} \end{array} \bigg ] \quad \text { means the same thing as } \quad \bigg [\begin{array}{cc} \mathtt{c} \\ \mathtt{d} \end{array}\bigg ] \bigg [ \begin{array}{cc} \mathtt{a} \\ \mathtt{o} \end{array}\bigg ] \bigg [\begin{array}{cc} \mathtt{t} \\ \mathtt{g} \end{array}\bigg ] \quad \text { and } \quad [\mathtt{c},\mathtt{d}] [\mathtt{a},\mathtt{o}] [\mathtt{t}, \mathtt{g}] . $$

Consider the following decision problem:

ACCEPTS-SHIFT

Instance: An alphabet $\varGamma$, a letter $c \not \in \varGamma$, and a finite automaton M with input alphabet $(\varGamma \, \cup \,\{c\})^2$.

Question: Does M accept a word of the form $x c^n \times c^n x$ for some $x \in \varGamma ^*$ and $n \ge 0$?

Theorem 2

The decision problem ACCEPTS-SHIFT is undecidable.

Proof

We reduce from the problem REWRITE-POWER. An instance of this decision problem is a set S of length-preserving rewriting rules, an alphabet $\varSigma$, and letters $a, b \in \varSigma$. Define $\varGamma = \varSigma \cup \{ d \}$, where $d \not \in \varSigma$ is a new symbol. Now we define the following regular languages:

$$\begin{aligned} E&= \left\{ {e \atopwithdelims [] e} : e \in \varSigma \right\} \quad \text {and} \quad R = \left\{ {r \atopwithdelims [] \ell } : \ell \rightarrow r \in S \right\} \\ L&= {d \atopwithdelims [] c} {{a \atopwithdelims [] c}}^+ {d \atopwithdelims [] d} \left( E^* R E^* {d \atopwithdelims [] d} \right) ^* {{c \atopwithdelims [] b}}^+ {c \atopwithdelims [] d} . \end{aligned}$$

Let $M = (Q, \varDelta , \delta , q_0, F)$ be a deterministic finite automaton accepting L, with $\varDelta = (\varGamma \cup \{c\})^2$. Clearly M can be constructed effectively from the definitions.

We claim that, for all $n \ge 2$, we have $a^{n-1} \Longrightarrow ^*b^{n-1}$ iff the language $L = L(M)$ contains a word of the form $x c^n \times c^n x$. The crucial observation is that

$$\begin{aligned} u \Longrightarrow v \quad \text {iff} \quad {v \atopwithdelims [] u} \in E^* R E^*. \end{aligned}$$

(8)

This follows immediately from the definitions of E and R.

$\Longrightarrow$: Suppose

$$ u_0 := a^{n-1} \Longrightarrow u_1 \Longrightarrow \cdots \Longrightarrow u_m = b^{n-1}$$

with $m \ge 1$ and $n \ge 2$. Then

$$ {u_{i+1} \atopwithdelims [] u_i} \in E^* R E^* $$

for $0 \le i < m$. Then

$$ {d \atopwithdelims [] d} {u_1 \atopwithdelims [] u_0} {d \atopwithdelims [] d} {u_2 \atopwithdelims [] u_1} \cdots {d \atopwithdelims [] d} {u_m \atopwithdelims [] u_{m-1}} {d \atopwithdelims [] d} \in {d \atopwithdelims [] d} \left( E^* R E^* {d \atopwithdelims [] d} \right) ^* . $$

Hence

$$ {d \atopwithdelims [] c} {u_0 \atopwithdelims [] c^{n-1}} {d \atopwithdelims [] d} {u_1 \atopwithdelims [] u_0} {d \atopwithdelims [] d} {u_2 \atopwithdelims [] u_1} \cdots {d \atopwithdelims [] d} {u_m \atopwithdelims [] u_{m-1}} {d \atopwithdelims [] d} {c^{n-1} \atopwithdelims [] u_m} {c \atopwithdelims [] d} \in L, $$

as desired. The first component is $d u_0 du_1 d \cdots d u_m d c^n$, while the second component is $c^n d u_0 d u_1 \cdots d u_{m-1} d u_m d$. Taking $x = d u_0 d u_1 d \cdots d u_m d,$ we see that $x c^n \times c^n x \in L$.

$\Longleftarrow$: Assume that $x c^n \times c^n x \in L$ for some word x with $n \ge 2$. Now L consists only of words of the form

$$ w = {d \atopwithdelims [] c} {{a \atopwithdelims [] c}}^i {d \atopwithdelims [] d} {v_0 \atopwithdelims [] u_0} {d \atopwithdelims [] d} {v_1 \atopwithdelims [] u_1} {d \atopwithdelims [] d} \cdots {v_m \atopwithdelims [] u_m} {d \atopwithdelims [] d} {{c \atopwithdelims [] b}}^j {c \atopwithdelims [] d} $$

where $u_t \Longrightarrow v_t$ for $1\le t\le m$ and $i, j \ge 1$. Observe that

$$\pi _1 (w) = d a^i d v_0 d v_1 \cdots d v_m d c^{j+1} \quad \text {and} \quad \pi _2 (w) = c^{i+1} d u_0 d u_1 \cdots d u_m d b^j d, $$

so if $\pi _1 (w) = xc^n$ and $\pi _2 (w) = c^n x$ we must have $i = j = n-1$ and $x = da^i d v_0 d v_1 \cdots d v_m d = d u_0 d u_1 \cdots d u_m d b^j d$. Since d is a new symbol, not in the alphabet of $\varSigma$, it follows that $u_0 = a^i$, $u_1 = v_0$, $u_2 = v_1, \ldots$, $u_m = v_{m-1}$, and $b^j = v_m$.

But then $u_0 \Longrightarrow v_0 = u_1$, $u_1 \Longrightarrow v_1 = u_2$, and so forth, up to $u_{m-1} \Longrightarrow v_{m-1} = u_m$, and finally $u_m \Longrightarrow v_m = b^j$. So $u_0 \Longrightarrow ^*v_m$, and therefore $a^{n-1} \Longrightarrow ^*b^{n-1}$. This completes the proof.    $\square$

Remark 3

In the decision problem ACCEPTS-SHIFT, the undecidability of the problem arises, in an essential way, from words of the form $x c^n \times c^n x$ where $n < |x|$, and not from those words with $n \ge |x|$ as one might first suspect. More formally, the related decision problem defined below is actually solvable in cubic time.

ACCEPTS-LONG-SHIFT

Instance: An alphabet $\varSigma$, a letter $c \not \in \varSigma$, and a finite automaton M with input alphabet $(\varSigma \, \cup \,\{c\})^2$.

Question: Does M accept a word of the form $x c^n \times c^n x$ for some $n \ge |x|$?

Theorem 4

The decision problem ACCEPTS-LONG-SHIFT is solvable in cubic time.

Proof

Suppose $x = a_1 a_2 \cdots a_m$. If $y = x c^n \times c^n x$ and $n \ge |x|$ then

$$y = [a_1, c] \cdots [a_m, c] [c,c]^{n-m} [c, a_1] [c, a_2] \cdots [c, a_m].$$

Given a DFA $M = (Q, \varSigma , \delta , q_0, F)$, we can create a nondeterministic finite automaton $M'$ that accepts all x for which the corresponding y is accepted by M. The idea is that $M'$ has state set $Q' = Q\times Q \times Q$; on input x the machine $M'$ “guesses” a state $q \in Q$, and stores it in the second component, and then simulates M on input $x \times c^m$ in the first component, starting from $q_0$ and reaching some state p, and simulates M on input $c^m \times x$ in the third component, starting from q. Finally, $M'$ accepts if the third component is an element of F and if there exists a path from p to q labeled $[c,c]^i$ for some $i \ge 0$. Now we can test whether $M'$ accepts a word by using depth-first or breadth-first search on the transition diagram of $M'$, whose size is at most cubic in terms of the size of M.    $\square$

4 Application to k-automatic Sets of Rational Numbers

Recently the second author and co-authors defined a notation of k-automaticity for sets of non-negative rational numbers [11, 13], in analogy with the more well-known concept for sets of non-negative integers [4].

For an integer $k \ge 2$ define $\varSigma _k = \lbrace 0,1, \ldots , k-1 \rbrace$. If $w \in \varSigma _k^*$, define $[w]_k$ to be the integer represented by the word w in base k (assuming the most significant digit is at the left). Let M be a finite automaton with input alphabet $\varSigma _k \times \varSigma _k$. We define ${{\mathrm{quo}}}_k (M) \subseteq {\mathbb {Q}}^{\ge 0}$ to be the set

$$\left\{ {{[\pi _1 (x)]_k} \over {[\pi _2 (x)]_k}} : x \in L(M) \right\} .$$

Furthermore, we call a set $T \subseteq {\mathbb {Q}}^{\ge 0}$ k-automatic if there exists a finite automaton M such that $T = {{\mathrm{quo}}}_k (M)$.

We first consider the following decision problem:

ACCEPTS-POWER

Instance: An integer $k \ge 2$, and a finite automaton M with input alphabet $(\varSigma _k)^2$.

Question: Is ${{\mathrm{quo}}}_k (L(M)) \, \cap \,\{ k^i : i \ge 0 \}$ nonempty?

Theorem 5

The problem ACCEPTS-POWER is undecidable.

Proof

The basic idea is to reduce once more from REWRITE-POWER, using the same construction as in the proof of Theorem 2. Our reduction produces an instance of ACCEPTS-SHIFT consisting of an alphabet $\varGamma$ of cardinality $\ell$, a letter $c \not \in \varGamma$, and a finite automaton M. By renaming symbols, if necessary, we can assume the symbols of $\varGamma$ are the digits $1,2,\ldots , \ell$ and c is the digit 0. It then suffices to take $k = \ell + 1$. Then $y \in L(M)$ with ${{\mathrm{quo}}}_k (y)$ a power of k if and only if $y = x 0^n \times 0^n x$ for some x and some $n \ge 0$. Note that, by our construction in the proof of Theorem 2, if M accepts $x0^n \times 0^n x$, then x contains no 0’s.    $\square$

Now consider a family of analogous decision problems ACCEPTS-POWER(k), where in each problem k is fixed.

Theorem 6

For each integer $k \ge 2$, the decision problem ACCEPTS-POWER(k) is undecidable.

Proof

We have to overcome the problem that k can depend on the size of $\varGamma$. To do so, we recode all words over the alphabet $\{0, 1\}$. It suffices to use the morphism $\varphi$ defined by

$$\begin{aligned} \varphi (c)&= 0^{m+1} \quad&\varphi (a_i)&= 1^i 0^{m-i} 1 \end{aligned}$$

where $\varSigma = \{ a_1, a_2, \ldots , a_m \}$. In the proof of Theorem 2, we replace E, R, L by $E', R', L'$, as follows:

$$\begin{aligned} E'&= \left\{ {\varphi (e) \atopwithdelims [] \varphi (e)} : e \in \varSigma \right\} \quad \text {and} \quad R' = \left\{ {\varphi (r) \atopwithdelims [] \varphi (\ell )} : \ell \rightarrow r \in S \right\} \\ L'&= {\varphi (d) \atopwithdelims [] \varphi (c)} {{\varphi (a) \atopwithdelims [] \varphi (c)}}^+ {\varphi (d) \atopwithdelims [] \varphi (d)} \left( E^* R E^* {\varphi (d) \atopwithdelims [] \varphi (d)} \right) ^* {{\varphi (c) \atopwithdelims [] \varphi (b)}}^+ {\varphi (c) \atopwithdelims [] \varphi (d)} . \end{aligned}$$

The construction works because the blocks for symbols of $\varSigma$ begin and end with at least one 1, while the block for c consists of all 0’s. Therefore, if the first coordinate of an element of $L'$ has a suffix in $0^+$, this can only arise from $\varphi (c)$, and the same for prefixes of the second coordinate.    $\square$

5 Problems About Conjugates

Recall that we say two words x and y are conjugates if one is a cyclic shift of the other; that is, if there exist u, v such that $x = uv$ and $y = vu$.

The undecidability result of the previous section suggests studying the following related natural decision problem.

ACCEPTS-GENERAL-SHIFT

Instance: A finite automaton M with input alphabet $\varSigma ^2$.

Question: Does M accept a word of the form $x \times y$ for conjugates $x,y \in \varSigma ^*$ ?

Theorem 7

The decision problem ACCEPTS-GENERAL-SHIFT is undecidable.

Proof

We reduce from the problem ACCEPTS-SHIFT. An instance of this problem is an alphabet $\varGamma$, a letter $c \notin \varGamma$, and a finite automaton M with input alphabet $(\varGamma \cup \{c\})^2$.

First check whether M accepts a word of the form $x \times x$ for some $x \in \varGamma ^*$. (This is decidable because the language $\{x \times x : x \in \varGamma ^*\}$ is regular.) If so, ACCEPTS-SHIFT $(\varGamma ,c,M)$ = “yes”. Otherwise, construct a finite automaton $M'$ whose language is

$$\begin{aligned} L(M) \cap \{sc^+ \times c^+t \mid s,t \in \varGamma ^*\}. \end{aligned}$$

Notice that ACCEPTS-SHIFT $(\varGamma ,c,M')$ = ACCEPTS-SHIFT $(\varGamma ,c,M)$. Clearly we have that if then ACCEPTS-SHIFT $(\varGamma ,c,M')$ = “no”.

So suppose that ACCEPTS-GENERAL-SHIFT $(M')$ = “yes”. Then $M'$ accepts a word $w = x \times y$ for words $x = uv$, $y = vu$ where $u,v \in (\varGamma \cup \{c\})^*$. We now show that $w = zc^n \times c^nz$ for some $z \in \varGamma ^*$ and $n \ge 1$.

By the construction of $M'$, uv ends with c, vu begins with c, and any two occurrences of c in uv or vu have only c’s between them. Hence if u or v is empty, then $w = c^n \times c^n$ for some $n \ge 1$, and we can take $z = \epsilon$, the empty word. So say neither u nor v is empty. Then v begins and ends with c, and hence v is in $c^+$. It follows that if u contains c, then u begins and ends with c, so again $w = c^n \times c^n$ for some $n \ge 1$, and we can take $z = \epsilon$. So say u does not contain c. Then $w = uc^n \times c^n u$ with $u \in \varGamma ^+$ and $n = |v|$, and we can take $z = u$.

So $w = zc^n \times c^nz$ for some word $z \in \varGamma ^*$ and $n \ge 1$. Therefore we have ACCEPTS-SHIFT $(\varGamma ,c,M')$ = “yes”. This completes the reduction. Then since ACCEPTS-SHIFT is undecidable by Theorem 2, ACCEPTS-GENERAL-SHIFT is also undecidable.    $\square$

Now we turn to two other decision problems, both inspired by the problem ACCEPTS-GENERAL-SHIFT. The first is

ACCEPTS-DISTINCT-CONJUGATES

Instance: A DFA $M = (Q, \varSigma , \delta , q_0, F)$.

Question: Does M accept two distinct conjugates uv and vu?

We will prove

Theorem 8

ACCEPTS-DISTINCT-CONJUGATES is decidable.

To prove this theorem, we need the concept of primitive word and primitive root. A nonempty word x is said to be primitive if it cannot be written in the form $x = y^i$ for a word y and an integer $i \ge 2$. The primitive root of a word x is the unique primitive word t such that $x = t^j$ for some $j \ge 1$.

Lemma 9

If a DFA M of n states accepts two distinct conjugates, then it accepts two distinct conjugates uv and vu, with at least one of u and v of length $\le n^2$.

Proof

Let $L = L(M)$, the language accepted by $M = (Q, \varSigma , \delta , q_0, F)$, where $|Q| = n$. Suppose that there exist $uv \in L$, $vu \in L$, but $uv \not = uv$. Without loss of generality, assume |uv| is as small as possible. Assume, contrary to what we want to prove, that both |u| and |v| are $> n^2$.

Consider the acceptance path of uv through M: it looks like $\delta (q_0, u) = q_1$ and $\delta (q_1, v) = p_1$ for some $q_1 \in Q$ and $p_1 \in F$. Similarly, consider the acceptance path of vu through M: it looks like $\delta (q_0, v) = q_2$ and $\delta (q_2, u) = p_2$ for some $q_2 \in Q$ and $p_2 \in F$.

Now create a new DFA $M' = (Q\times Q, \varSigma , \delta ', q'_0, F')$ by the usual product construction, where $\delta '([r,s],a) := [\delta (r,a), \delta (s,a)]$ and $q'_0 = [q_0, q_1]$ and $F = \{ [q_2, p_1] \}$. Then $M'$ has $n^2$ states and accepts v.

Since $|v| > n^2$, the acceptance path for v in $M'$ visits $\ge n^2 + 2$ states and hence some state is repeated, giving us a loop of at most $n^2$ states that can be cut out. Hence we can write $v = v_1 v_2 v_3$, where $v_2 \not = \epsilon$ and $v_1 v_3 \not = \epsilon$, and $M'$ accepts $v_1 v_3$. In M, then, it follows that $\delta (q_1, v_1 v_3) = p_1$ and $\delta (q_0, v_1 v_3) = q_2$, and hence M accepts the conjugates $u v_1 v_3$ and $v_1 v_3 u$. Since $|uv_1v_3|< |uv|$, the minimality of |uv| implies that these conjugates cannot be distinct, and so we must have

$$\begin{aligned} uv_1 v_3 = v_1 v_3 u . \end{aligned}$$

(9)

We can now repeat the argument of the previous paragraph for the word u. We get a decomposition $u = u_1 u_2 u_3$ where $u_2 \not = \epsilon$ and $u_1 u_3 \not = \epsilon$, and we get

$$\begin{aligned} v u_1 u_3 = u_1 u_3 v. \end{aligned}$$

(10)

Finally, the acceptance paths in M we have created imply that we can cut out both $u_2$ and $v_2$ simultaneously from uv and vu, and still get words accepted by M. So $u_1 u_3 v_1 v_3$ and $v_1 v_3 u_1 u_3$ are both accepted. Again, by minimality, we get that

$$\begin{aligned} u_1 u_3 v_1 v_3 = v_1 v_3 u_1 u_3 . \end{aligned}$$

(11)

Now, by the Lyndon-Schützenberger theorem (see, e.g., [9, 14]), Eq. (11) implies the existence of a nonempty word t and integers i, j such that $u_1 u_3 = t^i$, $v_1 v_3 = t^j$. Without loss of generality, we can assume that t is primitive.

Applying the same theorem to Eq. (10) tells us that there exists k such that $v = t^k$. And applying the same theorem once more to Eq. (9) tells us that there exists $\ell$ such that $u = t^\ell$. But then $uv = vu$, a contradiction.    $\square$

Remark 10

We observe that the bound of $n^2$ in the previous result is optimal, up to a constant multiplicative factor. Consider the languages

$$L_t = (a^t)^+ b (a^{t+1})^+ bb \, \cup \, (a^t)^+ bb (a^{t+1})^+ bb .$$

Then it is easy to see that $L_t$ can be accepted by a (complete) DFA of $n = 3t+8$ states. The shortest pair of distinct conjugates in $L_n$, however, are $a^{t(t+1)} b a^{t(t+1)} bb$ and $a^{t(t+1)} bb a^{t(t+1)} b$, corresponding to $u = a^{t(t+1)} b$ of length $t^2 + t + 1$ and $v = a^{t(t+1)} bb$ of length $t^2 + t + 2$. Thus both u and v are of length $n^2/9 + O(n)$.

We can now prove Theorem 8.

Proof

Given $L = L(M)$, for each nonempty word x define the language

$$ L_x = \{ y \in \varSigma ^* : xy \in L,\ yx \in L,\ xy \not = yx \}.$$

We observe that each $L_x$ is a regular language. To see this, note that we can write $L_x = L_1 \, \cap \, L_2 \, \cap \, L_3$, where

$$\begin{aligned} L_1&= \{ y \in \varSigma ^* : xy \in L \} \\ L_2&= \{ y \in \varSigma ^* : yx \in L \} \\ L_3&= \{ y \in \varSigma ^* : xy \not = yx \} . \end{aligned}$$

Both $L_1$ and $L_2$ are easily seen to be regular, and finite automata accepting them are easily constructed from M. To see that the same holds for $L_3$, note that if $xy = yx$ with x nonempty, then by the Lyndon-Schützenberger theorem it follows that $y \in t^*$, where t is the primitive root of x. Hence $L_3 = \overline{t^*}$. Therefore we can construct a finite automaton $M_x$ accepting $L_x$.

Finally, here is the decision procedure. By Lemma 9 we know that if an n-state DFA M accepts a pair of words uv and vu with $uv \not = vu$, then it must accept a pair with either $|u| \le n^2$ or $|v| \le n^2$. Thus, it suffices to enumerate all $u \in \varSigma ^*$ of lengths $1, 2, \ldots , n^2$, and compute $M_u$ for each u. If at least one $M_u$ has $L(M_u)$ nonempty, then answer “yes”; otherwise answer “no”.    $\square$

An alternative approach for proving Theorem 8 was suggested by the referee, as follows:

Proof

We show that ACCEPTS-DISTINCT-CONJUGATES is decidable by reducing it to the functionality problem for nondeterministic streaming string transducers (NSSTs) [1]. An NSST is a one-way nondeterministic automaton equipped with a fixed set of variables in which to store strings. At each step, it reads a symbol from the input, changes state, and updates its string variables in parallel with a “copyless assignment”. At the end of the input, it produces an output string based on its string variables and final state. See [1] for details.

Consider the relation R defined as the set of pairs $\{(uv,vu)\in L(M) \times L(M)\}$. An NSST T can implement R as a transduction as follows. T uses two string variables X and Y. Let w be T’s input. T updates X with $X := X\sigma$ whenever a symbol $\sigma$ of w is read, until some nondeterministic transition, after which, as long as symbols $\sigma$ of w are read, the following updates are performed: $X := X$ and $Y := Y\sigma$. When the end of w is reached, $w = uv$ for $u = X$ and $v = Y$. During the computation, T uses its finite-state control to check that w is in L(M). At the same time, T checks that vu is in L(M) by guessing a state q of M, simulating M on u starting from q, verifying that M ends u in an accepting state, simulating M on v starting from $q_0$, and verifying that M ends v in q. If all of these checks succeed, T outputs $YX = vu$.

We say that T is functional if for every input string, T produces at most one output string. If T is functional, then for every $x \in L(M)$, x has at most one conjugate in L(M). Then since every string is a conjugate of itself, x has no conjugates other than x in L(M), and so M does not accept distinct conjugates. On the other hand, if M does not accept distinct conjugates, then for each input x, T can only produce x as output, and so T is functional. Therefore T is functional iff the answer to ACCEPTS-DISTINCT-CONJUGATES is “no”. By Theorem 4.1 of [1], checking if T is functional is decidable. Therefore ACCEPTS-DISTINCT-CONJUGATES is decidable.    $\square$

Our second decision problem is

ACCEPTS-NON-CONJUGATES

Instance: A DFA $M = (Q, \varSigma , \delta , q_0, F)$.

Question: Does M accept two words of the same length that are not conjugates?

We prove

Theorem 11

ACCEPTS-NON-CONJUGATES is decidable.

Proof

Given a formal language L over an ordered alphabet $\varSigma$, we define ${{\mathrm{lexlt}}}(L)$ to be the union, over all $n \ge 0$, of the lexicographically least word of length n in L, if it exists. As is well-known (see, e.g., [15, Lemma 1]), if L is regular, then so is ${{\mathrm{lexlt}}}(L)$. Furthermore, given a DFA for L, we can algorithmically construct a DFA for ${{\mathrm{lexlt}}}(L)$.

We also define ${{\mathrm{cyc}}}(L)$ to be the union, over all words $w \in L$, of the conjugates of w. Again, as is well-known (see, e.g., [14, Theorem 3.4.3]), if L is regular, then so is ${{\mathrm{cyc}}}(L)$. Furthermore, given a DFA for L, we can algorithmically construct a DFA for ${{\mathrm{cyc}}}(L)$.

We claim that L contains two words x and y of the same length that are non-conjugates if and only if L is not a subset of ${{\mathrm{cyc}}}({{\mathrm{lexlt}}}(L))$.

Suppose such x, y exist. Let t be the lexicographically least word in L of length |x|. If t is a conjugate of x, then y is not a conjugate of t, so $y \not \in {{\mathrm{cyc}}}({{\mathrm{lexlt}}}(L))$. On the other hand, if t is not a conjugate of x, then $x \not \in {{\mathrm{cyc}}}({{\mathrm{lexlt}}}(L))$. In both cases L is not a subset of ${{\mathrm{cyc}}}({{\mathrm{lexlt}}}(L))$.

Suppose L is not a subset of ${{\mathrm{cyc}}}({{\mathrm{lexlt}}}(L))$. Then there is some word of some length n in L, say x, that is not a conjugate of the lexicographically least word of length n, say y. Then x and y are the desired two words.

Putting this all together, we get our decision procedure for the decision problem ACCEPTS-NON-CONJUGATES: given the DFA M for L, construct the DFA $M'$ for $L - {{\mathrm{cyc}}}({{\mathrm{lexlt}}}(L))$ using the techniques mentioned above. If $M'$ accepts at least one word, then the answer for ACCEPTS-NON-CONJUGATES is “yes”; otherwise it is “no”.    $\square$

6 Final Remarks

We still do not know whether the following problem from [11, p. 363] is decidable:

ACCEPTS-INTEGER

Instance: A finite automaton M with input alphabet $(\varSigma _k)^2$.

Question: Is ${{\mathrm{quo}}}_k (L(M)) \, \cap \, {\mathbb {N}}$ nonempty?

Unfortunately our techniques do not seem immediately applicable to this problem.

We mention two other problems about finite automata whose decidability is still open:

• 1. Given a DFA M with input alphabet $\{ 0, 1\}$, decide if there exists at least one prime number p such that M accepts the base-2 representation of p.

Remark 12

An algorithm for this problem would allow resolution of the existence of a Fermat prime $2^{2^k} + 1$ for $k > 4$.

• 2. Given a DFA M with input alphabet $\{0, 1\}$, decide if there exists at least one integer $n\ge 0$ such that M accepts the base-2 representation of $n^2$.