3
$\begingroup$

Let $A$ be a regular language, let $A'=\{xz\}$ such that for some $y,|x|=|y|=|z|$ and $xyz\in A$. Show that $A'$ is not necessarily regular language.

This is an excercise of Sipser, I've no idea how to construct $A,A'$ please help someone

$\endgroup$
3
  • $\begingroup$ actually I've no idea, I showed it regular if it was "exist $|y|$ such that $|x|=|y|$ and $xy\in A$ " but no idea for this case $\endgroup$ – James Yang Aug 25 '14 at 16:50
  • $\begingroup$ Please note our reference questions. In general, problems dumps such as this are problematic for SE; we don't really know what your problem is so there's little we can do to teach you fish. $\endgroup$ – Raphael Aug 26 '14 at 8:41
  • 1
    $\begingroup$ L = {nonrexxxxxgular} ... $\endgroup$ – J.-E. Pin Aug 26 '14 at 10:19
3
$\begingroup$

Hint: Let $A = a^+ b^+ c^+$ and consider $A' \cap a^+c^+$.

$\endgroup$
1
  • 1
    $\begingroup$ @RickDecker I hope that even in your part of the world, set intersection does not allow you to cut letters out of words. ;) $\endgroup$ – Raphael Aug 26 '14 at 8:43

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.