GATE CS 2024 Set 2

Match each phase with what it produces or does:

• P → 2. The lexical analyzer groups the input characters into lexemes and passes them on as tokens.
• Q → 3. The syntax analyzer checks the token stream against the grammar; the derivation it finds is a parse tree.
• R → 1. An abstract syntax tree, a compact tree of operators and operands without the parse tree's extra grammar nodes, is a common intermediate representation.
• S → 4. Constant folding, such as replacing 2 * 3 by 6 at compile time, is a code optimization.

This gives P – 2; Q – 3; R – 1; S – 4. Option C swaps the two trees, and A and D misplace tokens and constant folding.

Answer: B

Call the start state \(q_0\) and the accepting state \(q_1\). A 0 never changes the state and a 1 always switches it, so the DFA accepts exactly the strings with an odd number of 1s.

Option A follows the DFA directly. \(0^{*}1\) stays in \(q_0\) on 0s and moves to \(q_1\) on the first 1. From then on, every way of leaving \(q_1\) and coming back is either the self-loop 0 or a trip \(10^{*}1\) through \(q_0\), so \((0 + 10^{*}1)^{*}\) covers every continuation that ends in \(q_1\).

• B accepts the empty string, which has no 1s, and cannot produce 1.
• C cannot produce 111, which has three 1s.
• D forces a leading 0, so it misses 1, and it accepts 0.

Answer: A

IP addresses name the two ends of the journey, while a MAC address only names the next stop on the current link.

• The IP header carries the final destination, so the destination IP address is Y's all the way; routers forward on it but do not rewrite it. B is true and A is false.
• Y is on another network, so X sends the frame to its next-hop router R: the destination MAC address is R's, which X finds through ARP. R then puts the packet in a new frame for the next link.
• An Ethernet switch is transparent. It forwards frames by their destination MAC address but is never itself the addressee, so C is false. Y's MAC address would be used only if Y were on X's own LAN, so D is false.

Answer: B

The MMU is the hardware between the CPU and memory that handles every memory reference. Its jobs are the ones done on each access:

• B: it translates each virtual address to a physical address through the page table, with the TLB caching recent translations.
• C: if the page table entry is invalid or not present, it cannot translate the address and raises a trap (a page fault) for the OS to handle.
• D: it checks the protection bits on every access and traps when a process writes to a read-only page.

A is not an MMU task. Creating a process and allocating and filling its page table is done in software by the operating system kernel; the MMU only uses the table the OS has set up, for example through the page-table base register.

Answer: B, C, D

The test is whether P could carry on running after the event.

• A: a blocking read must wait for the disk, so P is moved to the blocked state and the OS switches to another process (or the idle task). Always.
• B: the missing page has to be read in from swap space, which is slow disk I/O, so P blocks until the page arrives. Always.
• C: the handler marks the other process ready, but P can simply resume afterwards; P is switched out only if the scheduler decides to preempt it. Not always.
• D: the timer handler may find that P's time slice has not run out, or that no other process is ready, and return to P. Not always.

Answer: A, B

A scan retrieves every record of the file, so the best possible cost is to read each data page exactly once.

• Heap and sorted files keep their records packed in data pages, so a scan reads all \(B\) pages in sequence, one I/O per page. Both are I/O efficient.
• With an unclustered index, tree or hash, the records are reached through the index entries. The order of the entries has nothing to do with where the records sit on disk, so consecutive entries usually point to different pages. The scan then costs about one page I/O per record, plus the reads of the index itself, which is far more than \(B\) when a page holds many records.

Answer: A, B

Under 2PL each transaction has a growing phase, in which it may only acquire locks, followed by a shrinking phase, in which it may only release them.

• A is true. Every schedule that 2PL allows is conflict serializable, equivalent to running the transactions one after another in the order of their lock points.
• B is false. Releasing a lock right after each operation and then locking the next item mixes the two phases, which is exactly what 2PL forbids.
• C is true. This is the shrinking phase: after the first release, no new lock may be taken.
• D is true. If T1 holds a lock on X and waits for Y while T2 holds Y and waits for X, both wait forever; basic 2PL does nothing to prevent this.

Answer: A, C, D

In IPv4, a datagram can meet a link with a smaller MTU anywhere on its path.

• B is true and A is false: any router whose outgoing link cannot carry the datagram splits it into fragments, each with its own IP header and with the offset and more-fragments fields set. (Fragmenting only at the source is how IPv6 works.)
• C is true and D is false: fragments of one datagram may take different routes, and a later link may have a larger MTU anyway, so routers forward fragments as independent datagrams. Only the destination host collects them, using the identification field and the offsets, and rebuilds the original datagram.

Answer: B, C

The question asks for the false statements.

• A is true. That is the usual definition: the semantic rules of an attribute grammar just compute attribute values, without printing, updating tables or other side effects.
• B is false. In an L-attributed definition an inherited attribute depends only on the parent and on siblings to its left, so a single left-to-right depth-first traversal always works, computing inherited attributes on the way down and synthesized ones on the way up.
• C is true. An LR parser computes a synthesized attribute when it reduces by a production, keeping the values on its stack.
• D is false. Inserting marker nonterminals to compute inherited attributes is guaranteed to work for LL grammars, but in an LR(1) grammar the markers can create parsing conflicts, so not every such definition can be evaluated bottom-up.

Answer: B, D

Check each statement for \(x = 0\) and \(x = 1\):

• A: \(x.1 = x\) is the identity law for AND, so it is true.
• B: \(x + 1 = 1\) for every \(x\), so \(x + 1 = x\) fails when \(x = 0\). False.
• C: \(x.x = x\) (idempotent law), so \(x.x = 0\) fails when \(x = 1\). False.
• D: \(x + \overline{x} = 1\) is the complement law, so it is true.

The false statements are B and C.

Answer: B, C