2
$\begingroup$

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).

$\endgroup$
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ That should do the trick.Thank you very much! $\endgroup$ – Thresh Bot Aug 30 '18 at 15:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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