Regular-Expression

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
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

Let L be the language represented by the regular expression Σ*0011Σ* where Σ = {0,1}. What is the minimum number of states in a DFA that recognizes (complement of L)?

A
4
B
5
C
6
D
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.
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
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*
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.
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

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
Question 6 Explanation: 
Both (A) and the given expression generates all strings over Σ.
Option (B) and (C) doesn't generate 11.
Question 7

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 = ɸ
Question 7 Explanation: 
If we draw DFA for language S and T it will represent same.
Question 8

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
Question 8 Explanation: 
Both A and B are equal, which generates strings over {0,1}, while 0 is followed by 1.
Question 9

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
Question 9 Explanation: 
Options A & B are generates string 1101.
C & D are not generate string 1101.
Question 10

(a) An identifier in a programming language consists of upto six letters and digits of which the first character must be a letter. Derive a regular expression for the identifier.

(b) Build an LL(1) parsing table for the language defined by the LL(1) grammar with productions

Program → begin d semi X end
X → d semi X | sY
Y → semi s Y | ε 
A
Theory Explanation.
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)*
Question 11 Explanation: 
(A) generates 100.
(B) generates 100 as substring.
(C) doesn't generate 1.
(D) answer.
Question 12

Which two of the following four regular expressions are equivalent? (ε is the empty string).

    (i) (00)*(ε+0)
    (ii) (00)*
    (iii) 0*
    (iv) 0(00)*
A
(i) and (ii)
B
(ii) and (iii)
C
(i) and (iii)
D
(iii) and (iv)
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)*
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?

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.
Question 15

Choose the correct alternatives (more than one may be correct) and write the corresponding letters only: Let r = 1(1+0)*, s = 11*0 and t = 1*0 be three regular expressions. Which one of the following is true?

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
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.
Question 16

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

A
10*(0*10*10*)*
B
((0 + 1)*1(0 + 1)*1)*10*
C
(0*10*10*)*10*
D
(0*10*10*)*0*1
Question 16 Explanation: 
The regular expression 10*(0*10*10*)* always generate string begin with 1 and thus does not generate string “01110” hence wrong option.
The regular expression ((0+1)*1(0+1)*1)*10* generate string “11110” which is not having odd number of 1’s , hence wrong option.
The regular expression (0*10*10*)10* is not a generating string “01”. Hence this is also wrong . It seems none of them is correct.
NOTE: Option 3 is most appropriate option as it generates the max number of strings with odd 1’s.
But option 3 is not generating odd strings. So, still it is not completely correct.
The regular expression (0*10*10*)*0*1 always generates all string ends with “1” and thus does not generate string “01110” hence wrong option.
Question 17

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) *
Question 17 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 18

Consider the regular expression

 R = (a + b)* (aa + bb) (a + b)* 
Which of the following non-deterministic finite automata recognizes the language defined by the regular expression R? Edges labeled λ denote transitions on the empty string.

A
B
C
D
Question 18 Explanation: 
Every string of given regular expression must contain the substring aa or bb.
But option (B), (C), (D) accepts aba, which do not contain aa or bb as substring.
Hence, (A) is correct.
Question 19

Consider the regular expression

 R = (a + b)* (aa + bb) (a + b)* 
Which deterministic finite automaton accepts the language represented by the regular expression R ?

A
B
C
D
Question 19 Explanation: 
(B) It accepts 'ab' which is not in the language.
(C) It is not accepting 'abb' which is in language.
(D) It is not accepting 'aa' and 'bb' which is in language.
There are 19 questions to complete.

Access quiz wise question and answers by becoming as a solutions adda PRO SUBSCRIBER with Ad-Free content

Register Now

If you have registered and made your payment please contact solutionsadda.in@gmail.com to get access