###### GATE 2021 CS-Set-2

August 22, 2023###### KVS 30-12-2018 Part-A

August 22, 2023# GATE 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 | 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 | 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.