Provide a polynomial time algorithm that decides whether or not the language recognized by some input DFA consists entirely of palindromes

Question

Everything needed to know is in the question statement. I believe that the DFA has to be acyclic (meaning its language is finite), which can be checked in polynomial time. However, finding all paths from the start state to an accept state can run in exponential time in worst-case.

Answer 1

I will give a general algorithm going through intermediate steps that can be implemented in polynomial time, each. Yet, I will not dive into the details of how to implement each step. The solution I'm suggesting may not be optimal, yet it is easy to understand. Essentially, we're going to rely on basic properties of Pushdown automata (PDAs, for short).

Let $\mathcal{A}$ be a given DFA over the alphabet $\Sigma$, and consider the language $PAL\subseteq \Sigma^*$ of the palindrome words. We need to decide whether $L(\mathcal{A})\subseteq PAL$ in polynomial time. Note that $L(\mathcal{A})\subseteq PAL$ iff $L(\mathcal{A})\cap \overline{PAL} = \emptyset$. So we need to decide whether the language $L(\mathcal{A})\cap \overline{PAL}$ is empty, and we do it as follows:

1- Construct a PDA $\mathcal{B}$ for $\overline{PAL}$: this is a well known exercise.

2- Construct a PDA $\mathcal{C}$ for $L(\mathcal{A})\cap \overline{PAL}$: this is also known, and can be done in polynomial time by a product construction of $\mathcal{A}$ and $\mathcal{B}$ (for example, see here).

3- Finally, check whether the language of the PDA $\mathcal{C}$ is empty. This also can be done in polynomial time (see here, or here).

Answer 2

The most straightforward way is the following:

Let $p(u,v)$ ("p" for palindrome) be a predicate which means "any path from $u$ to $v$ is a palindrome". We are interested in $p(S, F)$ for each starting state S and each finishing state F. To compute it, we need an auxiliary predicate $c(u,v)$ ("c" for connected): "there exists a pat from state $u$ to state $v$". $c$ can be computed in $O(n^3)$ time using transitive closure.

Let $E$ be the set of transitions. Let $\ell(u,v)$ be the label (symbol) on edge $u \to v$. Then:

$$p(u,v) = false,\ \ \text{if $\exists u', v':\ (u,u'), (v', v) \in E,\ c(u',v')=true,\ \ell(u,u') \ne \ell(v',v)$}$$ Simply put, if there is a path $u \to u' \leadsto v' \to v$ such that the first and the last symbols don't match, $p(u,v)$ is false.

If such a path doesn't exist, we can define $p(u,v)$ recursively: $$p(u,v) = \land_{u', v':\ (u,u'), (v', v) \in E,\ c(u',v')=true} p(u', v')$$ I.e. if there is a path $u \to u' \leadsto v' \to v$ such that $u' \leadsto v'$ is not a palindrome, then $p(u,v)$ is not a palindrome.

Now, we can write a DFS-like solution. Let $G$ be a graph where vertices are pairs of states and edges are as defined by the second equation: $$ (u,v) \to (u',v') \iff (u,u'), (v', v) \in E,\ c(u',v')=true $$ Intuitively, an edge leads from a problem to a "subproblem".

Our starting vertices for DFS are $(S,F)$ for each starting state $S$ and each finishing state $F$. We need to check that none of these vertices reaches a "bad" vertex, where $(u,v)$ is bad if it fails the condition from the first equation, i.e.: $$\exists u', v':\ (u,u'), (v', v) \in E,\ c(u',v')=true,\ \ell(u,u') \ne \ell(v',v)$$ This is a standard use-case for DFS or BFS.

Answer 3

The following doesn't necessarily answer the question, but might be of interest.

Suppose that $L$ is a regular language consisting entirely of palindromes, and suppose that $L$ is accepted by a DFA having $n$ states. According to the pumping lemma, every word $w \in L$ of length at least $n$ can be decomposed as $xyz$ such that $|xy| \leq n$, $y \neq \epsilon$, and $xy^iz \in L$ for all $i \geq 0$.

Suppose that $w$ has length at least $2n$, so that $|z|\ge |x|+|y|$. Choose $i$ so that $|x|+i|y| \geq |z|$. Since $xy^iz \in L$, we have $xy^iz = z'(y')^ix'$, where $w'$ is the reverse of $w$. In particular, we can write $y=st$ so that for some $j \geq 1$ we have $z' = xy^js$. Since $xz$ is also a palindrome, we have $$ xs'(t's')^jx' = xz = z'x' = x(st)^jsx'. $$ This shows that $s=s'$ and $t=t'$, that is, $s,t$ are palindromes, and the entire word has the form $w = x(st)^{j+1}sx'$. The proof of the pumping lemma shows that the first occurrence of $st$ corresponds to a cycle in the DFA, and this shows that in fact $x(st)^ksx' \in L$ for all $k \geq 0$.

We deduce that there is a finite language $F$ and a finite collection $R$ of words $(x,s,t)$, where $s,t$ are palindromes, such that $$ L = F \cup \bigcup_{(x,s,t) \in R} x(st)^*sx'. $$ Conversely, every language of this form is regular and consists of palindromes.