Skip to content
GATEiit

GATE CSE 2021 Set 2 Q57: Regular expressions for binary numbers divisible by three

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.

Try it: multiple select: one or more correct options

Select one or more options
Select all correct options. No negative marking, no partial marks.
Show answer and explanation

Answer: A, B, C (official GATE 2021 final answer key)

Concept used: The mod-3 DFA has states 0, 1, 2; a regular expression for it describes all loops on state 0.

First step: Draw the DFA (state = value mod 3, reading bits left to right) and write the ways to leave state 0 and come back to it.

Full step-by-step solution

Detailed working, common mistakes and linked mock tests will be available with a free GATEiit account. Log-in is coming soon.

Share this question

WhatsAppDownload image

Source: official GATE 2021 Set 2 CS question paper and final answer key, organised by IIT Bombay. Question paper · Answer key

More Theory of Computation PYQs

PracticePractise Theory of Computation questions →Full paperAll GATE CSE 2021 Set 2 questions →