1
$\begingroup$

Prove that the regular expression $\Sigma\Sigma(ab\cup ba)^∗a$ rejects the string $aabaabba$.

Would this be because the union of $ab$ and $ba$ would not accept the string $aabaabba$? I'm just confused on how to explain it.

$\endgroup$
2
  • 1
    $\begingroup$ I don't know what "ΣΣ" means. Please also use MathJax to type math. $\endgroup$ – Dmitry Apr 7 at 20:01
  • $\begingroup$ Presumably $\Sigma$ stands for $a \cup b$. $\endgroup$ – Yuval Filmus Apr 8 at 6:56
2
$\begingroup$

Any word accepted by this regular expression has to be either in length 3 or to end with $aba$ or $baa$.

Try to prove this fact, and use it to show that $aabaabba$ must be rejected.

$\endgroup$
2
  • $\begingroup$ I think it should be "end with $aba$ or $baa$". $\endgroup$ – Nathaniel Apr 7 at 19:41
  • $\begingroup$ Yes. I made a typo there :o $\endgroup$ – nir shahar Apr 7 at 20:07

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.