...
GATE 2021 CS-Set-2
August 22, 2023
KVS 30-12-2018 Part-A
August 22, 2023
GATE 2021 CS-Set-2
August 22, 2023
KVS 30-12-2018 Part-A
August 22, 2023

GATE 2021 CS-Set-2

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.

Correct Answer: B
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.

0 0 votes
Article Rating
Subscribe
Notify of
0 Comments
Inline Feedbacks
View all comments
0
Would love your thoughts, please comment.x
()
x
error: Alert: Content selection is disabled!!