0
$\begingroup$

I asked the converse just recently. But now trying to understand this version..

I'm working with case work and then I will take the union of all three cases where its strings with no zeros, 1 zero, and two zeros.

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

For one zero I have $1(11)^*0(11)^*|(11)^*0(11)^*1$

I'm confused about the two zeros case

Not sure if this is the right approach or if there is another method.

$\endgroup$
2
  • $\begingroup$ An alternate approach for one zero is $(11)$*$10(11)$*$|(11)$*$01(11)$*; perhaps that's more straightforward to generalize to two zeros? $\endgroup$ Commented Sep 12, 2023 at 20:25
  • $\begingroup$ Nothing wrong with the shorter $(11)^*(10|01)?(11)^*$, of course, covering zero or one zeroes. $\endgroup$ Commented Sep 12, 2023 at 20:42

1 Answer 1

Reset to default
1
$\begingroup$

You're on the right track! For no zeroes, your regex is correct. For one zero, it looks correct! For two zeroes, an even length string with two zeroes is the concatenation of two even length strings with one zero each, or two odd length strings with one zero each. You already came up with a regex for matching even length strings with one zero each, so I imagine you can adapt it for odd-length strings.

If I were building a regex, I would imagine an arbitrary even-length string with up to two zeroes in it. I would divide that string into blocks that are two characters long. Most of the blocks will probably be 11. When there is a zero in isolation, it will occur in a block like 01 or 10. Very rarely, you will get a string with a block that has two zeroes 00 in a row, in which case there must be only 1s throughout the rest of the string.

Putting these ideas together:

  • An even length string with a single zero in it: (11)*(01|10)(11)*
  • An even length string with two consecutive zeros appearing in a block together: (11)(00)(11)
  • An even length string with two zeroes that don't appear in the same block: (11)*(01|10)(11)*(01|10)(11)*
  • Putting this altogether: $$(11)^\star\quad(\epsilon | 00 | (01|10)(11)^\star(|01|10))\quad (11)^\star$$
$\endgroup$

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.