I have been stuck on this problem for a couple of hours and can't seem to figure it out.A bit of a hand would be nice.So we have that odd(w) is the letters from the string w that are in odd positions for w(have in mind odd(w) isn't the string from w with an odd length).So I found out by building a NFA I was able to prove that if w is regular then odd(w) is regular but am having a difficult time to find out if the reverse is true(if odd(w) is regular=>w is regular FOR EVERY regular language).
Is it ALWAYS true that if L= {w|odd(w) is regular} then L is regular.
automataregular-language
Best Answer
I believe the language L=$\{(ab)^na(ca)^n\}$ is a counterexample. $odd(L)=\{{a^{2n}}\}$, so it is regular, but $L$ is not regular (analogously to how $\{b^nc^n\}$ is not regular).