L is a regular language. Is $L' = \{a^{|w|} : w \in L\} $ a regular language?

Question

Let $ L \subseteq \{a,b\}^*$ be a regular language.

Is $L' = \{ {a^{|w|} : w \in L} \}$ a regular language?

We tried to define a function $f$ such that $f(r)=r'$ so that $ L(r')=L'$ but we couldn't develop it into something useful.

Will appriciate any hint or directions.

Answer 1

Use complete induction on $|r|$. When $|r| = 1$ easily find a regular expression $r'$ such that defines $L'$. Then assume for any $|r|<n$ that a regular expression $r'$ exists, such that defines $L'$. And finally, prove for $|r| = n$.

1. There exists $r_1$ and $r_2$ such that $r = ((r_1)\cup(r_2))$.
2. There exists $r_1$ and $r_2$ such that $r = ((r_1)\circ(r_2))$.
3. There exists $r_1$ such that $r = (r_1)^*$.

Those are the three cases $r$ can be built using regular expressions with a smaller length than $n$, and then the assumption can be used.

P.S: If you're from BGU, which I think you are, look at practical session 2, last exercise, very similar.

Answer 2

HINT: Let $M$ be a DFA that accepts $L$. Modify $M$ to get an NFA that accepts $L'$.