GATE IT 2005
Q31.
Let P be a non-deterministic push-down automaton (NPDA) with exactly one state, q, and exactly one symbol, Z, in its stack alphabet. State q is both the starting as well as the accepting state of the PDA. The stack is initialized with one Z before the start of the operation of the PDA. Let the input alphabet of the PDA be \Sigma. Let L(P) be the language accepted by the PDA by reading a string and reaching its accepting state. Let N(P) be the language accepted by the PDA by reading a string and emptying its stack. Which of the following statements is TRUE?Q32.
Let P(x) and Q(x) be arbitrary predicates. Which of the following statements is always TRUE?Q33.
Let T(n) be a function defined by the recurrence T(n) = 2T(n/2) + \sqrt n \text{ for }n \geq 2 and T(1) = 1 Which of the following statements is TRUE?Q34.
A language L satisfies the Pumping Lemma for regular languages, and also the Pumping Lemma for context-free languages. Which of the following statements about L is TRUE?Q35.
A disk has 8 equidistant tracks. The diameters of the innermost and outermost tracks are 1 cm and 8 cm respectively. The innermost track has a storage capacity of 10 MB. What is the total amount of data that can be stored on the disk if it is used with a drive that rotates it with I.Constant Linear Velocity II.Constant Angular Velocity?Q36.
A disk has 8 equidistant tracks. The diameters of the innermost and outermost tracks are 1 cm and 8 cm respectively. The innermost track has a storage capacity of 10 MB. If the disk has 20 sectors per track and is currently at the end of the 5^{th} sector of the inner-most track and the head can move at a speed of 10 meters/sec and it is rotating at constant angular velocity of 6000 RPM, how much time will it take to read 1 MB contiguous data starting from the sector 4 of the outer-most track?Q38.
Let A be a set with n elements. Let C be a collection of distinct subsets of A such that for any two subsets S_1 and S_2 in C, either S_1 \subset S_2 or S_2\subset S_1. What is the maximum cardinality of C?Q39.
Let n = p^{2}q, where p and q are distinct prime numbers. How many numbers m satisfy 1 \leq m \leq n and gcd(m,n)=1? Note that gcd(m,n) is the greatest common divisor of m and n.Q40.
Let G be a directed graph whose vertex set is the set of numbers from 1 to 100. There is an edge from a vertex i to a vertex j iff either j = i + 1 or j = 3i. The minimum number of edges in a path in G from vertex 1 to vertex 100 is