2020S1

Problem 1

Let $\Sigma$ be a finite alphabet (i.e., a finite set of letters), and $ϵ$ be the empty sequence. We define the shuffle $w_1\otimes w_2\subseteq {\Sigma }^{\ast }$ of two words $w_1,w_2\in {\Sigma }^{\ast }$ as follows.

• For every $w\in {\Sigma }^{\ast }$,

$ϵ\otimes w=w\otimes ϵ=\{ϵ\}.$

• For every $a,b\in \Sigma$ and $w_1,w_2\in {\Sigma }^{\ast }$,

$(a{w}_1)\otimes (b{w}_2)=\{aw\mid w\in w_1\otimes (b{w}_2)\}\cup \{bw\mid w\in (a{w}_1)\otimes w_2\}.$

Furthermore, for two languages $L_1,L_2\subseteq {\Sigma }^{\ast }$, their shuffle $L_1\otimes L_2\subseteq {\Sigma }^{\ast }$ is defined by:

$L_1\otimes L_2={\bigcup }_{w_1\in L_1,w_2\in L_2}{w}_1\otimes w_2.$

For example, we have:

$\{ab,ba\}\otimes \{c,ϵ\}=(ab\otimes ϵ)\cup (ab\otimes c)\cup (ba\otimes ϵ)\cup (ba\otimes c)=\{ab,cab,acb,abc,ba,cba,bca,bac\}.$

Answer the following questions.

1. Compute $\{a,bb\}\otimes \{ab,cc\}$.

2. Suppose that deterministic finite automata ${\mathcal{A}}_1=(Q_1,\Sigma ,{\delta }_1,q_{1,0},F_1)$ and ${\mathcal{A}}_2=(Q_2,\Sigma ,{\delta }_2,q_{2,0},F_2)$ accept languages $L_1$ and $L_2$, respectively. Here, $Q_i,{\delta }_i,q_{i,0},$ and $F_i$ are respectively the set of states, the transition function, the initial state, and the set of final states of ${\mathcal{A}}_i$ (i $\in \{1,2\}$). You may assume that the transition functions ${\delta }_i\in Q_i\times \Sigma \to Q_i$ (i $\in \{1,2\}$) are total functions. Give a non-deterministic automaton that accepts $L_1\otimes L_2$.

3. Prove the correctness of your answer for question (2) above.

4. Let $L_3=\{a^n{b}^n\mid n\ge 0\}$ and $L_4=\{c^m{d}^m\mid m\ge 0\}$. Prove that $L_3\otimes L_4$ is not a context-free language. Here, you may use the pumping lemma for context-free languages.

---

设 $\Sigma$ 为一个有限字母表（即，有限的字母集合），$ϵ$ 为空序列。我们定义两个单词 $w_1,w_2\in {\Sigma }^{\ast }$ 的 shuffle $w_1\otimes w_2\subseteq {\Sigma }^{\ast }$ 如下。

• 对于每个 $w\in {\Sigma }^{\ast }$,

$ϵ\otimes w=w\otimes ϵ=\{ϵ\}.$

• 对于每个 $a,b\in \Sigma$ 和 $w_1,w_2\in {\Sigma }^{\ast }$,

$(a{w}_1)\otimes (b{w}_2)=\{aw\mid w\in w_1\otimes (b{w}_2)\}\cup \{bw\mid w\in (a{w}_1)\otimes w_2\}.$

此外，对于两个语言 $L_1,L_2\subseteq {\Sigma }^{\ast }$, 它们的 shuffle $L_1\otimes L_2\subseteq {\Sigma }^{\ast }$ 定义为：

$L_1\otimes L_2={\bigcup }_{w_1\in L_1,w_2\in L_2}{w}_1\otimes w_2.$

例如，我们有：

$\{ab,ba\}\otimes \{c,ϵ\}=(ab\otimes ϵ)\cup (ab\otimes c)\cup (ba\otimes ϵ)\cup (ba\otimes c)=\{ab,cab,acb,abc,ba,cba,bca,bac\}.$

回答以下问题。

1. 计算 $\{a,bb\}\otimes \{ab,cc\}$。

2. 假设确定有限自动机 ${\mathcal{A}}_1=(Q_1,\Sigma ,{\delta }_1,q_{1,0},F_1)$ 和 ${\mathcal{A}}_2=(Q_2,\Sigma ,{\delta }_2,q_{2,0},F_2)$ 分别接受语言 $L_1$ 和 $L_2$。这里，$Q_i,{\delta }_i,q_{i,0},$ 和 $F_i$ 分别是 ${\mathcal{A}}_i$ 的状态集、转移函数、初始状态和终止状态集（i $\in \{1,2\}$）。你可以假设转移函数 ${\delta }_i\in Q_i\times \Sigma \to Q_i$ (i $\in \{1,2\}$) 是全函数。给出一个接受 $L_1\otimes L_2$ 的非确定性自动机。

3. 证明你在上述问题 (2) 中的答案的正确性。

4. 设 $L_3=\{a^n{b}^n\mid n\ge 0\}$ 和 $L_4=\{c^m{d}^m\mid m\ge 0\}$。证明 $L_3\otimes L_4$ 不是上下文无关语言。这里，你可以使用上下文无关语言的抽气引理。

---

Problem 2

The following C code models the behavior of each philosopher in the dining philosophers problem.

void philosopher(int i) {
  do {
    pickup(i);
    eat();
    putdown(i);
    think();
  } while (1);
}

There are five threads running concurrently on a multiprocessor system, each of which executes the philosopher function. The argument $i$ is the index of each thread, where $i=0,1,\dots ,4$. In the philosopher function, the eat and think functions are executed in turn repeatedly, while the pickup and putdown functions are used for synchronization between threads, respectively, before and after the execution of the eat function so that two philosophers sitting side by side (namely, the $i$-th and the $(i+1)\%5$-th threads for each $i=0,1,\dots ,4$) cannot simultaneously execute the eat function. Now consider the problem of implementing the pickup and putdown functions, using binary semaphores. Here, the P and V operations on a binary semaphore X are respectively expressed as wait(X) and signal(X) in C code, and the counter value of each binary semaphore is initialized to 1. Also, assume that the eat and think functions never cause a side effect that may influence the outside of each function.

Answer the following questions.

1. For each $i=0,1,\dots ,4$, let $R[i]$ be a binary semaphore. A deadlock may occur when the following pickup and putdown functions are used. Describe how such a deadlock may occur.

void pickup(int i) {
  wait(R[i]);
  wait(R[(i + 1) % 5]);
}
 
void putdown(int i) {
  signal(R[i]);
  signal(R[(i + 1) % 5]);
}

2. For each $i=0,1,\dots ,4$, let $S[i]$ be a binary semaphore, and state[i] be a shared variable that represents the state of the $i$-th thread. Also, let mutex be a binary semaphore that is used to achieve a mutual exclusion on all the threads. In order for at least one thread to be able to execute the eat and think functions repeatedly without a deadlock, the pickup and putdown functions are redefined as follows. The void-type test function sets state[i] to eating and calls the signal function for $S[i]$, if a certain condition is satisfied. Describe the test function using C code. Note that you need not consider starvation of each thread. Also, assume that the initial value of state[i] is thinking.

enum {thinking, eating, waiting} state[5];
 
void pickup(int i) {
  wait(mutex);
  state[i] = waiting;
  test(i);
  signal(mutex);
  wait(S[i]);
}
 
void putdown(int i) {
  wait(mutex);
  state[i] = thinking;
  test((i + 4) % 5);
  test((i + 1) % 5);
  signal(mutex);
}

3. Regarding the C code in question (2), answer whether or not a thread may suffer from starvation, assuming that any enabled thread is eventually scheduled. If your answer is “yes”, describe how the starvation occurs and briefly explain how to modify the code to avoid the starvation. If your answer is “no”, then explain the reason.

---

以下 C 代码模拟了在哲学家进餐问题中每个哲学家的行为。

void philosopher(int i) {
  do {
    pickup(i);
    eat();
    putdown(i);
    think();
  } while (1);
}

有五个线程在多处理器系统上并发运行，每个线程都执行 philosopher 函数。参数 $i$ 是每个线程的索引，其中 $i=0,1,\dots ,4$。在 philosopher 函数中，eat 和 think 函数交替执行，而 pickup 和 putdown 函数分别用于在线程之间进行同步，以便在 eat 函数执行前后，使得并排的两个哲学家（即，对于每个 $i=0,1,\dots ,4$ 的 $i$-th 和 $(i+1)\%5$-th 线程）不能同时执行 eat 函数。现在考虑使用二进制信号量实现 pickup 和 putdown 函数。这里，二进制信号量 X 的 P 和 V 操作分别在 C 代码中表示为 wait(X) 和 signal(X)，每个二进制信号量的计数值初始化为 1。同样，假设 eat 和 think 函数永远不会产生可能影响每个函数外部的副作用。

回答以下问题。

1. 对于每个 $i=0,1,\dots ,4$，让 $R[i]$ 为二进制信号量。当使用以下 pickup 和 putdown 函数时，可能会发生死锁。描述死锁可能如何发生。

void pickup(int i) {
  wait(R[i]);
  wait(R[(i + 1) % 5]);
}
 
void putdown(int i) {
  signal(R[i]);
  signal(R[(i + 1) % 5]);
}

2. 对于每个 $i=0,1,\dots ,4$，让 $S[i]$ 为二进制信号量，state[i] 为表示第 $i$ 个线程状态的共享变量。同时，让 mutex 为一个二进制信号量，用于在所有线程上实现互斥。为了使至少一个线程能够反复执行 eat 和 think 函数而不出现死锁，pickup 和 putdown 函数重新定义如下。test 函数设置 state[i] 为 eating 并在满足特定条件时调用 signal 函数对 $S[i]$。使用 C 代码描述 test 函数。注意，你不需要考虑每个线程的饥饿情况。同样，假设 state[i] 的初始值是 thinking。

enum {thinking, eating, waiting} state[5];
 
void pickup(int i) {
  wait(mutex);
  state[i] = waiting;
  test(i);
  signal(mutex);
  wait(S[i]);
}
 
void putdown(int i) {
  wait(mutex);
  state[i] = thinking;
  test((i + 4) % 5);
  test((i + 1) % 5);
  signal(mutex);
}

3. 关于问题（2）中的 C 代码，回答线程是否可能遭遇饥饿，假设任何启用的线程最终都会被调度。如果你的答案是 “yes”，请描述饥饿是如何发生的，并简要解释如何修改代码以避免饥饿。如果你的答案是 “no”，请解释原因。

---

Problem 3

In this problem, the length of a string $s$ is written $\ell (s)$, and the $i$-th character of $s$ is written $s[i]$, where the first character is $s[0]$. The string obtained by removing the first $i$ characters from $s$ is written $s+i$. We assume $0\le i<\ell (s)$ in $s[i]$ and $s+i$. For example, if $s=\text{PROBLEM}$, then $s[0]=\text{P}$ and $s+3=\text{BLEM}$. The set of characters consists of $N$ characters, where $N$ is an integer constant no less than 2, and for each character $c$ a distinct positive integer $\text{numval}(c)\le N$ is defined. Suppose that the computation of $s+i$ for given $s$ and $i$, and that of $\text{numval}(c)$ for given $c$, take $O(1)$ time. Also suppose that each of integer addition, multiplication and remainder takes $O(1)$ time, and that overflow will never occur in integer operations.

We consider the following problem FIND: For given strings $p$ and $s$, find the first position $i$ at which $s$ matches $p$. In other words, $i$ is the least non-negative integer that satisfies

$\forall j\in \{0,1,\dots ,\ell (p)-1\}.s[i+j]=p[j].$

In case there is no such $i$, we define $i=-1$. In the following, we assume $\ell (s)>\ell (p)>0$.

For strings $r$ and $p$ with $0<\ell (p)\le \ell (r)$, let function $\text{eq}(r,p)$ return 1 if the first $\ell (p)$ characters of $r$ equal $p$, and return 0 otherwise. Suppose that the time complexity of $\text{eq}(r,p)$ is $O(\ell (p))$. The following algorithm $S$ solves the problem FIND:

for (i = 0; i <= \ell(s) - \ell(p); i++)
  if (\text{eq}(s + i, p) == 1)
    return i;
return -1;

Answer the following questions.

1. Express the order of the worst-case time complexity of algorithm $S$ in terms of $\ell (s)$ and $\ell (p)$.

In the following, the hash value $h(s,m)$ of the first $m$ characters of string $s$ is defined by

$h(s,m)=\left({\sum }_{i=0}^{m-1}\text{numval}(s[i])\cdot d^{m-i-1}\right)\mathrm{mod}q,$

where $d$ and $q$ are positive integer constants, and $0<m\le \ell (s)$ is assumed.

2. Assume that $i<\ell (s)-m$ holds, and that $h^{\prime }=h(s+i,m)$ and $d_m=d^{m-1}$ have been precomputed. Show an algorithm or an expression to compute $h(s+i+1,m)$ in $O(1)$ time.

3. Give an algorithm $H_0$ that finds the least non-negative integer $i$ that satisfies $h(p,\ell (p))=h(s+i,\ell (p))$ (but answers $-1$ if no such $i$ exists) in time $O(\ell (s)+\ell (p))$. Also, answer in what condition the algorithm $H_0$ outputs a value which is not the solution of problem FIND.

4. Give an algorithm $H$ that satisfies all of the following conditions: (a) it always answers the solution of problem FIND, (b) it searches for the answer by using hash $h(s,m)$ and function $\text{eq}(r,p)$, and (c) if we assume that the number of integers $i$ that satisfy $h(p,\ell (p))=h(s+i,\ell (p))$ for given $s$ and $p$ is $O(1)$ independently of $s$ and $p$, then the algorithm $H$ runs in time $O(\ell (s)+\ell (p))$. In addition, show in what condition the time complexity of the algorithm $H$ is larger than $O(\ell (s)+\ell (p))$. Also, answer the order of the worst-case time complexity of the algorithm $H$ in terms of $\ell (s)$ and $\ell (p)$.

---

在这个问题中，字符串 $s$ 的长度写作 $\ell (s)$，并且 $s$ 的第 $i$ 个字符写作 $s[i]$，其中第一个字符是 $s[0]$。通过去除 $s$ 的前 $i$ 个字符得到的字符串写作 $s+i$。我们假设 $0\le i<\ell (s)$ 在 $s[i]$ 和 $s+i$ 中。例如，如果 $s=\text{PROBLEM}$，则 $s[0]=\text{P}$ 并且 $s+3=\text{BLEM}$。字符集由 $N$ 个字符组成，其中 $N$ 是一个整数常数，不小于 2，并且对于每个字符 $c$ 定义了一个不超过 $N$ 的不同正整数 $\text{numval}(c)$。假设给定 $s$ 和 $i$ 的 $s+i$ 的计算和给定 $c$ 的 $\text{numval}(c)$ 的计算时间都是 $O(1)$。还假设每个整数加法、乘法和取模操作的时间都是 $O(1)$，并且整数运算中不会出现溢出。

我们考虑以下问题 FIND：对于给定的字符串 $p$ 和 $s$，找到第一个位置 $i$，使得 $s$ 匹配 $p$。换句话说，$i$ 是满足以下条件的最小非负整数：

$\forall j\in \{0,1,\dots ,\ell (p)-1\}.s[i+j]=p[j].$

如果没有这样的 $i$，我们定义 $i=-1$。在下面的内容中，我们假设 $\ell (s)>\ell (p)>0$。

对于字符串 $r$ 和 $p$，其中 $0<\ell (p)\le \ell (r)$，让函数 $\text{eq}(r,p)$ 返回 1，如果 $r$ 的前 $\ell (p)$ 个字符等于 $p$，否则返回 0。假设 $\text{eq}(r,p)$ 的时间复杂度是 $O(\ell (p))$。以下算法 $S$ 解决了问题 FIND：

for (i = 0; i <= \ell(s) - \ell(p); i++)
  if (\text{eq}(s + i, p) == 1)
    return i;
return -1;

回答以下问题。

1. 用 $\ell (s)$ 和 $\ell (p)$ 表示算法 $S$ 的最坏情况下的时间复杂度。

在下文中，字符串 $s$ 的前 $m$ 个字符的哈希值 $h(s,m)$ 定义为

$h(s,m)=\left({\sum }_{i=0}^{m-1}\text{numval}(s[i])\cdot d^{m-i-1}\right)\mathrm{mod}q,$

其中 $d$ 和 $q$ 是正整数常数，并且假设 $0<m\le \ell (s)$。

2. 假设 $i<\ell (s)-m$ 成立，并且 $h^{\prime }=h(s+i,m)$ 和 $d_m=d^{m-1}$ 已经被预计算。展示一个算法或表达式，用于在 $O(1)$ 时间内计算 $h(s+i+1,m)$。

3. 提出一个算法 $H_0$，它能找到满足 $h(p,\ell (p))=h(s+i,\ell (p))$ 的最小非负整数 $i$（但如果没有这样的 $i$ 存在，则返回 $-1$），时间复杂度为 $O(\ell (s)+\ell (p))$。还要回答在什么情况下算法 $H_0$ 输出的值不是问题 FIND 的解。

4. 提出一个算法 $H$，满足以下所有条件：(a) 它总是能解答问题 FIND，(b) 它通过使用哈希 $h(s,m)$ 和函数 $\text{eq}(r,p)$ 来搜索答案，(c) 如果我们假设满足 $h(p,\ell (p))=h(s+i,\ell (p))$ 的整数 $i$ 的数量对于给定的 $s$ 和 $p$ 是 $O(1)$ 而独立于 $s$ 和 $p$，则算法 $H$ 以时间

$O(\ell (s)+\ell (p))$ 运行。此外，说明在什么情况下算法 $H$ 的时间复杂度大于 $O(\ell (s)+\ell (p))$。还要回答算法 $H$ 的最坏情况时间复杂度的阶数，以 $\ell (s)$ 和 $\ell (p)$ 表示。