I've started learning automata recently, and am struggling to figure out how to find a finite automaton that satisfies the following:
Given DFA $A_1 = (Q, \Sigma, \delta, q_0, F)$, find a finite automaton $A_2$ such that $$L(A_2) = \{s \mid (s\cdot s) \in L(A_1)\}$$ Where $s\cdot s$ is the concatenation of $s$ onto itself.

I can't seem to grasp how to get the automaton to "remember" $s$ so that I can check it twice, any tips on how to find such an automaton?

  • 1
    $\begingroup$ The intuitive approach is not that you "remember $s$ and check it twice", but that you check the two occurrences of $s$ in parallel. $\endgroup$ Mar 30 at 11:41
  • $\begingroup$ Thanks, Nathaniel! That post gave me good insight on how to go about it. $\endgroup$
    – Daniel
    Mar 30 at 13:05


Browse other questions tagged or ask your own question.