Given L is regular, Prove/Disprove that the following language is regular or not. $EXP = \{w| w^{|w|} ∈L\}$

  • 1
    $\begingroup$ What do you think? What have you tried, and where did you get stuck? $\endgroup$ – Yuval Filmus Feb 4 '18 at 16:17
  • $\begingroup$ Welcome to Computer Science! We discourage posts that simply state a problem out of context, and expect the community to solve it. Assuming you tried to solve it yourself and got stuck, it may be helpful if you wrote your thoughts and what you could not figure out. It will definitely draw more answers to your post. Until then, the question will be voted to be closed / downvoted. You may also want to check out these hints, or use the search engine of this site to find similar questions that were already answered. $\endgroup$ – Raphael Feb 4 '18 at 17:36
  • $\begingroup$ Oh, I did to try to find and used others to solve this. I'm sorry I should've mentioned my thoughts. Thanks! $\endgroup$ – Jatin Arora Feb 5 '18 at 17:39

Suppose that $L$ is accepted by a DFA with states $Q$, initial state $q_0$, accepting states $F$, and transition function $\delta$.

With every word $w$ we can associate the function $\delta_w\colon Q \to Q$ given by $\delta_w(q) = \delta(q,w)$. Note that there are finitely many such function. It is not hard to check that for any such function $\delta_w$, the language $L_{\delta_w} = \{ x : \delta_x = \delta_w \}$ is regular.

We can also associate with $w$ a set $N_w = \{ n \in \mathbb{N} : \delta(q_0,w^n) \in F \}$. Note that $N_w$ depends only on $\delta_w$, and so there are finitely many such sets. Moreover, each of them is eventually periodic (why?), and so the language $L_{N_w} = \{ x : |x| \in N_w \}$ is regular.

Combining the two observations, we see that $$ EXP = \bigcup_{w \in \Sigma^*} (L_{\delta_w} \cap L_{N_w}). $$ While the sum is infinite, there are only finitely many different summands, and we deduce that $EXP$ is regular.

| cite | improve this answer | |

Not the answer you're looking for? Browse other questions tagged or ask your own question.