GateAI
Regular Expressions and Finite Automata

GATE CSE 2020 · Q7

MCQ1 markMedium

Time

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?

Select one answerSingle correct

Pick an option to check

Solution

Step-by-step verified solution

Official answer: D

Regular Expressions and Finite Automata

A binary string with an odd number of 11's consists of an odd number of 11's separated and surrounded by any number of 00's.

Evaluating the visible options:

  • Option (A): ((0+1)∗1(0+1)∗1)∗10∗((0 + 1)^*1(0 + 1)^*1)^*10^* can generate strings with an even number of 11's because (0+1)∗(0+1)^* allows any number of 11's within it.

  • Option (B): (0∗10∗10∗)∗0∗1(0^*10^*10^*)^*0^*1 requires the string to end with a 11, failing to generate strings with an odd number of 11's that end in 00 (e.g., 1010).

According to the official answer key, the correct option is (D) (which is located on the next page: 0∗10∗(0∗10∗10∗)∗0^*10^*(0^*10^*10^*)^* or equivalent form).

*(Note: Options C and D are located on the subsequent page; this question continues onto the next page).*

Try the question first, then check your work.

Think the official key or this write-up is wrong?

Report error or challenge

Examiner trap

The misconception this question tests

This Regular Expressions and Finite Automata previous year question is Q7 of the GATE CSE 2020 paper. Find more GATE CSE PYQs on Regular Expressions and Finite Automata in Theory of Computation, or browse all GATE CSE PYQs.

Free diagnostic

Where do you stand for GATE?

Take the 20-minute diagnostic: the 3 topics that cost you the most marks, and a rank range. Or sit 5 related Regular Expressions and Finite Automata PYQs now with no account.

One GATE CSE PYQ every morning

An official question by email at 7 AM IST, with a link to its verified solution. Unsubscribe in one click.

Regular Expressions and Finite Automata in GATE CSE

Regular Expressions and Finite Automata has 41 GATE CSE PYQs across 24 papers from 2011 to 2026. 14 of them are 1-mark MCQs like this one, and GATE CSE 2020 has 2.

How GATE tests Regular Expressions and Finite Automata

More from GATE CSE 2020

Share this solution

A plain-text card for WhatsApp or Telegram study groups.

GateAI solution cardGATE CSE 2020 · Q7 · MCQ

Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?

Topic-wise GATE CS PYQs with verified steps

Independent practice explanation verified by the GateAI team. GATE is conducted by the IITs; question text follows the official paper.