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?
(0 + 1)* 0011(0 + 1)* + (0 + 1)* 1100(0 + 1)* | |
(0 + 1)* (00(0 + 1)* 11 + 11(0 + 1)* 00)(0 + 1)* | |
(0 + 1)* 00(0 + 1)* + (0 + 1)* 11(0 + 1)* | |
00(0 + 1)* 11 + 11(0 + 1)* 00 |
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.
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 |
4 | |
5 | |
6 | |
8 |
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.
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
I and II only | |
I and III only | |
II and III only | |
I, II, and III |
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.
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?
(0 * 10 * 1)*
| |
0 * (10 * 10*)*
| |
0*(10 * 1*)*0* | |
0 * 1(10 * 1)*10* |
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, ….}.
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)*?
The set of all strings containing the substring 00.
| |
The set of all strings containing at most two 0’s.
| |
The set of all strings containing at least two 0’s.
| |
The set of all strings that begin and end with either 0 or 1.
|
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?
(0 + 1) * 11(0 + 1) * | |
0 * 110 * | |
0 * 10 * 10 * | |
(0 + 1) * 1(0 + 1) * 1 (0 + 1) *
|
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.
→ 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
(1*0)*1*
| |
0+(0+10)*
| |
(0+1)*10(0+1)* | |
None of the above
|
Question 7 Explanation:
Both (A) and the given expression generates all strings over Σ.
Option (B) and (C) doesn't generate 11.
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?
S ⊂ T | |
T ⊂ S | |
S = T | |
S ∩ T = ɸ |
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 ⊂ B | |
B ⊂ A | |
A and B are incomparable | |
A = B |
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
110*(0 + 1) | |
1 ( 0 + 1)* 101 | |
(10)* (01)* (00 + 11)* | |
Both C and D |
Question 10 Explanation:
Options A & B are generates string 1101.
C & D are not generate 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?
0*(1+0)* | |
0*1010* | |
0*1*01 | |
0(10+1)* |
Question 11 Explanation:
(A) generates 100.
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 12 |
(i) and (ii) | |
(ii) and (iii) | |
(i) and (iii) | |
(iii) and (iv) |
Question 12 Explanation:
(00)*(ε+0),0*
In these two, we have any no. of 0's as well as null.
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?
(L ∪ D)+ | |
L(L ∪ D)* | |
(L⋅D)* | |
L⋅(L⋅D)* |
Question 13 Explanation:
Which is to be letter followed by any number of letters (or) digits
L(L ∪ D)*
L(L ∪ D)*
Question 14 |
Which of the following regular expression identifies are true?
r(*) = r* | |
(r*s*) = (r+s)* | |
(r+s)* = r* + s* | |
r*s* = r* + s* |
Question 14 Explanation:
(A) Answer.
(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.
(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 |
L(s) ⊆ L(r) and L(s) ⊆ L(t) | |
L(r) ⊆ L(s) and L(s) ⊆ L(t) | |
L(s) ⊆ L(t) and L(s) ⊆ L(r) | |
L(t) ⊆ L(s) and L(s) ⊆ L(r) | |
None of the above | |
A and C |
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.
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.