Gate (CS) 1999 Paper without Solution | GATE Computer Science Engineering(CSE) 2025 Mock Test Series - Computer Science Engineering (CSE) PDF Download

 Page 1


GATE CS - 1999
  
SECTION - A 
1. This question consists of TWENTY-FIVE multiple questions of ONE mark each.  For
each question, four possible alternatives (A, B, C and D) are given, out of which
ONLY ONE is correct. Indicate the correct answer in the boxes corresponding to
the questions only on the FIRST sheet of the answer book.
1.1 Suppose that the expectation of a random variable X is 5. Which of the following 
statements is true? 
(a) There is a sample point at which X has the value 5. 
(b) There is a sample point at which X has value greater than 5. 
(c) There is a sample point at which X has a value greater than or equal to 5. 
(d) None of the above 
1.2 The number of binary relations on a set with n elements is:
(a) 
2
n (b) 2
n
 
(c) 
2
2
n
(d) None of the above 
1.3 The number of binary strings of n zeroes and k ones that no two ones are 
adjacent is 
(a) 
1 n
k
C
-
(b) 
n
k
C
(c) 
1
n
k
C
+
(d) None of the above 
1.4 Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state 
finite automation that recognizes the language represented by this regular 
expression contains 
(a) n states (b) n + 1 states 
(c) n + 2 states (d) None of the above 
1.5 Context-free languages are closed under: 
(a) Union, intersection (b) Union, Kleene closure 
(c) Intersection, complement (d) Complement, Kleene closure 
1.6 Let L
D
 be the set of all languages accepted by a PDA by final state and L
E
 the set 
of all languages accepted by empty stack. Which of the following is true? 
(a) L
D
 = L
E
 (b) L
D 
?
 
L
E
(c) L
E
 = L
D
 (d) None of the above 
1.7 Which of the following expressions is not equivalent to x ? 
(a) x NAND X (b) x NOR x (c) x NAND 1 (d) x NOR 1 
Page 2


GATE CS - 1999
  
SECTION - A 
1. This question consists of TWENTY-FIVE multiple questions of ONE mark each.  For
each question, four possible alternatives (A, B, C and D) are given, out of which
ONLY ONE is correct. Indicate the correct answer in the boxes corresponding to
the questions only on the FIRST sheet of the answer book.
1.1 Suppose that the expectation of a random variable X is 5. Which of the following 
statements is true? 
(a) There is a sample point at which X has the value 5. 
(b) There is a sample point at which X has value greater than 5. 
(c) There is a sample point at which X has a value greater than or equal to 5. 
(d) None of the above 
1.2 The number of binary relations on a set with n elements is:
(a) 
2
n (b) 2
n
 
(c) 
2
2
n
(d) None of the above 
1.3 The number of binary strings of n zeroes and k ones that no two ones are 
adjacent is 
(a) 
1 n
k
C
-
(b) 
n
k
C
(c) 
1
n
k
C
+
(d) None of the above 
1.4 Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state 
finite automation that recognizes the language represented by this regular 
expression contains 
(a) n states (b) n + 1 states 
(c) n + 2 states (d) None of the above 
1.5 Context-free languages are closed under: 
(a) Union, intersection (b) Union, Kleene closure 
(c) Intersection, complement (d) Complement, Kleene closure 
1.6 Let L
D
 be the set of all languages accepted by a PDA by final state and L
E
 the set 
of all languages accepted by empty stack. Which of the following is true? 
(a) L
D
 = L
E
 (b) L
D 
?
 
L
E
(c) L
E
 = L
D
 (d) None of the above 
1.7 Which of the following expressions is not equivalent to x ? 
(a) x NAND X (b) x NOR x (c) x NAND 1 (d) x NOR 1 
GATE CS - 1999
  
1.8 Which of the following functions implements the Karnaugh map shown below? 
 CD 
AB 
00 00 11 10 
00 0 0 1 0 
01 X X 1 X 
11 0 1 1 0 
10 0 1 1 0 
(a) AB CD + (b) D(C +A) 
(c) AD + AB (d)( )( ) ( ) C D C D A B + + + +
1.9 Listed below are some operating system abstractions (in the left column) and the 
hardware components (in the right column)? 
(a) (A) – 2  (B) – 4  (C) – 3  (D) - 1 (b) (A) – 1  (B) – 2  (C) – 3  (D) – 4 
(c) (A) – 3  (B) – 2  (C) – 4  (D) - 1 (d) (A) – 4  (B) – 1  (C) – 2  (D) – 3 
1.10 Which of the following disk scheduling strategies is likely to give the best through 
put? 
(a) Farthest cylinder next  (b) Nearest cylinder next 
(c) First come first served (d) Elevator algorithm 
1.11 System calls are usually invoked by using 
(a) a software interrupt (b) polling 
(c) an indirect jump  (d) a privileged instruction 
1.12  A sorting technique is called stable if 
(a) it takes O (nlog n) time 
(b) it maintains the relative order of occurrence of non-distinct elements 
(c) it uses divide and conquer paradigm 
(d) it takes O(n) space 
(A) Thread 1. Interrupt
(B) Virtual address space 2. Memory
(C) File system 3. CPU
(D) Signal 4. Disk
Page 3


GATE CS - 1999
  
SECTION - A 
1. This question consists of TWENTY-FIVE multiple questions of ONE mark each.  For
each question, four possible alternatives (A, B, C and D) are given, out of which
ONLY ONE is correct. Indicate the correct answer in the boxes corresponding to
the questions only on the FIRST sheet of the answer book.
1.1 Suppose that the expectation of a random variable X is 5. Which of the following 
statements is true? 
(a) There is a sample point at which X has the value 5. 
(b) There is a sample point at which X has value greater than 5. 
(c) There is a sample point at which X has a value greater than or equal to 5. 
(d) None of the above 
1.2 The number of binary relations on a set with n elements is:
(a) 
2
n (b) 2
n
 
(c) 
2
2
n
(d) None of the above 
1.3 The number of binary strings of n zeroes and k ones that no two ones are 
adjacent is 
(a) 
1 n
k
C
-
(b) 
n
k
C
(c) 
1
n
k
C
+
(d) None of the above 
1.4 Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state 
finite automation that recognizes the language represented by this regular 
expression contains 
(a) n states (b) n + 1 states 
(c) n + 2 states (d) None of the above 
1.5 Context-free languages are closed under: 
(a) Union, intersection (b) Union, Kleene closure 
(c) Intersection, complement (d) Complement, Kleene closure 
1.6 Let L
D
 be the set of all languages accepted by a PDA by final state and L
E
 the set 
of all languages accepted by empty stack. Which of the following is true? 
(a) L
D
 = L
E
 (b) L
D 
?
 
L
E
(c) L
E
 = L
D
 (d) None of the above 
1.7 Which of the following expressions is not equivalent to x ? 
(a) x NAND X (b) x NOR x (c) x NAND 1 (d) x NOR 1 
GATE CS - 1999
  
1.8 Which of the following functions implements the Karnaugh map shown below? 
 CD 
AB 
00 00 11 10 
00 0 0 1 0 
01 X X 1 X 
11 0 1 1 0 
10 0 1 1 0 
(a) AB CD + (b) D(C +A) 
(c) AD + AB (d)( )( ) ( ) C D C D A B + + + +
1.9 Listed below are some operating system abstractions (in the left column) and the 
hardware components (in the right column)? 
(a) (A) – 2  (B) – 4  (C) – 3  (D) - 1 (b) (A) – 1  (B) – 2  (C) – 3  (D) – 4 
(c) (A) – 3  (B) – 2  (C) – 4  (D) - 1 (d) (A) – 4  (B) – 1  (C) – 2  (D) – 3 
1.10 Which of the following disk scheduling strategies is likely to give the best through 
put? 
(a) Farthest cylinder next  (b) Nearest cylinder next 
(c) First come first served (d) Elevator algorithm 
1.11 System calls are usually invoked by using 
(a) a software interrupt (b) polling 
(c) an indirect jump  (d) a privileged instruction 
1.12  A sorting technique is called stable if 
(a) it takes O (nlog n) time 
(b) it maintains the relative order of occurrence of non-distinct elements 
(c) it uses divide and conquer paradigm 
(d) it takes O(n) space 
(A) Thread 1. Interrupt
(B) Virtual address space 2. Memory
(C) File system 3. CPU
(D) Signal 4. Disk
GATE CS - 1999
  
1.13 Suppose we want to arrange the n numbers stored in any array such that all 
negative values occur before all positive ones. Minimum number of exchanges 
required in the worst case is 
(a) n  -  1 (b) n 
(c) n + 1 (d) None of the above 
1.14 If one uses straight two-way merge sort algorithm to sort the following elements 
in ascending order: 
20, 47, 15, 8, 9, 4, 40, 30, 12, 17 
then the order of these elements after second pass of the algorithm is:  
(a) 8, 9, 15, 20, 47, 4, 12, 17, 30, 40 
(b) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17 
(c) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17 
(d) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40 
1.15 The number of articulation points of the following graph is 
(a) 0 (b) 1 (c) 2 (d) 3 
1.16 If n is a power of 2, then the minimum number of multiplications needed to 
compute a* is 
(a) log
2
n (b) n (c) n -1 (d) n 
1.17 Which of the following is the most powerful parsing method? 
(a) LL (1) (b) Canonical LR (c) SLR (d) LALR 
1.18 Consider the join of a relation R with a relation S. If R has m tuples and S has n 
tuples then the maximum and minimum sizes of the join respectively are 
(a) m + n and 0   (b) mn and 0 
(c) m + n and |m – n|  (d) mn and m + n 
1 
2 3 
4 
5 
6 
7 
Page 4


GATE CS - 1999
  
SECTION - A 
1. This question consists of TWENTY-FIVE multiple questions of ONE mark each.  For
each question, four possible alternatives (A, B, C and D) are given, out of which
ONLY ONE is correct. Indicate the correct answer in the boxes corresponding to
the questions only on the FIRST sheet of the answer book.
1.1 Suppose that the expectation of a random variable X is 5. Which of the following 
statements is true? 
(a) There is a sample point at which X has the value 5. 
(b) There is a sample point at which X has value greater than 5. 
(c) There is a sample point at which X has a value greater than or equal to 5. 
(d) None of the above 
1.2 The number of binary relations on a set with n elements is:
(a) 
2
n (b) 2
n
 
(c) 
2
2
n
(d) None of the above 
1.3 The number of binary strings of n zeroes and k ones that no two ones are 
adjacent is 
(a) 
1 n
k
C
-
(b) 
n
k
C
(c) 
1
n
k
C
+
(d) None of the above 
1.4 Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state 
finite automation that recognizes the language represented by this regular 
expression contains 
(a) n states (b) n + 1 states 
(c) n + 2 states (d) None of the above 
1.5 Context-free languages are closed under: 
(a) Union, intersection (b) Union, Kleene closure 
(c) Intersection, complement (d) Complement, Kleene closure 
1.6 Let L
D
 be the set of all languages accepted by a PDA by final state and L
E
 the set 
of all languages accepted by empty stack. Which of the following is true? 
(a) L
D
 = L
E
 (b) L
D 
?
 
L
E
(c) L
E
 = L
D
 (d) None of the above 
1.7 Which of the following expressions is not equivalent to x ? 
(a) x NAND X (b) x NOR x (c) x NAND 1 (d) x NOR 1 
GATE CS - 1999
  
1.8 Which of the following functions implements the Karnaugh map shown below? 
 CD 
AB 
00 00 11 10 
00 0 0 1 0 
01 X X 1 X 
11 0 1 1 0 
10 0 1 1 0 
(a) AB CD + (b) D(C +A) 
(c) AD + AB (d)( )( ) ( ) C D C D A B + + + +
1.9 Listed below are some operating system abstractions (in the left column) and the 
hardware components (in the right column)? 
(a) (A) – 2  (B) – 4  (C) – 3  (D) - 1 (b) (A) – 1  (B) – 2  (C) – 3  (D) – 4 
(c) (A) – 3  (B) – 2  (C) – 4  (D) - 1 (d) (A) – 4  (B) – 1  (C) – 2  (D) – 3 
1.10 Which of the following disk scheduling strategies is likely to give the best through 
put? 
(a) Farthest cylinder next  (b) Nearest cylinder next 
(c) First come first served (d) Elevator algorithm 
1.11 System calls are usually invoked by using 
(a) a software interrupt (b) polling 
(c) an indirect jump  (d) a privileged instruction 
1.12  A sorting technique is called stable if 
(a) it takes O (nlog n) time 
(b) it maintains the relative order of occurrence of non-distinct elements 
(c) it uses divide and conquer paradigm 
(d) it takes O(n) space 
(A) Thread 1. Interrupt
(B) Virtual address space 2. Memory
(C) File system 3. CPU
(D) Signal 4. Disk
GATE CS - 1999
  
1.13 Suppose we want to arrange the n numbers stored in any array such that all 
negative values occur before all positive ones. Minimum number of exchanges 
required in the worst case is 
(a) n  -  1 (b) n 
(c) n + 1 (d) None of the above 
1.14 If one uses straight two-way merge sort algorithm to sort the following elements 
in ascending order: 
20, 47, 15, 8, 9, 4, 40, 30, 12, 17 
then the order of these elements after second pass of the algorithm is:  
(a) 8, 9, 15, 20, 47, 4, 12, 17, 30, 40 
(b) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17 
(c) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17 
(d) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40 
1.15 The number of articulation points of the following graph is 
(a) 0 (b) 1 (c) 2 (d) 3 
1.16 If n is a power of 2, then the minimum number of multiplications needed to 
compute a* is 
(a) log
2
n (b) n (c) n -1 (d) n 
1.17 Which of the following is the most powerful parsing method? 
(a) LL (1) (b) Canonical LR (c) SLR (d) LALR 
1.18 Consider the join of a relation R with a relation S. If R has m tuples and S has n 
tuples then the maximum and minimum sizes of the join respectively are 
(a) m + n and 0   (b) mn and 0 
(c) m + n and |m – n|  (d) mn and m + n 
1 
2 3 
4 
5 
6 
7 
GATE CS - 1999
  
1.19. The relational algebra expression equivalent to the following tuple calculus 
expression: 
( )
{ }
10 20 t t r t A t B ? ? = ? = ? ? ? ?
? ? ? ?
is
(a) 
( )
( )
10 20 A B
r s
= ? =
(b) 
( )
( )
( )
( )
10 20 A B
r r s s
= =
?
(c) 
( )
( )
( )
( )
10 20 A B
r r s s
= =
n (d) 
( )
( )
( )
( )
10 20 A B
r r s s
= =
-
1.20. Booth’s coding in 8 bits for the decimal number –57 is 
(a) 0 – 100 + 1000  (b) 0 – 100 + 100 -1 
(c) 0 – 1 + 100 – 10 + 1 (d) 0 0 – 10 + 100 - 1 
1.21. The maximum gate delay for any output to appear in an array multiplier for 
multiplying two n bit number is 
(a) O
( )
2
n (b) O(n) (c) O(log n) (d) O(1) 
1.22. The main memory of a computer has 2 cm blocks while the cache has 2 c blocks. 
If the cache uses the set associative mapping scheme with 2 blocks per set, then 
block k of the main memory maps to the set  
(a) (k mod m) of the cache (b) (k mod c) of the cache 
(c) (k mod 2c) of the cache (d) (k mod 2 cm) of the cache 
1.23. The Newton-Raphson method is to be used to find the root of the equation f(x)=0 
where 
o
x is the initial approximation and f' is the derivative of f. The method 
converges 
(a) always (b) only if f is a polynomial 
(c) only if ( ) 0
o
f x < (d) None of the above 
1.24. Let R = (a, b, c, d, e, f) be a relation scheme with the following dependencies 
c 
 f, e 
 a, ec 
 d. a 
 b. Which of the following is a key for R? 
(a) CD (b) EC (c) AE (d) AC 
1.25 Which of the following is correct? 
(a) B-trees are for storing data on disk and B
+
 trees are for main memory. 
(b) Range queries are faster on B* trees. 
(c) B-trees are for primary indexes and B* trees are for secondary indexes. 
(d) The height of a B* tree is independent of the number of records. 
Page 5


GATE CS - 1999
  
SECTION - A 
1. This question consists of TWENTY-FIVE multiple questions of ONE mark each.  For
each question, four possible alternatives (A, B, C and D) are given, out of which
ONLY ONE is correct. Indicate the correct answer in the boxes corresponding to
the questions only on the FIRST sheet of the answer book.
1.1 Suppose that the expectation of a random variable X is 5. Which of the following 
statements is true? 
(a) There is a sample point at which X has the value 5. 
(b) There is a sample point at which X has value greater than 5. 
(c) There is a sample point at which X has a value greater than or equal to 5. 
(d) None of the above 
1.2 The number of binary relations on a set with n elements is:
(a) 
2
n (b) 2
n
 
(c) 
2
2
n
(d) None of the above 
1.3 The number of binary strings of n zeroes and k ones that no two ones are 
adjacent is 
(a) 
1 n
k
C
-
(b) 
n
k
C
(c) 
1
n
k
C
+
(d) None of the above 
1.4 Consider the regular expression (0 + 1) (0 + 1)…. N times. The minimum state 
finite automation that recognizes the language represented by this regular 
expression contains 
(a) n states (b) n + 1 states 
(c) n + 2 states (d) None of the above 
1.5 Context-free languages are closed under: 
(a) Union, intersection (b) Union, Kleene closure 
(c) Intersection, complement (d) Complement, Kleene closure 
1.6 Let L
D
 be the set of all languages accepted by a PDA by final state and L
E
 the set 
of all languages accepted by empty stack. Which of the following is true? 
(a) L
D
 = L
E
 (b) L
D 
?
 
L
E
(c) L
E
 = L
D
 (d) None of the above 
1.7 Which of the following expressions is not equivalent to x ? 
(a) x NAND X (b) x NOR x (c) x NAND 1 (d) x NOR 1 
GATE CS - 1999
  
1.8 Which of the following functions implements the Karnaugh map shown below? 
 CD 
AB 
00 00 11 10 
00 0 0 1 0 
01 X X 1 X 
11 0 1 1 0 
10 0 1 1 0 
(a) AB CD + (b) D(C +A) 
(c) AD + AB (d)( )( ) ( ) C D C D A B + + + +
1.9 Listed below are some operating system abstractions (in the left column) and the 
hardware components (in the right column)? 
(a) (A) – 2  (B) – 4  (C) – 3  (D) - 1 (b) (A) – 1  (B) – 2  (C) – 3  (D) – 4 
(c) (A) – 3  (B) – 2  (C) – 4  (D) - 1 (d) (A) – 4  (B) – 1  (C) – 2  (D) – 3 
1.10 Which of the following disk scheduling strategies is likely to give the best through 
put? 
(a) Farthest cylinder next  (b) Nearest cylinder next 
(c) First come first served (d) Elevator algorithm 
1.11 System calls are usually invoked by using 
(a) a software interrupt (b) polling 
(c) an indirect jump  (d) a privileged instruction 
1.12  A sorting technique is called stable if 
(a) it takes O (nlog n) time 
(b) it maintains the relative order of occurrence of non-distinct elements 
(c) it uses divide and conquer paradigm 
(d) it takes O(n) space 
(A) Thread 1. Interrupt
(B) Virtual address space 2. Memory
(C) File system 3. CPU
(D) Signal 4. Disk
GATE CS - 1999
  
1.13 Suppose we want to arrange the n numbers stored in any array such that all 
negative values occur before all positive ones. Minimum number of exchanges 
required in the worst case is 
(a) n  -  1 (b) n 
(c) n + 1 (d) None of the above 
1.14 If one uses straight two-way merge sort algorithm to sort the following elements 
in ascending order: 
20, 47, 15, 8, 9, 4, 40, 30, 12, 17 
then the order of these elements after second pass of the algorithm is:  
(a) 8, 9, 15, 20, 47, 4, 12, 17, 30, 40 
(b) 8, 15, 20, 47, 4, 9, 30, 40, 12, 17 
(c) 15, 20, 47, 4, 8, 9, 12, 30, 40, 17 
(d) 4, 8, 9, 15, 20, 47, 12, 17, 30, 40 
1.15 The number of articulation points of the following graph is 
(a) 0 (b) 1 (c) 2 (d) 3 
1.16 If n is a power of 2, then the minimum number of multiplications needed to 
compute a* is 
(a) log
2
n (b) n (c) n -1 (d) n 
1.17 Which of the following is the most powerful parsing method? 
(a) LL (1) (b) Canonical LR (c) SLR (d) LALR 
1.18 Consider the join of a relation R with a relation S. If R has m tuples and S has n 
tuples then the maximum and minimum sizes of the join respectively are 
(a) m + n and 0   (b) mn and 0 
(c) m + n and |m – n|  (d) mn and m + n 
1 
2 3 
4 
5 
6 
7 
GATE CS - 1999
  
1.19. The relational algebra expression equivalent to the following tuple calculus 
expression: 
( )
{ }
10 20 t t r t A t B ? ? = ? = ? ? ? ?
? ? ? ?
is
(a) 
( )
( )
10 20 A B
r s
= ? =
(b) 
( )
( )
( )
( )
10 20 A B
r r s s
= =
?
(c) 
( )
( )
( )
( )
10 20 A B
r r s s
= =
n (d) 
( )
( )
( )
( )
10 20 A B
r r s s
= =
-
1.20. Booth’s coding in 8 bits for the decimal number –57 is 
(a) 0 – 100 + 1000  (b) 0 – 100 + 100 -1 
(c) 0 – 1 + 100 – 10 + 1 (d) 0 0 – 10 + 100 - 1 
1.21. The maximum gate delay for any output to appear in an array multiplier for 
multiplying two n bit number is 
(a) O
( )
2
n (b) O(n) (c) O(log n) (d) O(1) 
1.22. The main memory of a computer has 2 cm blocks while the cache has 2 c blocks. 
If the cache uses the set associative mapping scheme with 2 blocks per set, then 
block k of the main memory maps to the set  
(a) (k mod m) of the cache (b) (k mod c) of the cache 
(c) (k mod 2c) of the cache (d) (k mod 2 cm) of the cache 
1.23. The Newton-Raphson method is to be used to find the root of the equation f(x)=0 
where 
o
x is the initial approximation and f' is the derivative of f. The method 
converges 
(a) always (b) only if f is a polynomial 
(c) only if ( ) 0
o
f x < (d) None of the above 
1.24. Let R = (a, b, c, d, e, f) be a relation scheme with the following dependencies 
c 
 f, e 
 a, ec 
 d. a 
 b. Which of the following is a key for R? 
(a) CD (b) EC (c) AE (d) AC 
1.25 Which of the following is correct? 
(a) B-trees are for storing data on disk and B
+
 trees are for main memory. 
(b) Range queries are faster on B* trees. 
(c) B-trees are for primary indexes and B* trees are for secondary indexes. 
(d) The height of a B* tree is independent of the number of records. 
GATE CS - 1999
  
2. This question consists of TWENTY-FIVE sub-questions, of TWO marks each.  For
each of these sub-questions, four possible alternatives (A, B, C and D) are given,
out of which ONLY ONE is correct. Indicate the correct answers in the boxes
corresponding to the questions only on the SECOND sheet of the answer book.
2.1 Consider two events E
1
 and E
2
 such that probability of E
1
, Pr [E
1
]= 
1
,
2
probability 
of E
2
, Pr
21
1
,
3
E = ? ?
? ?
and probability of E
1
 and E
2
, Pr[E
1
 and E
2
]=
1
.
5
 Which of the 
following statements is/are true? 
(a) 
1 2
2
Pr or is 
3
E E ? ?
? ?
(b) Events E
1
 and E
2
 are independent  
(c) Events E
1
 and E
2
 are not independent 
(d) 
1
2
4
Pr
5
E
E
? ?
=
? ?
? ?
2.2. Two girls have picked 10 roses, 15 sunflowers and 15 daffodils. What is the 
number of ways they can divide the flowers amongst themselves? 
(a) 1638   (b) 2100 
(c) 2640   (d) None of the above 
2.3. Let L be a set with a relation R which is transitive, anti-symmetric and reflexive 
and for any two elements a, b ? L let the least upper bound lub (a,b) and the 
greatest lower bound glb (a,b) exist. Which of the following is/are true? 
(a) L is a poset (b) L is a Boolean algebra 
(c) -L1 is context free (d) -L2 is regular 
2.4. If L is context free language and L2 is a regular language which of the following 
is/are false? 
(a) L1 – L2 is not context free (b) L1 n L2 is context free 
(c) ~L1 is context free  (d) ~L2 is regular 
2.5. Given the programming constructs (i) assignment (ii) for loops where the loop 
parameter cannot be changed within the loop (iii) if-then-else (iv) forward go to 
(v) arbitrary go to (vi) non-recursive procedure call (vii) recursive 
procedure/function call (viii) repeat loop, which constructs will you not include in 
a programming language such that it should be possible to program the 
terminates (i.e., halting) function in the same programming language.   
(a) (ii), (iii), (iv) 
(b) (v), (vii), (viii) 
(c) (vi), (vii), (viii) 
(d) (iii), (vii), (viii)