跳到主要内容

東京大学 情報理工学系研究科 創造情報学専攻 2022年8月実施 筆記試験 第1問

标签：

Author​

itsuitsuki

Description​

We are constructing a deterministic finite automaton (DFA) that judges whether the sum of two binary integers is a multiple of three or not.

(1) A DFA is represented by a directed graph called a state diagram. Figure 1 is an example of a state diagram. The states of a DFA are represented by the nodes of the graph. When a DFA in state qq reads a symbol aa, it changes its state according to the outgoing edge labeled aa of the node corresponding to qq. The set of allowed input symbols is a finite set, which is called its input alphabet. In the state graph of a DFA, each node has exactly one outgoing edge for each symbol in its input alphabet.

One of the states is the start state, which is indicated by the arrow labeled start. Some states are designated as final states, which are indicated by double circles. When a DFA MM in its start state will be in one of the final states after reading all symbols of a symbol string ww one-by-one from left to right, we say MM accepts ww.

(1-1) Let M1M_1 be the DFA represented by Figure 1. The input alphabet of M1M_1 is {0,1}\{0, 1\}. Answer the state that M1M_1 will be in after reading the symbol string 0101110 starting in the start state.

(1-2) Answer the shortest symbol string starting with 0101110 that the DFA M1M_1 accepts.

(1-3) Construct a DFA M2M_2 that accepts a symbol string ww if and only if the length of ww is an even number, and draw its state diagram. M2M_2 must satisfy the following conditions.

  • (Condition 1) The number of states of M2M_2 is two.
  • (Condition 2) The input alphabet of M2M_2 is {0,1}\{0, 1\}.

(2) Consider a string of symbols in {0,1}\{0, 1\} to be a binary number. Let (xn−1xn−2⋯x0)2(x_{n-1}x_{n-2} \cdots x_0)_2 denote the nn-digit binary number whose ii-th digit (0≤i<n)(0 \le i < n) from the least significant digit is xi∈{0,1}x_i \in \{0, 1\}. Let V(xn−1xn−2⋯x0)\mathcal{V}(x_{n-1}x_{n-2} \cdots x_0) denote its value. When the string xn−1xn−2⋯x0x_{n-1}x_{n-2} \cdots x_0 starts with a sequence of 0s, let V(xn−1xn−2⋯x0)\mathcal{V}(x_{n-1}x_{n-2} \cdots x_0) denote the value of the string without the sequence of 0s. The string whose length is zero is called an empty string, denoted by ε\varepsilon. Let V(ε)=0\mathcal{V}(\varepsilon) = 0. For example, V(0101110)\mathcal{V}(0101110) is 46 in decimal. For every binary number with an even number of digits (x2n−1x2n−2⋯x0)2(x_{2n-1}x_{2n-2} \cdots x_0)_2, show

V(x2n−1x2n−2⋯x0)≡(2∑i=0n−1x2i+1+∑i=0n−1x2i)(mod3).\mathcal{V}(x_{2n-1}x_{2n-2} \cdots x_0) \equiv \left( 2 \sum_{i=0}^{n-1} x_{2i+1} + \sum_{i=0}^{n-1} x_{2i} \right) \pmod 3.

Here, "a≡b(mod3)a \equiv b \pmod 3" denotes the remainders of aa and bb are the same when they are divided by three. In what follows, we will omit " (mod3)\pmod 3" and simply denote "a≡ba \equiv b."

(3) Consider ww, a string of symbols in {0,1}\{0, 1\}, to be a binary number (w)2(w)_2. Construct a DFA M3M_3 that accepts wRw^R, the string ww in reverse order, if and only if its length is an even number and

V(w)≡0 \mathcal{V}(w) \equiv 0

holds, and draw its state diagram. M3M_3 must satisfy the following conditions.

  • (Condition 1) The number of states of M3M_3 is six.
  • (Condition 2) The input alphabet of M3M_3 is {0,1}\{0, 1\}.

(4) Consider ww, a string of symbols in {0,1}\{0, 1\}, to be a binary number (w)2(w)_2. Construct a DFA M4M_4 that accepts wRw^R if and only if

V(w)≡0\mathcal{V}(w) \equiv 0

holds regardless of the length of ww, and draw its state diagram. M4M_4 must satisfy the following conditions.

  • (Condition 1) The number of states of M4M_4 is three.
  • (Condition 2) The input alphabet of M4M_4 is {0,1}\{0, 1\}.

(5) Let

Σ={(ab)∣a,b∈{0,1}}.\Sigma = \left\{ \binom{a}{b} \mid a, b \in \{0, 1\} \right\}.

For w=(xn−1yn−1)(xn−2yn−2)⋯(x0y0)w = \binom{x_{n-1}}{y_{n-1}} \binom{x_{n-2}}{y_{n-2}} \cdots \binom{x_0}{y_0}, a string of symbols in Σ\Sigma with length nn, construct a DFA M5M_5 that accepts wRw^R if and only if

V(xn−1xn−2⋯x0)+V(yn−1yn−2⋯y0)≡0\mathcal{V}(x_{n-1}x_{n-2} \cdots x_0) + \mathcal{V}(y_{n-1}y_{n-2} \cdots y_0) \equiv 0

holds, and draw its state diagram. M5M_5 must satisfy the following conditions.

  • (Condition 1) The number of states of M5M_5 is three.
  • (Condition 2) The input alphabet of M5M_5 is Σ\Sigma.

题目描述​

构造确定性有限自动机（DFA），判断两个二进制整数之和是否为 3 的倍数。

  1. DFA 用称为状态图的有向图表示：结点为状态；处于 (q) 时读入符号 (a)，沿 (q) 的标号为 (a) 的唯一出边转移。允许输入符号的有限集合称为输入字母表，每个状态对字母表中每个符号恰有一条出边。一个状态是以 start 箭头标出的初态，双圈表示终态。DFA 从初态自左向右逐符号读完串 (w) 后若位于终态，就接受 (w)。
    1. 对图 1 的 DFA (M_1)，字母表为 ({0,1})。从初态读完 0101110 后处于哪个状态？
    2. 求以 0101110 开头且被 (M_1) 接受的最短符号串。
    3. 构造 DFA (M_2)，当且仅当串长为偶数时接受，并画状态图。要求恰有 2 个状态，字母表为 ({0,1})。
  2. 把 ({0,1}) 串视为二进制数。记 ((x_{n-1}\cdots x_0)2) 的从最低位起第 (i) 位为 (x_i)，其数值为 (\mathcal V(x{n-1}\cdots x_0))。开头的连续 0 不影响数值；空串记为 (\varepsilon)，令 (\mathcal V(\varepsilon)=0)。例如 (\mathcal V(0101110)=46)。证明对任意偶数位二进制数 [ \mathcal V(x_{2n-1}\cdots x_0) \equiv 2\sum_{i=0}^{n-1}x_{2i+1}+\sum_{i=0}^{n-1}x_{2i} \pmod3. ] 后文省略“(\pmod3)”，直接写 (\equiv)。
  3. 把串 (w) 视为二进制数 ((w)_2)，(w^R) 表示逆序串。构造并画 DFA (M_3)，当且仅当 (w) 长度为偶数且 (\mathcal V(w)\equiv0) 时接受 (w^R)。要求恰有 6 个状态，字母表 ({0,1})。
  4. 构造并画 DFA (M_4)，不论 (w) 长度为何，当且仅当 (\mathcal V(w)\equiv0) 时接受 (w^R)。要求恰有 3 个状态，字母表 ({0,1})。
  5. 令 [ \Sigma=\left{\binom ab\mid a,b\in{0,1}\right}. ] 对长度 (n) 的串 [ w=\binom{x_{n-1}}{y_{n-1}}\binom{x_{n-2}}{y_{n-2}}\cdots\binom{x_0}{y_0}, ] 构造并画 DFA (M_5)，当且仅当 [ \mathcal V(x_{n-1}\cdots x_0)+\mathcal V(y_{n-1}\cdots y_0)\equiv0 ] 时接受 (w^R)。要求恰有 3 个状态，输入字母表为 (\Sigma)。
本页目录