regular language proof, a language partial to a regular one

Question

So, I've been trying to solve a question I got and I think I'm correct but I'm not positive. Is the language {w| www belongs to L' and L' is regular} regular? I couldnt find any way to prove it isnt regular so I thought maybe it is, What I considered is the next scenario, assume that we have the automaton A(L') We look at the Delta(q0,www) = qF for every word of the form www in L' , and we can assume that there exist a state qi that Delta(q0,w) = qi, and Delta(qi,ww) = qF, So because thats true (for obvious reasons) I can build an automaton that the state qi is an accepting state for every word www in the original automaton and remove other accepting states from the automaton and now we have an automaton that accepts the word w for every word www that existed in L' which means L is regular (cause it has a dfa/nfa). keep in mind, w is a complete word of unknown length.

Is this basic idea correct or am I missing a hole in my idea ?

Answer 1

Suppose that $M=\langle Q,\Sigma,\delta,q_0,F\rangle$ is a DFA that recognizes $L'$; we can construct a DFA $M'=\langle Q',\Sigma,\delta',q_0',F'\rangle$ that recognizes $L$ as follows.

$Q'$ is the set of all functions from $Q$ to $Q$. A state $f\in Q'$ is an acceptor state in $M'$ if $f^3(q_0)\in F$, where $f^3(q)=f(f(f(q)))$; i.e., $F'=\{f\in Q':f^3(q_0)\in F\}$. The initial state $q_0'$ is the identity function on $Q$. It only remains to define the transition function $\delta'$.

For each $w\in\Sigma$ let $f_w:Q\to Q:q\mapsto\delta(q,w)$. Then for $f\in Q'$ and $a\in\Sigma$ we define $$\delta'(f,a)=f\circ f_a\;;$$ this makes sense, since $f\circ f_a$ is a function from $Q$ to $Q$ and is therefore an element of $Q'$, i.e., a state of $M$.

I leave it to you to show that this DFA $M'$ recognizes $L$. You’ll want to prove (by induction on the length of $w$) that $\delta'(q_0',w)=f_w$ for each $w\in\Sigma^*$.

By the way, by suitably modifying $F'$ you can use this construction to prove that a variety of languages related in similar ways to $L'$ are regular.

Answer 2

Hint. Assume that you have a DFA for $L'$ whose set of states is $Q$ and transition rule $\delta_1$. Now construct a new DFA whose set of states is $\mathcal P(Q\times Q)$ and transition rule $$ \delta_2(X,a) = \{ (q,\delta_1(q',a)) \mid (q,q') \in X\} $$

Now, an appropriate choice of initial and accepting states will solve your problem.

Answer 3

An easy way to prove this result is to use the fact that a language is regular if and only if it is recognized by a finite monoid.

Definition. A language $L$ of $A^*$ is recognized by a finite monoid $M$ if there is a surjective monoid morphism $f:A^* \to M$ and a subset $P$ of $M$ such that $f^{-1}(P) = L$.

Let now $K = \{u \in A^* \mid u^3 \in L\}$ and let $Q = \{m \in M \mid m^3 \in P \}$. Then we have \begin{array} {}f^{-1}(Q) &= \{ u \in A^* \mid f(u)^3 \in P \} = \{ u \in A^* \mid f(u^3) \in P \} \\ &= \{ u \in A^* \mid u^3 \in f^{-1}(P) \} = \{ u \in A^* \mid u^3 \in L \} \\ &= K \end{array} Thus $K$ is regular.