August 22, 2023
August 22, 2023
August 22, 2023
###### KVS 30-12-2018 Part-A
August 22, 2023
 Question 12
Which of the following regular expressions represent(s) the set of all binary numbers that are divisible by three? Assume that the string ∊ 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)*
Question 12 Explanation:

Transition table

 0 1 ->*q0 q0 q1 q1 q2 q0 q2 q1 q2

DFA of divisible by 3

The regular expression will be

Three paths to reach to final state from initial state

Path 1: self loop of 0 on q0

Path 2: q0->q1->q0  hence 11

Path 3: q0->q1->q2->q1->q0 hence 10(1+00)*01

So finally the regular expression will be

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

Other regular expression is (if we consider two paths)

Path 1: Path 1: self loop of 0 on q0

Path 2: q0->q1->q2*->q1->q0

Hence regular expression

(0+1 (01*0)*1)*

Another regular expression is (if we consider only one path and remaining part is present inside this path as cycles)

q0->q1->q2->q1->q0

Another regular expression is

(0*(1(01*0)*1)*)*

So A,B, C are correct.

Option D generates string 11100 which is not accepted by FA hence wrong.

Question 12 Explanation:

Transition table

 0 1 ->*q0 q0 q1 q1 q2 q0 q2 q1 q2

DFA of divisible by 3

The regular expression will be

Three paths to reach to final state from initial state

Path 1: self loop of 0 on q0

Path 2: q0->q1->q0  hence 11

Path 3: q0->q1->q2->q1->q0 hence 10(1+00)*01

So finally the regular expression will be

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

Other regular expression is (if we consider two paths)

Path 1: Path 1: self loop of 0 on q0

Path 2: q0->q1->q2*->q1->q0

Hence regular expression

(0+1 (01*0)*1)*

Another regular expression is (if we consider only one path and remaining part is present inside this path as cycles)

q0->q1->q2->q1->q0

Another regular expression is

(0*(1(01*0)*1)*)*

So A,B, C are correct.

Option D generates string 11100 which is not accepted by FA hence wrong.