Question

Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string $\epsilon$ is divisible by three.

• A. $(0 + 1(01^*0)^*1)^*$
• B. $(0 + 11 + 10(1 + 00)^*01)^*$
• C. $(0^*(1(01^*0)^*1)^*)^*$
• D. $(0 + 11 + 11(1 + 00)^*00)^*$

Hint:

Regular expressions for divisibility properties are best verified by mapping them to cycles of the corresponding modulo DFA.

Answer 1

The Correct Option is A, B, C

To determine which regular expressions represent the set of all binary numbers divisible by three, we need to analyze each option. Binary numbers divisible by three can be recognized by certain repeating patterns. We will evaluate each given regular expression to determine if it satisfies this condition. We assume that the empty string, \epsilon, is divisible by three.

1. Regular Expression: (0 + 1(01^*0)^*1)^*
   • This expression starts with 0 or a sequence involving patterns 1(01^*0)^*1. This captures numbers with specific combinations of 0s and 1s, where each 'block' terminates with 1, indicating successful division checkpoints.
   • The (01^*0) part results in zero or more occurrences of 0 between two 1s, symbolizing balanced binary pairs critical in divisible sets.
   • Repeating this in multiple blocks covers numbers like 0, 11, 110, 111, etc. Thus, this expression caters to binary numbers divisible by three.
2. Regular Expression: (0 + 11 + 10(1 + 00)^*01)^*
   • This expression covers a basic pattern 0, solely representing divisible by three numbers.
   • The 11 part signifies the simplest binary divisible by three.
   • The 10(1 + 00)^*01 represents sequences that end back into a divisible format, encompassing broader cases like duplicating or interspersing with zeros.
   • With its comprehensive composite structures, it captures the requirements for divisibility by three in binary.
3. Regular Expression: (0^*(1(01^*0)^*1)^*)^*
   • The 0^* allows for leading zeros that remain neutral in divisibility checks.
   • The core segment (1(01^*0)^*1)^* incorporates repetitions of blocks pivotal in forming numbers divisible by three.
   • It replicates conditions where internal zeros and endpoint ones solidify a divisible outcome, hence, aptly fits our divisibility rule.
4. Regular Expression: (0 + 11 + 11(1 + 00)^*00)^*
   • Though it recognizes patterns with 0 and 11, adding 11(1 + 00)^*00 deviates.
   • Instead of guaranteeing divisibility through expanding and repeating, it exits on double zero as a closure, failing even checks.
   • This structure doesn't ensure resulting sequences remain divisible by three, causing it to not fully deliver on deterministic criteria.

Thus, the correct answers are:

• (0 + 1(01^*0)^*1)^*
• (0 + 11 + 10(1 + 00)^*01)^*
• (0^*(1(01^*0)^*1)^*)^*

These expressions correctly generate all binary numbers divisible by three, with the rules described effectively addressing the divisibility conditions through regular patterns.