GATE 2021 CS-Set-2
August 22, 2023KVS 30-12-2018 Part-A
August 22, 2023GATE 2021 CS-Set-2
Question 12 |
(0+1 (01*0)*1)* | |
(0+11+10(1+00)*01)* | |
(0*(1(01*0)*1)*)* | |
(0+11+11(1+00)*00)* |
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.
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.