2017S1

Problem 1

A language $L\subseteq {\Sigma }^{\ast }$ over a finite alphabet $\Sigma$ is said to be regular if there exists a finite automaton $\mathcal{A}$ such that $L=\mathcal{L}(\mathcal{A})$. Here

$$\mathcal{L}(\mathcal{A})=\{w\in {\Sigma }^{\ast }\mid w\text{ is accepted by }\mathcal{A}\}$$

Answer the following questions.

1. We fix an alphabet $\Sigma$ by $\Sigma =\{a,b\}$. For the language $L_1$ below, present a nondeterministic finite automaton (NFA) ${\mathcal{A}}_1$ such that: $\mathcal{L}({\mathcal{A}}_1)=L_1$, and the number of states of ${\mathcal{A}}_1$ is not greater than 4.

$$L_1=\{w\in {\Sigma }^{\ast }\mid \text{there is a character }l\in \Sigma \text{ that occurs more than once in }w\}$$

2. Assume that $\Sigma$ is a finite alphabet. Prove the following: any finite language $L=\{w_1,\dots ,w_n\}\subseteq {\Sigma }^{\ast }$ is regular. Here $n$ is a nonnegative integer.

3. We fix an alphabet $\Sigma$ by $\Sigma =\{a,b\}$. For the language $L_1$ in Question (1), present a deterministic finite automaton (DFA) ${\mathcal{A}}_2$ such that: $\mathcal{L}({\mathcal{A}}_2)={\Sigma }^{\ast }\setminus L_1$, and the number of states of ${\mathcal{A}}_2$ is not greater than 5. Here ${\Sigma }^{\ast }\setminus L_1$ denotes the complement of $L_1$ in ${\Sigma }^{\ast }$.

4. Give a decision procedure for the following problem, and explain it briefly.

Input: nondeterministic finite automaton $\mathcal{A}$.

Output: whether the language $\mathcal{L}(\mathcal{A})$ is an infinite set or not.

---

一个语言 $L\subseteq {\Sigma }^{\ast }$ 在有限字母表 $\Sigma$ 上，如果存在一个有限自动机 $\mathcal{A}$ 使得 $L=\mathcal{L}(\mathcal{A})$，则称该语言是正则的。这里

$$\mathcal{L}(\mathcal{A})=\{w\in {\Sigma }^{\ast }\mid w\text{ 被 }\mathcal{A}\text{ 接受}\}$$

回答以下问题。

1. 我们固定字母表 $\Sigma$ 为 $\Sigma =\{a,b\}$。对于以下语言 $L_1$，给出一个不超过 4 个状态的非确定性有限自动机 (NFA) ${\mathcal{A}}_1$，使得：$\mathcal{L}({\mathcal{A}}_1)=L_1$。

$$L_1=\{w\in {\Sigma }^{\ast }\mid \Sigma 中存在字符l\text{ 在 }w\text{ 中出现多于一次}\}$$

2. 假设 $\Sigma$ 是一个有限字母表。证明如下：任何有限语言 $L=\{w_1,\dots ,w_n\}\subseteq {\Sigma }^{\ast }$ 是正则的。这里 $n$ 是一个非负整数。

3. 我们固定字母表 $\Sigma$ 为 $\Sigma =\{a,b\}$。对于问题 (1) 中的语言 $L_1$，给出一个不超过 5 个状态的确定性有限自动机 (DFA) ${\mathcal{A}}_2$，使得：$\mathcal{L}({\mathcal{A}}_2)={\Sigma }^{\ast }\setminus L_1$。这里 ${\Sigma }^{\ast }\setminus L_1$ 表示 ${\Sigma }^{\ast }$ 中 $L_1$ 的补集。

4. 给出以下问题的决策过程，并简要解释。

输入: 非确定性有限自动机 $\mathcal{A}$。

输出: 语言 $\mathcal{L}(\mathcal{A})$ 是否是一个无限集。

---

Problem 2

Suppose that we are given an undirected graph $G$ where each edge is associated with a cost. A minimum spanning tree is a subgraph of the graph such that: it connects all the vertices; it is a tree; and it takes a minimum total cost. The following pseudo code (Algorithm $A$) shows an algorithm to compute a minimum spanning tree. We let the numbers of vertices and edges of $G$ be denoted by $V$ and $E$, respectively.

Step 1. Choose an arbitrary vertex and let $G^{\prime }$ be the subtree of $G$ consisting of only that vertex.

Step 2. Choose an edge with a minimum cost, out of $(a)$ and add the edge and its end vertices to $G^{\prime }$.

Step 3. Repeat Step 2 until $G^{\prime }$ contains all the vertices of $G$.

Answer the following question.

1. Answer an appropriate phrase that fills $(a)$ above.

There are multiple ways to implement Algorithm $A$. Specifically, computation time differs depending on how to find an edge with a minimum cost in Step 2.

Answer the following questions.

2. Suppose that $G$ is dense ($V^2\approx E$) and given as an adjacency matrix. Explain a time-efficient implementation of Algorithm $A$ in this case. Answer also the time complexity of the implementation, and explain why.

3. Suppose that $G$ is sparse ($V\approx E$) and given as adjacency lists. Explain a time-efficient implementation of Algorithm $A$ in this case. Answer also the time complexity of the implementation, and explain why.

4. Show that the graph $G^{\prime }$ obtained using Algorithm $A$ is a minimum spanning tree of the graph $G$.

---

假设我们有一个无向图 $G$，其中每条边都有一个成本。最小生成树是图的一个子图，它连接所有顶点；它是一棵树；并且它的总成本最低。以下伪代码（算法 $A$）展示了一种计算最小生成树的算法。我们用 $V$ 和 $E$ 分别表示 $G$ 的顶点数和边数。

步骤 1. 选择一个任意顶点，并让 $G^{\prime }$ 为仅由该顶点组成的 $G$ 的子树。

步骤 2. 从 $(a)$ 中选择一条成本最小的边，并将该边及其终端顶点添加到 $G^{\prime }$ 中。

步骤 3. 重复步骤 2，直到 $G^{\prime }$ 包含 $G$ 的所有顶点。

回答以下问题。

1. 回答填充上文 $(a)$ 处的适当短语。

有多种方法可以实现算法 $A$。具体来说，在步骤 2 中找到成本最低的边的计算时间不同。

回答以下问题。

2. 假设 $G$ 是稠密的（$V^2\approx E$）并作为邻接矩阵给出。解释一种在这种情况下算法 $A$ 的高效实现。还要回答实现的时间复杂度，并解释原因。

3. 假设 $G$ 是稀疏的（$V\approx E$）并作为邻接表给出。解释一种在这种情况下算法 $A$ 的高效实现。还要回答实现的时间复杂度，并解释原因。

4. 证明使用算法 $A$ 获得的图 $G^{\prime }$ 是图 $G$ 的最小生成树。

---

Problem 3

Answer the following questions regarding sequential logic circuits. Assume that the clock is an ideal rectangular wave without skew, and that the gate delay is short enough compared with the clock cycle.

1. Choose one from D flip-flop, JK flip-flop and T flip-flop, and explain how its output is determined by the clock, the inputs and the internal state.

2. Design and depict a circuit ALT, whose output toggles between 0 and 1 every clock cycle as illustrated below. You can use the flip-flop you have chosen in Question (1), and the AND, OR and NOT gates.

Clock:         ____|¯¯¯¯|____|¯¯¯¯|____|¯¯¯
Output of ALT: ____|¯¯¯¯¯¯¯¯¯|_________|¯¯¯¯¯¯

3. Design and depict a circuit that sorts 8 integers, each of which being a 4-bit unsigned integer, by the bubble sort algorithm. The inputs and the outputs of the sorting circuit are as follows:

   • Inputs $I_0,I_1,\dots ,I_7$. Each of them is a 4-bit unsigned integer.
   • 1-bit input $L$.
   • Outputs $O_0,O_1,\dots ,O_7$. Each of them is a 4-bit unsigned integer.
   • 1-bit output $V$.

The sorting circuit should work as follows.

(a) When $L$ is 1, the inputs $I_0,I_1,\dots ,I_7$ are stored using 32 flip-flops. Those stored data are regarded as eight 4-bit unsigned integers, and called $v_0,v_1,\dots ,v_7$ in the following.

(b) After $L$ becomes 0, in the first clock cycle, the circuit compares $v_0$ and $v_1$, and if $v_0>v_1$, then it swaps them, and otherwise it keeps them. The same operations are applied to the three pairs $(v_2,v_3)$, $(v_4,v_5)$ and $(v_6,v_7)$. The new values of $v_0,v_1,\dots ,v_7$ are output to $O_0,O_1,\dots ,O_7$.

(c) In the second clock cycle after $L$ becomes 0, the circuit compares $v_1$ and $v_2$, and if $v_1>v_2$, then it swaps them, and otherwise it keeps them. The same operations are applied to the two pairs $(v_3,v_4)$ and $(v_5,v_6)$. The new values of $v_0,v_1,\dots ,v_7$ are output to $O_0,O_1,\dots ,O_7$.

(d) The circuit repeats steps (b) and (c) while $L$ is 0. If no swap of values happens for two consecutive clock cycles that execute (b) or (c), $V$ is set to 1, and otherwise $V$ is set to 0.

You can use the following circuits in your design: the flip-flop you have chosen in Question (1), the ALT circuit you have designed in Question (2), 4-bit comparator CMP, 4-bit 2-to-1 multiplexer MUX, and the AND, OR and NOT gates.

---

回答以下有关时序逻辑电路的问题。假设时钟是一个没有偏斜的理想矩形波，并且门延迟相对于时钟周期来说足够短。

1. 从 D 触发器、JK 触发器和 T 触发器中选择一个，并解释其输出是如何由时钟、输入和内部状态决定的。

2. 设计并描绘一个电路 ALT，其输出每个时钟周期在 0 和 1 之间切换，如下所示。你可以使用你在问题 (1) 中选择的触发器，以及 AND、OR 和 NOT 门。

Clock:         ____|¯¯¯¯|____|¯¯¯¯|____|¯¯¯
Output of ALT: ____|¯¯¯¯¯¯¯¯¯|_________|¯¯¯¯¯¯

3. 设计并描绘一个电路，使用冒泡排序算法对 8 个 4 位无符号整数进行排序。排序电路的输入和输出如下：

   • 输入 $I_0,I_1,\dots ,I_7$。每个都是一个 4 位无符号整数。
   • 1 位输入 $L$。
   • 输出 $O_0,O_1,\dots ,O_7$。每个都是一个 4 位无符号整数。
   • 1 位输出 $V$。

排序电路应如下工作。

(a) 当 $L$ 为 1 时，输入 $I_0,I_1,\dots ,I_7$ 使用 32 个触发器存储。这些存储的数据被认为是八个 4 位无符号整数，并在下文中称为 $v_0,v_1,\dots ,v_7$。

(b) $L$ 变为 0 后，在第一个时钟周期中，电路比较 $v_0$ 和 $v_1$，如果 $v_0>v_1$，则交换它们，否则保持不变。同样的操作应用于三对 $(v_2,v_3)$，$(v_4,v_5)$ 和 $(v_6,v_7)$。$v_0,v_1,\dots ,v_7$ 的新值输出到 $O_0,O_1,\dots ,O_7$。

(c) $L$ 变为 0 后的第二个时钟周期中，电路比较 $v_1$ 和 $v_2$，如果 $v_1>v_2$，则交换它们，否则保持不变。同样的操作应用于两对 $(v_3,v_4)$ 和 $(v_5,v_6)$。$v_0,v_1,\dots ,v_7$ 的新值输出到 $O_0,O_1,\dots ,O_7$。

(d) 电路在 $L$ 为 0 时重复步骤 (b) 和 (c)。如果在执行 (b) 或 (c) 的两个连续时钟周期内没有发生值交换，则 $V$ 置为 1，否则 $V$ 置为 0。

你可以在设计中使用以下电路：你在问题 (1) 中选择的触发器、你在问题 (2) 中设计的 ALT 电路、4 位比较器 CMP、4 位 2 比 1 多路复用器 MUX，以及 AND、OR 和 NOT 门。