Simulations and Reductions in Finite Automata
Consider the following problem: If $A$ is any language, let $\sqrt{A}$ denote the set of first halves of strings in $A$, where both the first and second halves are identical $$\sqrt{A} = {x \mid \mbox{$xx \in A$}}$$ Show that if $A$ is regular, then so is $\sqrt{A}$. Proof Sketch Before trying to come up with a solution to this problem, let us understand what we can deduce simply from the problem statement:...