# regular language proof, a language partial to a regular one

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 ?

• What if there is another word $u$ such that $\delta(q_0,u)=q_i$, but $\delta(q_i,uu)$ is not an acceptor state (i.e., $uuu\notin L'$)? – Brian M. Scott Dec 12 '14 at 2:45
• By "{w| www belongs to L' and L' is regular}", do you mean that $w$ is in the language if only there is some regular $L'$ (which may depend on $w$) that contains $www$? If so, the language is the set of all strings ... – Henning Makholm Dec 12 '14 at 2:48
• Or is $L'$ given, and you're looking for the language $\{w\mid www\in L'\}$? – Henning Makholm Dec 12 '14 at 2:51
• Henning I assume L' is given as some regular language and I'm looking for {w∣www∈L′}, Brian if uuu ∉ L' then the qi state will not be accepting in the new automaton I'm constructing, to easier explain my approach think of an automaton representing L' assume there is a word accepted there , if it is of the type uuu then just turn the state after the first u to accepting and remove the rest, rince and repeat with all words of that type. – ron Dec 12 '14 at 2:56
• @ron: That’s not clear. On the one hand, $w$ makes $q_i$ an accepting state; on the other hand, $u$ makes $q_i$ a non-accepting state. How do you resolve that? And even if you can, how are you going to rinse and repeat if $L'$ contains infinitely many words of the form $vvv$? – Brian M. Scott Dec 12 '14 at 3:02

## 3 Answers

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.

• thank you for the detailed explanation ! appriciated! – ron Dec 12 '14 at 3:56
• @ron: You’re welcome! – Brian M. Scott Dec 12 '14 at 3:57

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.

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.