0
$\begingroup$

I have the following Regular Expression (classic Computer Science definition of Regular Expression, not PCRE or modern computer language RegEx):

{(ΣΣ)*00(ΣΣ)*}Σ ∪ Σ{(ΣΣ)*00(ΣΣ)*}

It "feels" like it should be reducible to me but I can't see how. Is it reducible or am I just asking for trouble trying? The term in {} just generates even-length strings that contain, at least, the substring 00.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

$(\Sigma \Sigma)^* (\Sigma 0 0 | 0 0 \Sigma) (\Sigma \Sigma)^* $

You need an even number of letters on the left and an odd number on the right, or the other way round.

Improve this answer
$\endgroup$
1
  • $\begingroup$ Interesting, thank you. I'm just envisioning the equivalent NFA and I think your answer is cleaner. Now let me see if I can derive it! $\endgroup$
    – Diode
    Commented Mar 28 at 18:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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