GATE CS 2024 Set 2

Find each field width:

• Registers: 50 registers need \(\lceil \log_2 50 \rceil = 6\) bits per register field.
• OPCODE: each type has \(150 / 2 = 75\) operations, which need 7 bits (\(2^{7} = 128\)); with the type bit, \(Y = 8\).
• R-type: \(8 + X + 3 \times 6 = 32\), so \(X = 6\).
• I-type: \(8 + 2 \times 6 + Z = 32\), so \(Z = 12\).

Hence \(X + 2Y + Z = 6 + 16 + 12 = 34\). The result does not depend on how the opcode is sized: \(X = 14 - Y\) and \(Z = 20 - Y\), so the sum is 34 either way.

Answer: 34

The part \(b^{*}ab^{*}\) contributes exactly one \(a\), each repetition of \((ab^{*}ab^{*})\) adds two more, and \(b\)’s may appear anywhere. So \(L_1\) is the set of strings with an odd number of \(a\)’s.

Count such strings of length at most 4:

• length 0: none;
• length 1: just \(a\), 1 string;
• length 2: one \(a\), \(\binom{2}{1} = 2\) strings;
• length 3: one or three \(a\)’s, \(3 + 1 = 4\) strings;
• length 4: one or three \(a\)’s, \(4 + 4 = 8\) strings.

Total: \(1 + 2 + 4 + 8 = 15\). For each length \(n \ge 1\), exactly half of the \(2^{n}\) strings qualify.

Answer: 15

The product group works coordinate by coordinate, so \((x, y, z)\) is its own inverse exactly when \(2x \equiv 0 \pmod 2\), \(2y \equiv 0 \pmod 3\) and \(2z \equiv 0 \pmod 4\).

• In \(Z_2\): both 0 and 1 work (2 choices).
• In \(Z_3\): only 0 works, since \(2 \cdot 1 = 2\) and \(2 \cdot 2 = 4 \equiv 1\) (1 choice).
• In \(Z_4\): 0 and 2 work (2 choices).

So there are \(2 \times 1 \times 2 = 4\) such elements: \((0,0,0), (0,0,2), (1,0,0), (1,0,2)\). The identity \((0,0,0)\) counts, since it is its own inverse.

Answer: 4

A 4 KB page holds \(2^{12} / 4 = 1024\) entries. So one inner page-table page maps 1024 pages, and the outer directory (one page, 1024 entries) can point to at most 1024 inner pages. The directory page always exists.

• Minimum: the 2000 pages fall into as few 1024-page regions as possible, \(\lceil 2000 / 1024 \rceil = 2\) inner pages, so \(X = 1 + 2 = 3\).
• Maximum: the pages are spread out so that each inner page has few valid entries. With 2000 pages and only 1024 possible inner pages, all 1024 can be in use, so \(Y = 1 + 1024 = 1025\).

Hence \(X + Y = 3 + 1025 = 1028\).

Answer: 1028

\(I_0\) holds \(S' \rightarrow \bullet S\), the five items \(S \rightarrow \bullet SS\), \(S \rightarrow \bullet Aa\), \(S \rightarrow \bullet bAc\), \(S \rightarrow \bullet Bc\), \(S \rightarrow \bullet bBa\), and, from the dots before \(A\) and \(B\), \(A \rightarrow \bullet d\#\) and \(B \rightarrow \bullet @\).

\(\mathit{GOTO}(I_0, S)\) moves the dot over \(S\) in the two items that have \(S\) next, giving the kernel \(S' \rightarrow S \bullet\) and \(S \rightarrow S \bullet S\). Closing the second item adds the five \(S\)-items with the dot at the start, and these in turn bring in \(A \rightarrow \bullet d\#\) and \(B \rightarrow \bullet @\).

Total: \(2 + 5 + 2 = 9\) items. Stopping at the kernel would give only 2.

Answer: 9