Exams › GATE › Technical

Consider the following context-free grammar where the start symbol is S and the set of terminals is {a,b,c,d}. S → AaAb | BbBa A → cS | ε B → dS | ε The following is a partially-filled LL(1) parsing table. Columns: a, b, c, d, Rows: S: (a) S → AaAb, (b) S → BbBa, (c) (1), (d) (2), () blank A: (a) A → ε, (b) (3), (c) A → cS, (d) blank, () blank B: (a) (4), (b) B → ε, (c) blank, (d) B → dS, () blank Which one of the following options represents the CORRECT combination for the numbered cells in the parsing table? Note: In the options, “blank” denotes that the corresponding cell is empty.

1. (1) S → AaAb (2) S → BbBa (3) A → ε (4) B → ε
2. (1) S → BbBa (2) S → AaAb (3) A → ε (4) B → ε
3. (1) S → AaAb (2) S → BbBa (3) blank (4) blank
4. (1) S → BbBa (2) S → AaAb (3) blank (4) blank

Correct answer: (1) S → AaAb (2) S → BbBa (3) A → ε (4) B → ε

Solution

The correct option is right because it accurately fills the LL(1) parsing table based on the productions of the grammar. For the non-terminal S, the first production is chosen for 'a' and the second for 'b', while A can derive ε for 'a' and B can also derive ε for 'b', aligning with the grammar's rules.

Related GATE Technical questions

• Consider a computer with a 4 MHz processor. Its DMA controller can transfer 8 bytes in 1 cycle from a device to main memory through cycle stealing at regular intervals. What is the data transfer rate (in bits per second) of the DMA controller if 1% of the processor cycles are used for DMA?
• Let p and q be the following propositions: p: Fail grade can be given. q: Student scores more than 50% marks. Consider the statement: “Fail grade cannot be given when student scores more than 50% marks.” Which one of the following is the CORRECT representation of the above statement in propositional logic?
• Consider a single processor system with four processes A, B, C, and D, represented as given below, where for each process the first value is its arrival time, and the second value is its CPU burst time. A (0, 10), B (2, 6), C (4, 3), and D (6, 7). Which one of the following options gives the average waiting times when preemptive Shortest Remaining Time First (SRTF) and Non-preemptive Shortest Job First (N-P-SJF) CPU scheduling algorithms are applied to the processes?
• Which one of the following CIDR prefixes exactly represents the range of IP addresses 10.1.2.2 to 10.1.2.255?
• You are given a set V of distinct integers. A binary search tree T is created by inserting all elements of V one by one, starting with an empty tree. The tree T follows the convention that, at each node, all values stored in the left subtree of the node are smaller than the value stored at the node. You are not aware of the sequence in which these values were inserted into T, and you do not have access to T. Which one of the following statements is TRUE?
• Consider an array X that contains n positive integers. A subarray of X is defined to be a sequence of array locations with consecutive indices. The C code snippet given below has been written to compute the length of the longest subarray of X that contains at most two distinct integers. The code has two missing expressions labelled (P) and (Q). int first=0, second=0, len1=0, len2=0, maxlen=0; for (int i=0; i < n; i++) { if (X[i] == first) { len2++; } else if (X[i] == second) { len2++; len1 = (P); second = first; } else { len2 = (Q); len1 = 1; second = first; } if (len2 > maxlen) { maxlen = len2; } first = X[i]; } Which one of the following options gives the CORRECT missing expressions? (Hint: At the end of the i-th iteration, the value of len1 is the length of the longest subarray ending with X[i] that contains all equal values, and len2 is the length of the longest subarray ending with X[i] that contains at most two distinct values.)

⚔️ Practice GATE Technical free + battle 1v1 →