# Regular Expression

 Question 1
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.
[MSQ]
 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)^*$
GATE CSE 2021 SET-2   Theory of Computation
Question 1 Explanation:
 Question 2
Which one of the following regular expressions represents the set of all binary strings with an odd number of 1's?
 A $((0+1)^* 1(0+1)^*1)^*10^*$ B $(0^*10^*10^*)^*0^*1$ C $10^*(0^*10^*10^*)^*$ D $(0^*10^*10^*)^*10^*$
GATE CSE 2020   Theory of Computation
Question 2 Explanation:
 Question 3
In some programming language, an identifier is permitted to be a letter followed by any number of letters or digits. If $L$ and $D$ denote the sets of letters and digits respectively, which of the following expressions defines an identifier?
 A $(L+D)^{+}$ B $\text { (L.D)* }$ C $L(L+D)^{*}$ D $L(L . D)^{*}$
ISRO CSE 2017   Theory of Computation
Question 3 Explanation:
 Question 4
Let $L=\left\{w \in(0+1)^{*} \mid w \text { has even number of } 1 \text { 's }\right\}$, i.e. $L$ is the set of all bit strings with even number of 1's. Which one of the regular expression below represents $L$?
 A $(0^*10^*1)^*$ B $0^*(10^*10^*)^*$ C $0^*(10^*1^*)^*0^*$ D $0^*1(10^*1)^*10^*$
ISRO CSE 2016   Theory of Computation
Question 4 Explanation:
 Question 5
Which one of the following regular expressions represents the language: the set of all binary strings having two consecutive 0s and two consecutive 1s?
 A (0+1)*0011(0+1)*+(0+1)*1100(0+1)* B (0+1)*(00(0+1)*11+11(0+1)*00)(0+1)* C (0+1)*00(0+1)*+(0+1)*11(0+1)* D 00(0+1)*11+11(0+1)*00
GATE CSE 2016 SET-1   Theory of Computation
Question 5 Explanation:
 Question 6
The length of the shortest string NOT in the language (over $\Sigma$={a,b}) of the following regular expression is _________.
a*b* (ba)* a*
 A 1 B 2 C 3 D 4
GATE CSE 2014 SET-3   Theory of Computation
Question 6 Explanation:
 Question 7
Let L = {w $\in$ (0 + 1)*|w has even number of 1s}, i.e. L is the set of all bit strings with even number of 1s. Which one of the regular expressions below represents L?
 A (0 *10 *1) * B 0 * (10 *10 *) * C 0 * (10 *1) * 0 * D 0 *1(10 *1) *10 *
GATE CSE 2010   Theory of Computation
Question 7 Explanation:
 Question 8
Which one of the following languages over the alphabet {0,1} is described by the regular expression: (0+1)*0(0+1)*0(0+1)*?
 A The set of all strings containing the substring 00. B The set of all strings containing at most two 0's. C The set of all strings containing at least two 0's. D The set of all strings that begin and end with either 0 or 1
GATE CSE 2009   Theory of Computation
Question 8 Explanation:
 Question 9
Which of the following regular expressions describes the language over$\{0, 1\}$ consisting of strings that contain exactly two 1's?
 A $(0 + 1)^ * \ 11(0 + 1) ^*$ B $0 ^* \ 110 ^*$ C $0 ^* 10 ^* 10 ^*$ D $(0 + 1) ^* 1(0 + 1) ^* 1 (0 + 1) ^*$
GATE IT 2008   Theory of Computation
Question 9 Explanation:
 Question 10
Consider the regular expression $R = (a + b)^* \ (aa + bb) \ (a + b)^*$
Which one of the regular expressions given below defines the same language as defined by the regular expression R ?
 A $(a(ba)^* + b(ab)^*)(a + b)^+$ B $(a(ba)^* + b(ab)^*)^*(a + b)^*$ C $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^*$ D $(a(ba)^* (a + bb) + b(ab)^*(b + aa))(a + b)^+$
GATE IT 2007   Theory of Computation
Question 10 Explanation:
There are 10 questions to complete.

### 7 thoughts on “Regular Expression”

1. Options wrong

Reply
• Please specify the question number and option which you fell as wrong.

Reply
• 7th C option is wrong

Reply
• Thank You shivam,
We have updated the option C.

Reply
2. Q11 options A and B don’t have a final state.

Reply
• Thank You,
We have updated the figure as per your suggestion.

Reply