GATE 2017 Computer Science & IT Solution PDF
Document Details
Uploaded by TopQualityNash
2017
GATE
Tags
Related
- gate-computer-science-and-information-technology-2019-9789352868469-9789353061166-9352868463_compress-1-578.pdf
- gate-computer-science-and-information-technology-2019-9789352868469-9789353061166-9352868463_compress-1-578.pdf
- GATE Syllabus PDF
- GATE 2023 Computer Science and Information Technology (CS) PDF
- GATE-O-PEDIA Computer Science & Information Technology PDF
- GATE-2025 Online Test Series Schedule PDF
Summary
This document is a solution set for the GATE 2017 Computer Science & IT exam, covering both General Aptitude and Computer Science & IT sections. It provides detailed answers and explanations to various questions, which are useful for GATE aspirants.
Full Transcript
## MADE EASY - GATE 2017 Examination - Computer Science & IT - Session 2 ### MADE EASY India's Best Institute for IES, GATE & PSUs ### GATE 2017: Examination Computer Science & IT | Session-2 **Click here for Detailed Solutions** * MADE EASY has taken due care in making solutions. If you find an...
## MADE EASY - GATE 2017 Examination - Computer Science & IT - Session 2 ### MADE EASY India's Best Institute for IES, GATE & PSUs ### GATE 2017: Examination Computer Science & IT | Session-2 **Click here for Detailed Solutions** * MADE EASY has taken due care in making solutions. If you find any discrepancy/ typo/technical error, kindly share/post your views. * If you want to contest the answer key given by MADE EASY, kindly post your suggested answer with detailed explanations. * Students are requested to share their expected marks in GATE 2017. www.madeeasy.in Corporate Office: 44-A/1, Kalu Sarai, New Delhi - 110016 | Ph: 011-45124612, 9958995830 Delhi | Hyderabad | Noida | Bhopal | Jaipur | Lucknow | Indore | Pune | Bhubaneswar | Kolkata | Patna ### Section - I (General Aptitude) **Q.1** A test has twenty questions worth 100 marks in total. There are two types of questions. Multiple choice questions are worth 3 marks each and essay questions are worth 11 marks each. How many multiple choice questions does the exam have? - (a) 12 - (c) 18 - (b) 15 - (d) 19 **Ans.** (b) **Q.2** There are five buildings called V, W, X, Y and Z in a row (not necessarily in that order). V is to the West of W. Z is to the East of X and the West of V. W is to the West of Y. Which is the building in the middle? - (a) V - (c) X - (b) W - (d) Y **Ans.** (a) **Q.3** Saturn is _______ to be seen on a clear night with the naked eye. - (a) enough bright - (b) bright enough - (c) as enough bright - (d) bright as enough **Ans.** (b) **Q.4** Choose the option with words that are not synonyms. - (a) aversion, dislike - (b) luminous, radiant - (c) plunder, loot - (d) yielding, resistant **Ans.** (d) **Q.5** There are 3 red socks, 4 green socks and 3 blue socks. You choose 2 socks. The probability that they are of the same colour is - (a) 1/5 - (c) 1/4 - (b) 7/30 - (d) 4/15 **Ans.** (d) **Q.6** X is a 30 digit number starting with the digit 4 followed by the digit 7. Then the number X³ will have - (a) 90 digits - (c) 92 digits - (b) 91 digits - (d) 93 digits **Ans.** (a) **Q.7** There are three boxes. One contains apples, another contains oranges and the last one contains both apples and oranges. All three are known to be incorrectly labelled. If you are permitted to open just one box and then pull out and inspect only one fruit, which box would you open to determine the contents of all three boxes? - (a) The box labelled 'Apples' - (b) The box labelled 'Apples and Oranges' - (c) The box labelled 'Oranges’ - (d) Cannot be determined **Ans.** (b) **Q.8** "We lived in a culture that denied any merit to literary works, considering them important only when they were handmaidens to something seemingly more urgent- namely ideology. This was a country where all gestures, even the most private, were interpreted in political terms.” The author's belief that ideology is not as important as literature is revealed by the word: - (a) 'culture’ - (b) 'seemingly' - (c) 'urgent' - (d) 'political' **Ans.** (c) ** Q.9** The number of roots of *e^x+0.5x²-2 = 0* in the range [-5, 5] is - (a) 0 - (c) 2 - (b) 1 - (d) 3 **Ans.** (c) **Q.10** An air pressure contour line joins locations in a region having the same atmospheric pressure. The following is an air pressure contour plot is a geographical region. Contour lines are shown at 0.05 bar intervals in this plot. [ **Image of an air pressure contour plot** ] If the possibility of a thunderstorm is given by how fast air pressure rises or drops over a region, which of the following regions is most likely to have a thunderstorm? - (a) P - (c) R - (b) Q - (d) S **Ans.** (c) ### Section - II (Computer Science & IT) **Q.1** Identify the language generated by the following grammar, where S is the start variable. S → XY X→ aX|a Y→ aYb∈ - (a) {a^m b^n | m≥ n, n > 0} - (c) {a^m b^n|m>n, n ≥ 0} - (b) {a^m b^n|m ≥ n, n ≥ 0} - (d) {a^m b^n|m>n, n > 0} **Ans.** (c) **Q.2** Given the following binary number in 32-bit (single precision) IEEE-754 format: **00111110011011010000000000000000** The decimal value closest to this floating-point number is - (a) 1.45 × 10¹ - (c) 2.27×10⁻¹ - (b) 1.45 × 10⁻¹ - (d) 2.27 × 10¹ **Ans.** (c) **Q.3** The Breadth First Search (BFS) algorithm has been implemented using the queue data structure. Which one of the following is a possible order of visiting the nodes in the graph below? [ **Image of a graph with 6 labelled nodes** ] - (a) MNOPQR - (c) QMNROP - (b) NQMPOR - (d) POQNMR **Ans.** (d) **Q.4** Which of the following is/are shared by all the threads in a process? - I. Program counter - II. Stack - III. Address space - IV. Registers - (a) I and II only - (c) IV only - (b) III only - (d) III and IV only **Ans.** (b) **Q.5** The minimum possible number of states of a deterministic finite automaton that accepts the regular language L = {w₁aw2|w₁, w₂ ={a, b}*, |w₁| = 2, |w2| ≥ 3} is **Ans.** (8) **Q.6** G is an undirected graph with n vertices and 25 edges such that each vertex of G has degree at least 3. Then the maximum possible value of n is ** Ans.** (16) **Q.7** Match the following: **List-I** - (P) static char var; - (Q) m = malloc(10); m = NULL; - (R) char *ptr[10]; - (S) register int var1; **List-II** - (i) Sequence of memory locations to store addresses - (ii) A variable located in data section of memory - (iii) Request to allocate a CPU register to store data - (iv) A lost memory which cannot be freed - (a) P (ii), Q → (iv), R → (i), S → (iii) - (b) P→(ii), Q → (i), R → (iv), S → (iii) - (c) P→(ii), Q → (iv), R → (iii), S → (i) - (d) P (iii), Q → (iv), R → (i), S → (ii) **Ans.** (a) **Q.8** Consider socket API on a Linux machine that supports connected UDP sockets. A connected UDP socket is a UDP socket on which connect function has already been called. Which of the following statements is/are CORRECT? I. A connected UDP socket can be used to communicate with multiple peers simultaneously. II. A process can successfully call connect function again for an already connected UDP socket. - (a) I only - (c) Both I and II - (b) II only - (d) Neither I nor II **Ans.** (b) **Q.9** Match the algorithms with their time complexities: **List-I (Algorithm)** - (P) Towers of Hanoi with n disks - (Q) Binary search given n sorted numbers - (R) Heap sort given n numbers at the worst case - (S) Addition of two n×n matrices **List-II (Time complexity)** - (i) Θ(n²) - (ii) O(n log n) - (iii) Θ(2^n) - (iv) O(log n) - (a) P (iii), Q (iv), R - (i), S - (ii) - (b) P (iv), Q - (iii), R - (i), S - (ii) - (c) P(iii), Q (iv), R (ii), S - (i) - (d) P (iv), Q (iii), R (ii), S - (i) **Ans.** (c) **Q.10** A circular queue has been implemented using a singly linked list where each node consists of a value and a single pointer pointing to the next node. We maintain exactly two external pointers FRONT and REAR pointing to the front node and the rear node of the queue, respectively. Which of the following statements is/are CORRECT for such a circular queue, so that insertion and deletion operations can be performed in O(1) time? - I. Next pointer of front node points to the rear node. - II. Next pointer of rear node points to the front node. - (a) I only - (c) Both I and II - (b) II only - (d) Neither I nor II **Ans.** (b) **Q.11** In a file allocation system, which of the following allocation scheme(s) can be used if no external fragmentation is allowed? - I. Contiguous - II. Linked - III. Indexed - (a) I and III only - (c) III only - (b) II only - (D) II and III only **Ans.** (d) ** Q.12** An ER model of a database consists of entity types A and B. These are connected by a relationship R which does not have its own attribute. Under which one of the following conditions, can the relational table for R be merged with that of A? - (a) Relationship R is one-to-many and the participation of A in R is total. - (b) Relationship R is one-to-many and the participation of A in R is partial. - (c) Relationship R is many-to-one and the participation of A in R is total. - (d) Relationship R is many-to-one and the participation of A in R is partial. **Ans.** (c & d) **Q.13** The representation of the value of a 16-bit unsigned integer X in hexadecimal number system is BCA9. The representation of the value of X in octal number system is - (a) 571244 - (c) 571247 - (b) 736251 - (d) 136251 **Ans.** (d) **Q.14** Let L1, L2 be any two context-free languages and R be any regular language. Then which of the following is/are CORRECT? - I. L₁ L₂ is context-free. - II. L₁ is context-free. - III. L₁- R is context-free. - IV. L₁0 L₂ is context-free. - (a) I, II and IV only - (c) II and IV only - (b) I and III only - (d) I only **Ans.** (c) **Q.15** Consider a quadratic equation *x² – 13x + 36 = 0* with coefficients in a base 'b'. The solutions of this equation in the same base 'b' are x = 5 and x = 6. Then b = **Ans.** (8) **Q.16** Consider the following tables T₁ and T2. | T1 | | T2 | |---|---|---| | **P** | **Q ** | **R** | **S** | | 2 | 2 | 2 | 2 | | 3 | 8 | 8 | 3 | | 7 | 3 | 3 | 2 | | 5 | 8 | 9 | 7 | | 6 | 9 | 5 | 7 | | 8 | 5 | 7 | 2 | | 9 | 8 | 7 | 7 | In table T₁, P is the primary key and Q is the foreign key referencing R in table T₂ with on-delete cascade and on-update cascade. In table T2, R is the primary key and S is the foreign key referencing P in table T₁ with on-delete set NULL and on-update cascade. In order to delete record (3,8) from table T₁, the number of additional records that need to be deleted from table T₁ is **Ans.** (0) **Q.17** The maximum number of IPv4 router addresses that can be listed in the record route (RR) option field of an IPv4 header is **Ans.** (9) **Q.18** Consider the set X = {a, b, c, d, e} under the partial ordering R = {(a, a), (a, b), (a, c), (a, d), (a, e), (b, b), (b, c), (b, e), (c, c), (c, e), (d, d), (d, e), (e, e)}. The Hasse diagram of the partial order (X, R) is shown below: [ **Image of Hasse Diagram for Set X** ] The minimum number of ordered pairs that need to be added to R to make (X, R) a lattice is **Ans.** (0) **Q.19** Let *[1 1 -1 7] and [ -1 -2 -1] [2 -3 4] [6 12 6] [5 10 5] [3 -2 3]* be two matrices. Then the rank of P + Q is _______. **Ans.** (2) **Q.20** Match the following according to input (from the left column) to the compiler phase (in the right column) that processes it: **List-I** - (P) Syntax tree - (Q) Character stream - (R) Intermediate representation - (S) Token stream **List-II** - (i) Code generator - (ii) Syntax analyzer - (iii) Semantic analyzer - (iv) Lexical analyzer - (a) P (ii), Q → (iii), R → (iv), S → (i) - (b) P (ii), Q → (i), R → (iii), S → (iv) - (c) P (iii), Q→ (iv), R → (i), S → (ii) - (d) P (i), Q → (iv), R → (ii), S → (iii) **Ans.** (c) **Q.21** Let p, q, r denote the statements “It is raining”, “It is cold", and "It is pleasant", respectively. Then the statement "It is not raining and it is pleasant, and it is not pleasant only if it is raining and it is cold” is represented by - (a) (¬p^r)^(¬r → (p^q)) - (c) (p^r)v ((p^q) → ¬r) - (b) (p^r)^((p^q) → ¬r) - (d) (p^r)v (r → (p^q)) **Ans.** (a) **Q.22** Consider tiie following function implemented in C: ```C { void printxy (int x, int y) { int *ptr; x = 0; ptr = &x; y = *ptr; *ptr = 1; printf ("%d, %d", x, y); } } ``` The output of invoking printxy (1, 1) is - (a) 0,0 - (c) 1,0 - (b) 0, 1 - (d) 1, 1 **Ans.** (c) **Q.23** If *f(x) = R sin(πx/2) + S, f'(π/2) = √2 and ∫(f(x)dx from 0 to π = 2R/π* then the constants R and S are, respectively - (a) π/4 and π/16 - (b) π/4 and 0 - (c) π/4 and 0 - (d) π/ and π **Ans.** (c) **Q.24** Consider tlie following statements about the routing protocols, Routing Information Protocol (RIP) and Open Shortest Path First (OSPF) in an IPv4 network. - I: RIP uses distance vector routing - II: RIP packets are sent using UDP - III: OSPF packets are sent using TCP - IV: OSPF operation is based on link-state routing Which of the statements above are CORRECT? - (a) I and IV only - (c) I, II and IV only - (b) I, II and III only - (d) II, III and IV only **Ans.** (c) **Q.25** Which of the following statements about parser is/are CORRECT? - I. Canonical LR is more powerful than SLR. - II. SLR is more powerful than LALR. - III. SLR is more powerful than Canonical LR. - (a) I only - (c) III only - (b) II only - (d) II and III only **Ans.** (a) **Q.26** Consider a machine with a byte addressable main memory of 2^32 bytes divided into blocks of size 32 bytes. Assume that a direct mapped cache having 512 cache lines is used with this machine. The size of the tag field in bits is **Ans.** (18) **Q.27** P and Q are considering to apply for a job. The probability that P applies for the job is 1/4, the probability that P applies for the job given that Q applies for the job is 1/2, and the probability that Q applies for the job given that P applies for the job is 1/3. Then the probability that P does not apply for the job given that Q does not apply for the job is - (a) 4/5 - (c) 7/8 - (b) 6/11 - (d) 5/12 **Ans.** (a) **Q.28** Consider the following languages. - L₁ = {a^p | p is a prime number} - L₂ = {a^n b^m c^(2m) | n ≥ 0, m ≥ 0} - L₃ = {a^n b^n c^(2n) | n ≥ 0} - L₄ = {a^n b^n | n ≥ 1} Which of the following are CORRECT? - I. L₁ is context-free but not regular. - II. L2 is not context-free. - III. L3 is not context-free but recursive. - IV. L₄ is deterministic context-free. - (a) I, II and IV only - (c) I and IV only - (b) II and III only - (d) III and IV only **Ans.** (d) **Q.29** The read access times and the hit ratios for different caches in a memory hierarchy are as given below. | Code | Read access time (in nanoseconds) | Hit ratio | |---|---|---| | I-cache | 2 | 0.8 | | D-cache | 2 | 0.9 | | L2 -cache| 8 | 0.9 | | Main memory | 90 | 0.1 | The read access time of main memory is 90 nanoseconds. Assume that the caches use the referred word-first read policy and the write back policy. Assume that all the caches are direct mapped caches. Assume that the dirty bit is always 0 for all the blocks in the caches. In execution of a program, 60% of memory reads are for instruction fetch and 40% are for memory operand fetch. The average read access time in nanoseconds (upto 2 decimal places) is **Ans.** (2.74) **Q.30** Let δ denote the transition function and ô denote the extended transition function of the ε-NFA whose transition table is given below: | δ | ε | a | b | 0b | |---|---|---|---|---| | q0 | {q2} | {q1} | {q0} | {q0} | | q1 | {q2} | {q2} | {q3} | {q3} | | q2 | {q0} | Φ | Φ | {q2} | | q3 | Φ | Φ | {q2} | {q2} | The δ(q2, aba) is - (a) ф - (c) (q0, q1, q2) - (b) (q0, q1, q3) - (d) (q0, q2, q3) **Ans.** (c) **Q.31** Given *f(w, x, y, z) = ∑m{0, 1, 2, 3, 7, 8, 10) + Σd(5, 6, 11, 15)*, where d represents the don't-care condition in Karnaugh maps. Which of the following is a minimum product-of-sums (POS) form of f(w, x, y, z)? - (a) f = (w+z)(x + z) - (c) f = (w + z)(x + z) - (b) f = (w + z)(x + z) - (d) f = (w+z)(x + z) **Ans.** (a) **Q.32** A system shares 9 tape drives. The current allocation and maximum requirement of tape drives for three processes are shown below: | Process| Current Allocation | Maximum Requirement | |---|---|---| | P1 | 3 | 7 | | P2 | 1 | 6 | | P3 | 3 | 5 | Which of the following best describes current state of the system? - (a) Safe, Deadlocked - (c) Not Safe, Deadlocked - (b) Safe, Not Deadlocked - (d) Not Safe, Not Deadlocked **Ans.** (b) **Q.33** If w, x, y, z are Boolean variables, then which one of the following is INCORRECT? - (a) wx + w(x + y) + x(x + y) = x + wy - (b) wx(y + z) + wx = w + x + yz - (c) (wx(y+xz) + wx)y = xy - (d) (w + y) (wxy + wyz) = wxy + wyz **Ans.** (c) **Q.34** For any discrete random variable X, with probability mass function *P(X = j) = p_j, p_j≥0, j∈ {0...N}, and ∑ p_j = 1, j=0 to N*, define the polynomial function *g_x(z) = ∑ p_j z^j, j=0 to N*. For a certain discrete random variable Y, there exists a scalar β∈ [0, 1] such that *g_y(z) = (1 – β + βz)^N*. The expectation of Y is - (a) Νβ (1 – β) - (b) NB - (c) N (1 - β) - (d) Not expressible in terms of N and β alone **Ans.** (b) **Q.35** The next state table of a 2-bit saturating up-counter is given below. | Q₁ | Q₀ | Q₁⁺ | Q₀⁺ | |---|---|---|---| | 0 | 0 | 0 | 1 | | 0 | 1 | 1 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 1 | 1 | The counter is built as a synchronous sequential circuit using T flip-flops. The expressions for T₁ and T₀ are - (a) T₁ = Q₁Q₀ T₀ = Q₁Q₀ - (b) T₁ = Q₁Q₀ T₀ = Q₁ + Q₀ - (c) T₁ = Q₁₄ + Q₀ T₀ = Q₁ + Q₀ - (d) T₁ = Q₁Q₀ T₀ = Q₁ + Q₀ **Ans.** (b) **Q.36** Consider the following expression grammar G: E→E-TT T→T+FF F→ (E) id Which of the following grammars is not left recursive, but is equivalent to G? - (a) E→E-TT T→T+F|F F→ (E) | id - (c) ETX X→ -TX E T→ FY Y → +FY |∈ F→ (E) [id - (b) ETE' Ε' -ΤΕ' | E T→T+F F F→ (E) | id - (d) E → TX \(TX) X→-TX |+TX | ∈ T→ id **Ans.** (c) **Q.37** In a two-level cache system, the access times of L₁ and L2 caches are 1 and 8 clock cycles, respectively. The miss penalty from the L2 cache to main memory is 18 clock cycles. The miss rate of L₁ cache is twice that of L2. The average memory access time (AMAT) of this cache system is 2 cycles. The miss rates of L₁ and L₂ respectively are: - (a) 0.111 and 0.056 - (b) 0.056 and 0.111 - (c) 0.0892 and 0.1784 - (d) 0.1784 and 0.0892 **Ans.** (a) **Q.38** If the ordinary generating function of a sequence {a_n} is *(1+z) / (1 - z) ³* then a₃ - a₀ is **Ans.** (15) **Q.39** Consider the following C program. ```C #include <stdio.h> #include <string.h> int main() { char* c = "GATECSIT2017"; char* p = c; printf("%d", (int) strlen (c+2[p] – 6[p]−1)); return 0; } ``` The output of the program is **Ans.** (2) **Q.40** Consider the recurrence function T(n) = 2T(√n)+1, n>2 T(n) = 2, 0<n≤2 Then T(n) in terms of notation is - (a) O(log log n) - (b) O(log n) - (c) Θ(√n) - (d) O(n) **Ans.** (b) **Q.41** If the characteristic polynomial of a 3 × 3 matrix M over R (the set of real numbers) is λ³ – 4λ² + aλ + 30. α∈ R and one eigenvalue of M is 2, then the largest among the absolute values of the eigenvalues of M is **Ans.** (5) **Q.42** If a random variable X has a Poisson distribution with mean 5, then the expectation E[(X + 2)²] equals **Ans.** (54) **Q.43** Consider the C program fragment below which is meant to divide x by y using repeated subtractions. The variables x, y, q and r are all unsigned int. ```C while (r >= y) { r = r-y; q = q + 1; } ``` Which of the following conditions on the variables x, y, q and r before the execution of the fragment will ensure that the loop terminates in a state satisfying the condition x == (y x q + r)? - (a) (q == r) && (r == 0) - (b) (x > 0) && (r == x) && (y > 0) - (c) (q == 0) && (r == x) && (y > 0) - (d) (q == 0) && (y > 0) **Ans.** (c) **Q.44** In a B+ tree, if the search-key value is 8 bytes long, the block size is 512 bytes and the block pointer size is 2 bytes, then the maximum order of the B+ tree is **Ans.** (52) **Q.45** Consider the following database table named top_scorer. | top_scorer | |---|---|---| | player | country | gaols | | Klose | Germany | 16 | | Ronaldo | Brazil | 15 | | G Muller | Germany | 14 | | Fontaine | France | 13 | | Pele | Brazil | 12 | | Klinsmann | Germany | 11 | | Kocsis | Hungary | 11 | | Batistuta | Argentina | 10 | | Cubillas | Peru | 10 | | Lato | Poland | 10 | | Lineker | England | 10 | | T Muller | Germany | 10 | | Rahn | Germany | 10 | Consider the following SQL query: ```SQL SELECT ta.player FROM top_scorer as ta WHERE ta.goals > ALL (SELECT tb.goals FROM top_scorer as tb WHERE tb.country = 'Spain') AND ta.goals > ANY (SELECT tc.goals FROM top_scorer as tc WHERE tc.country = 'Germany') ``` The number of tuples returned by the above SQL query is **Ans.** (7) **Q.46** Consider two hosts X and Y. connected by a single direct link of rate 10⁶ bits/sec. The distance between the two hosts is 10,000 km and the propagation speed along the link is 2 × 10⁸ m/sec. Host X sends a file of 50,000 bytes as one large message to host Y continuously. Let the transmission and propagation delays be p milliseconds and q milliseconds, respectively. Then the values of p and q are - (a) p = 50 and q = 100 - (b) p = 50 and q = 400 - (c) p = 100 and q = 50 - (d) p = 400 and q = 50 **Ans.** (d) **Q.47** Consider the set of processes with arrival time (in milliseconds), CPU burst time (in milliseconds), and priority (0 is the highest priority) shown below. None of the processes have I/O burst time. | Process | Arrival Time | Burst Time | Priority | |---|---|---|---| | P1 | 0 | 11 | 2 | | P2 | 5 | 28 | 0 | | P3 | 12 | 2 | 3 | | P4 | 2 | 10 | 1 | | P5 | 9 | 16 | 4 | The average waiting time (in milliseconds) of all the processes using preemptive priority scheduling algorithm is **Ans.** (29) **Q.48** Consider the following C program ```C #include <stdio.h> int main() { int m = 10; int n, n1; n = ++m; n1 = m++; n--; n = n1; printf("%d", n); return 0; } ``` The output of the program is **Ans.** (0) **Q.49** A message is made up entirely of characters from the set X = {P, Q, R, S, T}. The table of probabilities for each of the characters is shown below: | Character | Probability | |---|---| | P | 0.22 | | Q | 0.34 | | R | 0.17 | | S | 0.19 | | T | 0.08 | | Total | 1.00 | If a message of 100 characters over X is encoded using Huffman coding, then the expected length of the encoded message in bits is **Ans.** (225) **Q.50** Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by a context free grammar G. Let L(M) be the language accepted by a Turing machine M. Which of the following decision problems are undecidable? - I. Given a regular expression R and a string w, is we L (R)? - II. Given a context-free grammar G, is L(G) = Ф? - III. Given a context-free grammar G, is L(G) = Σ* for some alphabet Σ? - IV. Given a Turing machine M and a string w, is we L(M)? - (a) I and IV only - (b) II and III only - (c) II, Ill and IV only - (d) III and IV only **Ans.** (d) **Q.51** Consider the following C function. ```C int fun {int n) { int i, j; for (i = 1; i <= n; i++) { for (j = 1; j <