GATE CSE 1995
Q2.
Which of the following definitions below generate the same language as L, where L=\{x^ny^n \text{ such that } n\geq 1 \}? I. E \rightarrow xEy\mid xy II. x y \mid (x^+xyy^+) III. x^+y^+Q3.
Consider a grammar with the following productions S \rightarrow a \alpha b \mid b \alpha c \mid aB S \rightarrow \alpha S\mid b S \rightarrow \alpha b b\mid ab S \alpha \rightarrow bd b\mid b The above grammar is:Q4.
In the following Pascal program segment, what is the value of X after the execution of the program segment? X := -10; Y := 20; If X > Y then if X < 0 then X := abs(X) else X := 2*X;Q5.
Assume that X and Y are non-zero positive integers. What does the following Pascal program segment do? while X <> Y do if X > Y then X := X - Y else Y := Y - X; write(X);Q6.
Let A be the set of all non-singular matrices over real number and let * be the matrix multiplication operation. ThenQ8.
For merging two sorted lists of sizes m and n into a sorted list of size m+n, we require comparisons ofQ9.
Which of the following statements is true? I. As the number of entries in a hash table increases, the number of collisions increases. II. Recursive programs are efficient III. The worst case complexity for Quicksort is O(n^2) IV. Binary search using a linear linked list is efficient