## Regular-Expressions

 Question 1

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
Theory-of-Computation       Regular-Expressions       2016 set-01
Question 1 Explanation:
Option A doesn’t generate string “001011” as it has two consecutive 0’s and two consecutive 1’s.
Option C generates string “00” which doesn’t have two consecutive 1’s.
Option D doesn’t generate string “00110” which has two consecutive 0’s and two consecutive 1’s.
 Question 2

 A 4 B 5 C 6 D 8
Theory-of-Computation       Regular-Expressions       GATE 2015(Set-03)
Question 2 Explanation:
No. of states in DFA accepting L and complement of L is same. So let's draw minimal DFA for L,

So, 5 states are there.
 Question 3
Which of the regular expressions given below represent the following DFA?
```I) 0*1(1+00*1)*
II) 0*1*1+11*0*1
III) (0+1)*1```
 A I and II only B I and III only C II and III only D I, II, and III
Compiler-Design       Regular-Expressions       GATE 2014(Set-01)
Question 3 Explanation:
The DFA accepts the language “all strings ending with 1”.
So the regular expression corresponding to DFA is (0+1)*1.
Now, by using state elimination method,
So the DFA also has another equivalent regular expression: 0*1(1+00*1)*.
But the regular expression (0*1*1+11*0*1) is not equivalent to DFA, as the DFA also accept the string “11011” which cannot be generated by this regular expression.
 Question 4
Let L = {w ∈ (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 expression below represents L?
 A (0 * 10 * 1)* B 0 * (10 * 10*)* C 0*(10 * 1*)*0* D 0 * 1(10 * 1)*10*
Theory-of-Computation       Regular-Expressions       2010
Question 4 Explanation:
The best way to find correct answer is option elimination method. We will guess strings which has even number of 1’s and that is not generated by wrong options OR which generate strings which doesn’t have even number of 1’s.
Option A: (reg expr: (0*10*1)* ) doesn’t generate string such as { 110, 1100,....}
Option C: (reg expr: 0*(10*1*)*0* generate string such as {1, 111,....} which have odd number of 1’s.
Option D: (reg expr: 0*1(10*1)*10* doesn’t generate strings such as { 11101, 1111101, ….}.
 Question 5
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.
Theory-of-Computation       Regular-Expressions       2009
Question 5 Explanation:
Option A is false, as the regular expression generates string “010” which doesn’t have “00” as substring. Option B is false, as we can have the string “000” from the given regular expression, which has more than two 0’s. Option D is false, as we cannot generate the string “01” from the given regular expression and according to option D, string “01” must be generated by regular expression, which clearly shows option D is not correct language as per regular expression.
 Question 6
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) *
Theory-of-Computation        Regular-Expressions       Gate 2008-IT
Question 6 Explanation:
Option A: (0+1)* 11(0+1)*
→ 1110 this consists of 3 ones but accepted by given expression. So this is false.
Option B: 0* 110*
→ 0101 this string consists of two is but not accepted by given expression. This is false.
Option C: 0* 10* 10*
→ This is true.
Option D: (0+1)* 1(0+1)* 1(0+1)*
→ 011010 - This can have three is but accepted by given expression. So this is also false.
 Question 7
The regular expression 0*(10*)* denotes the same set as
 A (1*0)*1* B 0+(0+10)* C (0+1)*10(0+1)* D None of the above
Theory-of-Computation       Regular-Expressions       Gate-2003
Question 7 Explanation:
Both (A) and the given expression generates all strings over Σ.
Option (B) and (C) doesn't generate 11.
 Question 8
Let S and T be language over Σ = {a,b} represented by the regular expressions (a+b*)* and (a+b)*, respectively. Which of the following is true?
 A S ⊂ T B T ⊂ S C S = T D S ∩ T = ɸ
Theory-of-Computation       Regular-Expressions       Gate-2000
Question 8 Explanation:
If we draw DFA for language S and T it will represent same.
 Question 9
If the regular set A is represented by A = (01 + 1)* and the regular set ‘B’ is represented by B = ((01)*1*)*, which of the following is true?
 A A ⊂ B B B ⊂ A C A and B are incomparable D A = B
Theory-of-Computation       Regular-Expressions       Gate-1998
Question 9 Explanation:
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
 Question 10
The string 1101 does not belong to the set represented by
 A 110*(0 + 1) B 1 ( 0 + 1)* 101 C (10)* (01)* (00 + 11)* D Both C and D
Theory-of-Computation       Regular-Expressions       Gate-1998
Question 10 Explanation:
Options A & B are generates string 1101.
C & D are not generate string 1101.
 Question 11
Which one of the following regular expressions over {0,1} denotes the set of all strings not containing 100 as a substring?
 A 0*(1+0)* B 0*1010* C 0*1*01 D 0(10+1)*
Theory-of-Computation       Regular-Expressions       Gate-1997
Question 11 Explanation:
(A) generates 100.
(B) generates 100 as substring.
(C) doesn't generate 1.
 Question 12

 A (i) and (ii) B (ii) and (iii) C (i) and (iii) D (iii) and (iv)
Theory-of-Computation       Regular-Expressions       Gate-1996
Question 12 Explanation:
(00)*(ε+0),0*
In these two, we have any no. of 0's as well as null.
 Question 13
In some programming languages, an identifier is permitted to be a letter following 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 L(L ∪ D)* C (L⋅D)* D L⋅(L⋅D)*
Theory-of-Computation       Regular-Expressions       Gate-1995
Question 13 Explanation:
Which is to be letter followed by any number of letters (or) digits
L(L ∪ D)*
 Question 14
Which of the following regular expression identifies are true?
 A r(*) = r* B (r*s*) = (r+s)* C (r+s)* = r* + s* D r*s* = r* + s*
Theory-of-Computation       Regular-Expressions       Gate-1992
Question 14 Explanation:
(B) RHS generates Σ* while LHS can't generate strings where r comes after s like sr, srr, etc.
LHS ⊂ RHS.
(C) LHS generates Σ* while RHS can't generate strings where r comes after an s.
RHS ⊂ LHS.
(D) LHS contains all strings where after an s, no r comes. RHS contains all strings of either r or s but no combination of them.
So, RHS ⊂ LHS.
 Question 15

 A L(s) ⊆ L(r) and L(s) ⊆ L(t) B L(r) ⊆ L(s) and L(s) ⊆ L(t) C L(s) ⊆ L(t) and L(s) ⊆ L(r) D L(t) ⊆ L(s) and L(s) ⊆ L(r) E None of the above F A and C
Theory-of-Computation       Regular-Expressions       Gate-1991
Question 15 Explanation:
L(s) ⊆ L(r), because 'r' generates all strings which 's' does but 'r' also generates '101' which 's' does not generate.
L(s) ⊆ L(t), because 't' generates all the strings which 's' generates but 't' also generates '0' which 's' do not generates.
There are 15 questions to complete.
PHP Code Snippets Powered By : XYZScripts.com