0
$\begingroup$

Also followup question is the set of all binary strings that are of even length with at least two zeros.

But for both questions I'm thinking of building my regular expression with casework, no zeroes, 1 zero, and two zeroes.

For no zeros I have: $(11)^*$

For one zero there just seems to be too many edge cases to also keep the string of even length. You have to consider the zero being at the start or somewhere in the middle or at the end. All while having the expression match any number of odd 1s.

I'm confused how to do this and looking for any insights on how to do this problem and the follow up. Thanks

$\endgroup$
2
  • 1
    $\begingroup$ You could express the string as a sequence of pairs of digits, at least one of which is (00|01|10). $\endgroup$ Commented Sep 12, 2023 at 19:17
  • $\begingroup$ So (..)*(.0|0.)(..)* works, where . matches any single symbol. $\endgroup$ Commented Sep 12, 2023 at 19:37

1 Answer 1

Reset to default
1
$\begingroup$

Wlog, "10" or "01" or "00" needs to be somewhere, so we start with that.

There are two cases:

Case 1: (odd number of digits)(10|01|00)(odd number of digits)
Case 2: (even number of digits)(10|01|00)(even number of digits)

Case 1: (00|01|10|11)*(1|0)(10|01|00)(1|0)(00|01|10|11)*
Case 2: (00|01|10|11)*(10|01|00)(00|01|10|11)*

Edit: As Karl pointed out, these two cases end up actually being the same, so you really only need case 2.

$\endgroup$
5
  • $\begingroup$ These two cases are redundant. $\endgroup$ Commented Sep 12, 2023 at 19:33
  • $\begingroup$ Oh, could you elaborate? $\endgroup$ Commented Sep 12, 2023 at 19:34
  • $\begingroup$ Well, can you think of an instance of case 1 that isn't an instance of case 2? The 10|01 already allows the 0 to occur at an even position or an odd position. $\endgroup$ Commented Sep 12, 2023 at 19:35
  • 1
    $\begingroup$ Ah, good point. I'll leave my original answer up because that's what first came to mind. $\endgroup$ Commented Sep 12, 2023 at 19:37
  • $\begingroup$ @ScottHahn Any ideas for how to work on the converse? math.stackexchange.com/questions/4768051/… $\endgroup$ Commented Sep 12, 2023 at 20:18

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.