2019S1

Problem 1

In this problem, integers ranging from $0$ to $2^n-1$ are represented by $n$ bits. Answer the following questions.

1. Design a Half adder and a Full adder. You can use only AND, OR, and NOT gates.

2. Design a circuit as follows. Its inputs are three 16-bit integers $\mathbf{a}$, $\mathbf{b}$, and $\mathbf{c}$. The outputs are two 17-bit integers $\mathbf{d}$ and $\mathbf{e}$ such that $\mathbf{a}+\mathbf{b}+\mathbf{c}=\mathbf{d}+\mathbf{e}$. Here, you can use only Half adders and Full adders (the number of the adders is not restricted), and no adders can be connected in series.

3. Design a circuit as follows. Its inputs are four 16-bit integers ${\mathbf{a}}_1$, ${\mathbf{a}}_2$, ${\mathbf{a}}_3$, and ${\mathbf{a}}_4$. The outputs are two 17-bit integers ${\mathbf{b}}_1$ and ${\mathbf{b}}_2$ such that ${\mathbf{a}}_1+{\mathbf{a}}_2+{\mathbf{a}}_3+{\mathbf{a}}_4={\mathbf{b}}_1+{\mathbf{b}}_2$. Here, you can use only Half adders and Full adders (the number of the adders is not restricted), and the maximum number of adders connected in series must be minimized.

4. Design a circuit as follows. Its inputs are two 8-bit integers $\mathbf{a}$ and $\mathbf{b}$. The outputs are two integers $\mathbf{c}$ and $\mathbf{d}$ such that $\mathbf{a}\times \mathbf{b}=\mathbf{c}+\mathbf{d}$. Here, you can use only Half adders and Full adders (the number of the adders is not restricted) in addition to $8\times 8$ one-bit multipliers.

---

在这个问题中，从 $0$ 到 $2^n-1$ 的整数由 $n$ 位表示。回答以下问题。

1. 设计一个半加器和一个全加器。你只能使用 AND、OR 和 NOT 门。

2. 按如下设计一个电路。其输入为三个 16 位整数 $\mathbf{a}$、$\mathbf{b}$ 和 $\mathbf{c}$。输出为两个 17 位整数 $\mathbf{d}$ 和 $\mathbf{e}$，使得 $\mathbf{a}+\mathbf{b}+\mathbf{c}=\mathbf{d}+\mathbf{e}$。在这里，你只能使用半加器和全加器（加法器的数量不限），并且不能将加法器串联。

3. 按如下设计一个电路。其输入为四个 16 位整数 ${\mathbf{a}}_1$、${\mathbf{a}}_2$、${\mathbf{a}}_3$ 和 ${\mathbf{a}}_4$。输出为两个 17 位整数 ${\mathbf{b}}_1$ 和 ${\mathbf{b}}_2$，使得 ${\mathbf{a}}_1+{\mathbf{a}}_2+{\mathbf{a}}_3+{\mathbf{a}}_4={\mathbf{b}}_1+{\mathbf{b}}_2$。在这里，你只能使用半加器和全加器（加法器的数量不限），并且必须最小化串联的加法器的最大数量。

4. 按如下设计一个电路。其输入为两个 8 位整数 $\mathbf{a}$ 和 $\mathbf{b}$。输出为两个整数 $\mathbf{c}$ 和 $\mathbf{d}$，使得 $\mathbf{a}\times \mathbf{b}=\mathbf{c}+\mathbf{d}$。在这里，你只能使用半加器和全加器（加法器的数量不限），此外还有 $8\times 8$ 的一位乘法器。

---

Problem 2

We consider a 32-bit machine with 32KB physical memory, upon which the operating system supports the paging functionality. The page size is 4KB, the virtual memory size is 4GB, and there is no cache memory. Answer the following questions. Note that 1KB is equivalent to 1024 bytes.

1. (1) Explain each of the following terms regarding the paging functionality, briefly.

• Page
• Page Table
• Page Replacement
• Page Fault
• Translation Look-aside Buffer (TLB)

(2) Obtain the physical address in hexadecimal corresponding to the virtual address of $2A0F$ (hexadecimal) when the following page table is given.

Page number (decimal)	Frame number (binary)	Valid bit
0	111	1
1	000	0
2	110	1
3	000	0
4	101	1
5	000	0
6	000	0
7	000	0
8	000	0
9	001	1
10	100	1
11	000	1
12	011	1
13	000	0
14	000	0
15	010	1

(3) Obtain the number of page faults caused by executing each of the following two pieces of program code written in C language.

Program Code 1

for (j = 0; j < 1024; j++)
  for (i = 0; i < 1024; i++)
    sum += A[i * 1024 + j];

Program Code 2

for (i = 0; i < 1024; i++)
  for (j = 0; j < 1024; j++)
    sum += A[i * 1024 + j];

Note that each program code is executed under the following assumptions:

• $i$, $j$, and $sum$ are 32-bit integer variables. $A$ is a 32-bit integer 1-dimensional array with $1024\times 1024$ elements. The values of $sum$ and each element of $A$ are all set.
• Program code optimization by a compiler is disabled.
• In the initial state, all the pages that are allocated for $A$ are not valid. Any data (including the program code and the page table) other than $A$ are allocated to some valid page, and it is never paged out.
• Page allocation for the start address of $A$ is aligned with a page boundary.
• Page replacement is based on the Least Recently Used (LRU) policy.

---

我们考虑一台拥有 32KB 物理内存的 32 位机器，操作系统支持分页功能。页面大小为 4KB，虚拟内存大小为 4GB，没有缓存内存。请回答以下问题。注意 1KB 相当于 1024 字节。

1. (1) 简要解释以下与分页功能相关的术语。

• 页面
• 页表
• 页面置换
• 页面错误
• 翻译后备缓冲区（TLB）

(2) 在以下页表给出的情况下，获取对应于虚拟地址 $2A0F$（十六进制）的物理地址（十六进制）。

页号 (十进制)	帧号 (二进制)	有效位
0	111	1
1	000	0
2	110	1
3	000	0
4	101	1
5	000	0
6	000	0
7	000	0
8	000	0
9	001	1
10	100	1
11	000	1
12	011	1
13	000	0
14	000	0
15	010	1

(3) 获取在以下两段用 C 语言编写的程序代码中执行每段代码时引发的页面错误数量。

程序代码 1

for (j = 0; j < 1024; j++)
  for (i = 0; i < 1024; i++)
    sum += A[i * 1024 + j];

程序代码 2

for (i = 0; i < 1024; i++)
  for (j = 0; j < 1024; j++)
    sum += A[i * 1024 + j];

请注意，每段程序代码都在以下假设条件下执行：

• $i$, $j$ 和 $sum$ 是 32 位整数变量。$A$ 是一个具有 $1024\times 1024$ 元素的 32 位整数一维数组。$sum$ 和 $A$ 的每个元素的值都已设定。
• 禁用编译器的程序代码优化。
• 在初始状态下，分配给 $A$ 的所有页面都是无效的。除了 $A$ 之外的任何数据（包括程序代码和页表）都分配给某个有效页面，并且永远不会被调出。
• 为 $A$ 的起始地址分配页面时，与页面边界对齐。
• 页面置换基于最近最少使用（LRU）策略。

---

Problem 3

In the following, we represent a deterministic finite automaton as a quintuple $\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$ (where $Q$ is a finite set of states, $\Sigma$ is a finite set of input symbols, $\delta :Q\times \Sigma \to Q$ is the transition function, $q_0\in Q$ is the initial state, and $F\subseteq Q$ is the set of final states), and a context-free grammar as a quadruple $G=(V,\Sigma ,P,S)$ (where $V$ is a finite set of non-terminal symbols, $\Sigma$ is a finite set of terminal symbols, $P$ is a finite set of production rules, and $S\in V$ is the start symbol). A context-free grammar $G=(V,\Sigma ,P,S)$ is in Chomsky normal form if each production rule is of the form $B\to CD$, $B\to a$, or $S\to ϵ$ (where $B$ is a non-terminal symbol, $C$ and $D$ are non-terminal symbols other than $S$, $a$ is a terminal symbol, and $ϵ$ is an empty sequence). We write $L(\mathcal{A})$ for the language accepted by a deterministic finite automaton $\mathcal{A}$, and $L(G)$ for the language generated by a context-free grammar $G$. Answer the following questions.

1. Let $\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$ be a deterministic finite automaton. Give a deterministic finite automaton that accepts the complement of $L(\mathcal{A})$, i.e., ${\Sigma }^{\ast }\setminus L(\mathcal{A})$. Here, you may assume that $\delta$ is a total function.

2. Describe an algorithm that takes a context-free grammar $G$ as an input, and decides whether or not $L(G)=\varnothing$.

3. Given a context-free grammar $G=(V,\Sigma ,P,S)$ in Chomsky normal form and a deterministic finite automaton $\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$, we define a context-free grammar $G_{\mathcal{A}}$ by:

   $$V_{\mathcal{A}}=\{S^{\prime }\}\cup \{B_{q,q^{\prime }}\mid B\in V\wedge (q,q^{\prime })\in Q\}$$ $$P_{\mathcal{A}}=\{B_{q,q^{\prime }}\to C_{q,q^{\prime \prime }}{D}_{q^{\prime \prime },q^{\prime }}\mid (B\to CD\in P)\wedge (q,q^{\prime },q^{\prime \prime })\in Q\}$$ $$\cup \{B_{q,q^{\prime }}\to a\mid (B\to a\in P)\wedge (q,q^{\prime })\in Q\wedge (\delta (q,a)=q^{\prime })\}$$ $$\cup \{S^{\prime }\to S_{q_0,q}\mid (q\in F)\}.$$

   Here, assume $S^{\prime }\notin \{B_{q,q^{\prime }}\mid B\in V\wedge (q,q^{\prime })\in Q\}$. Prove that $L(G_{\mathcal{A}})=(L(G)\cap L(\mathcal{A}))\setminus \{ϵ\}$ holds.

4. Give a method to decide, given a context-free grammar $G$ in Chomsky normal form and a deterministic finite automaton $\mathcal{A}$ as inputs, whether or not $L(G)\subseteq L(\mathcal{A})$. You may use the results of questions (1), (2), and (3).

---

在以下内容中，我们将确定有限自动机表示为五元组 $\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$（其中 $Q$ 是一个有限状态集，$\Sigma$ 是一个有限输入符号集，$\delta :Q\times \Sigma \to Q$ 是转移函数，$q_0\in Q$ 是初始状态，$F\subseteq Q$ 是终止状态集），上下文无关文法表示为四元组 $G=(V,\Sigma ,P,S)$（其中 $V$ 是一个非终结符号的有限集合，$\Sigma$ 是一个终结符号的有限集合，$P$ 是一组产生规则，$S\in V$ 是开始符号）。上下文无关文法 $G=(V,\Sigma ,P,S)$ 处于 Chomsky 范式，如果每个产生规则的形式为 $B\to CD$，$B\to a$ 或 $S\to ϵ$（其中 $B$ 是一个非终结符号，$C$ 和 $D$ 是非终结符号，$a$ 是一个终结符号，$ϵ$ 是一个空序列）。我们用 $L(\mathcal{A})$ 表示确定有限自动机 $\mathcal{A}$ 接受的语言，用 $L(G)$ 表示上下文无关文法 $G$ 生成的语言。请回答以下问题。

1. 设 $\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$ 是一个确定有限自动机。给出一个确定有限自动机，它接受 $L(\mathcal{A})$ 的补集，即 ${\Sigma }^{\ast }\setminus L(\mathcal{A})$。这里，你可以假设 $\delta$ 是一个全函数。

2. 描述一个算法，该算法接受上下文无关文法 $G$ 作为输入，并决定 $L(G)=\varnothing$ 与否。

3. 给定一个 Chomsky 范式的上下文无关文法 $G=(V,\Sigma ,P,S)$ 和一个确定有限自动机 $\mathcal{A}=(Q,\Sigma ,\delta ,q_0,F)$，我们定义上下文无关文法 $G_{\mathcal{A}}$ 如下：

   $$V_{\mathcal{A}}=\{S^{\prime }\}\cup \{B_{q,q^{\prime }}\mid B\in V\wedge (q,q^{\prime })\in Q\}$$ $$P_{\mathcal{A}}=\{B_{q,q^{\prime }}\to C_{q,q^{\prime \prime }}{D}_{q^{\prime \prime },q^{\prime }}\mid (B\to CD\in P)\wedge (q,q^{\prime },q^{\prime \prime })\in Q\}$$ $$\cup \{B_{q,q^{\prime }}\to a\mid (B\to a\in P)\wedge (q,q^{\prime })\in Q\wedge (\delta (q,a)=q^{\prime })\}$$ $$\cup \{S^{\prime }\to S_{q_0,q}\mid (q\in F)\}.$$

   这里，假设 $S^{\prime }\notin \{B_{q,q^{\prime }}\mid B\in V\wedge (q,q^{\prime })\in Q\}$。证明 $L(G_{\mathcal{A}})=(L(G)\cap L(\mathcal{A}))\setminus \{ϵ\}$ 成立。

4. 提供一种方法，判断给定 Chomsky 范式中的上下文无关文法 $G$ 和一个确定有限自动机 $\mathcal{A}$ 作为输入，$L(G)\subseteq L(\mathcal{A})$ 是否成立。你可以使用问题 (1)，(2) 和 (3) 的结果。