Given a DFA $A$, find a polynomial-time algorithm to determine if a word in the form $ww$ is in $L(A)$

Question

Given a DFA $A$ with $|\Sigma|\ge 2$, find a polynomial-time algorithm to determine if there exists a word in the form $ww$ in $L(A)$.

Answer 1

Let $I_t$ be the automaton obtained from $A$ by making $t$ the only final state. Let $F_t$ be the automaton obtained from $A$ by making $t$ the initial state.

The number of the $I_t$ and $F_t$ automata is linear in the number of states of $A$. For each pair of automata, $(I_t, F_t)$, check whether the intersection of their languages is non-empty.

If the language of pair $(I_t, F_t)$ is non-empty, it contains a word $w$ such that $ww \in L(A)$. (The run of $ww$ in $A$ goes through $t$.) The algorithm clearly runs in polynomial time.