R02-C-問1

题目

日文原文

【問1】
決定性有限オートマトン $M_1 = (P, \Sigma, δ_1, p_1, F_1)$ を考える．ただし，$P, \Sigma, δ_1, p_1, F_1$ はそれぞれ $M_1$ の状態集合，アルファベット，遷移関数，初期状態，最終状態の集合を表す．

• $P = \{p_0, p_1, p_2, p_3\}$,
• $\Sigma = \{0, 1, 2, 3\}$,
• $F_1 = \{p_0\}$,
• $δ_1(p_i, a) = p_{(i + n(a)) \bmod 4}$（ただし $i = 0, 1, 2, 3$）。 ここで $n(a)$ は記号 $a \in \Sigma$ に対応する整数であり，以下が成り立つ：

$$n(0) = 0, \quad n(1) = 1, \quad n(2) = 2, \quad n(3) = 3.$$

非負整数 $x$ と正の整数 $y$ に対して，$x \bmod y$ は $x$ を $y$ で割ったときの余りを表す．例えば，$δ_1(p_1, 3) = p_0$ である．次の問いに答えよ．

1. $M_1$ の状態遷移図を与えよ．
2. 決定性有限オートマトン $M_2 = (P, \Sigma, δ_1, p_1, F_2)$ は，$M_1$ と同じ状態集合，アルファベット，遷移関数，初期状態を持つ．$M_2$ と等価な決定性有限オートマトンの最小状態数が 2 であるとき，最終状態の集合 $F_2 ⊆ P$ の例をひとつ与えよ．
3. $\Sigma$ 上の文字列 $u$ に対して，

$$Y(u) = \begin{cases} 1 & \text{if } u \text{ is the empty string}, \\ Y(v) \times n(a) & \text{if } u = va, \ v \in \Sigma^*, \ a \in \Sigma. \end{cases}$$

$Y(u) \bmod 6 = 0$ かつ $Y(u) ≠ 0$ となる $u$ のみを受理する決定性有限オートマトン $M_3$ を考える．ここで，$M_3$ の状態集合を $\{q_0, q_1, q_2, q_3, q_6\}$，初期状態を $q_1$，最終状態の集合を $\{q_6\}$ とする．また，各状態は次のような文字列に対応する：

• $q_0$ は $Y(u) = 0$ を満たす文字列 $u$ に対応，
• $q_1$ は $Y(u) \bmod 2 ≠ 0$ かつ $Y(u) \bmod 3 ≠ 0$ を満たす文字列 $u$ に対応，
• $q_2$ は $Y(u) \bmod 2 = 0$ かつ $Y(u) \bmod 6 ≠ 0$ を満たす文字列 $u$ に対応，
• $q_3$ は $Y(u) \bmod 3 = 0$ かつ $Y(u) \bmod 6 ≠ 0$ を満たす文字列 $u$ に対応，
• $q_6$ は $Y(u) \bmod 6 = 0$ かつ $Y(u) ≠ 0$ を満たす文字列 $u$ に対応． $M_3$ の状態遷移図を与えよ．

---

中文翻译

【问题1】
考虑一个确定性有限自动机 $M_1 = (P, \Sigma, δ_1, p_1, F_1)$，其中 $P, \Sigma, δ_1, p_1, F_1$ 分别表示 $M_1$ 的状态集合、字母表、转移函数、初始状态和终止状态集合：

• $P = \{p_0, p_1, p_2, p_3\}$，
• $\Sigma = \{0, 1, 2, 3\}$，
• $F_1 = \{p_0\}$，
• $δ_1(p_i, a) = p_{(i + n(a)) \bmod 4}$（其中 $i = 0, 1, 2, 3$）。 这里 $n(a)$ 是字母 $a \in \Sigma$ 对应的整数，定义如下：

$$n(0) = 0, \quad n(1) = 1, \quad n(2) = 2, \quad n(3) = 3.$$

对于非负整数 $x$ 和正整数 $y$，$x \bmod y$ 表示 $x$ 除以 $y$ 的余数。例如，$δ_1(p_1, 3) = p_0$。回答以下问题：

1. 绘制 $M_1$ 的状态转移图。
2. 定义另一个自动机 $M_2 = (P, \Sigma, δ_1, p_1, F_2)$，其状态集合、字母表、转移函数和初始状态与 $M_1$ 相同。如果与 $M_2$ 等价的最小确定性有限自动机只有 2 个状态，给出一个 $F_2 ⊆ P$ 的例子。
3. 对于字母表 $\Sigma$ 上的字符串 $u$，定义：

$$Y(u) = \begin{cases} 1 & \text{如果 } u \text{ 是空字符串}, \\ Y(v) \times n(a) & \text{如果 } u = va, \ v \in \Sigma^*, \ a \in \Sigma. \end{cases}$$

考虑一个自动机 $M_3$，它接受的字符串 $u$ 满足 $Y(u) \bmod 6 = 0$ 且 $Y(u) ≠ 0$。$M_3$ 的状态集合为 $\{q_0, q_1, q_2, q_3, q_6\}$，初始状态为 $q_1$，终止状态集合为 $\{q_6\}$。各状态对应以下字符串：

• $q_0$ 对应 $Y(u) = 0$ 的字符串 $u$，
• $q_1$ 对应 $Y(u) \bmod 2 ≠ 0$ 且 $Y(u) \bmod 3 ≠ 0$ 的字符串 $u$，
• $q_2$ 对应 $Y(u) \bmod 2 = 0$ 且 $Y(u) \bmod 6 ≠ 0$ 的字符串 $u$，
• $q_3$ 对应 $Y(u) \bmod 3 = 0$ 且 $Y(u) \bmod 6 ≠ 0$ 的字符串 $u$，
• $q_6$ 对应 $Y(u) \bmod 6 = 0$ 且 $Y(u) ≠ 0$ 的字符串 $u$。 绘制 $M_3$ 的状态转移图。

---

M1 の状態遷移図 - TikZコード

以下は、$M_1$ の状態遷移図を Obsidian の TikZ プラグインで描画するコードです。

\usepackage{tikz}

\begin{document}
\begin{tikzpicture}

  % 定义状态
  \node (p0) at (0, 0) [circle, draw, double] {$p_0$}; % 接受状态
  \node (p1) at (3, 0) [circle, draw] {$p_1$};
  \node (p2) at (3, -3) [circle, draw] {$p_2$};
  \node (p3) at (0, -3) [circle, draw] {$p_3$};

  % 转移路径
  \draw[->] (p0) to[loop above] node {0} ();
  \draw[->] (p0) to[bend left] node[midway, above] {1} (p1);
  \draw[->] (p0) to[bend left=15] node[midway, right] {2} (p2);
  \draw[->] (p0) to[bend right] node[midway, left] {3} (p3);

  \draw[->] (p1) to[loop above] node {0} ();
  \draw[->] (p1) to[bend left] node[midway, right] {1} (p2);
  \draw[->] (p1) to[bend left=15] node[midway, right] {2} (p3);
  \draw[->] (p1) to[bend right] node[midway, above] {3} (p0);

  \draw[->] (p2) to[loop below] node {0} ();
  \draw[->] (p2) to[bend left] node[midway, below] {1} (p3);
  \draw[->] (p2) to[bend left=15] node[midway, left] {2} (p0);
  \draw[->] (p2) to[bend right] node[midway, right] {3} (p1);

  \draw[->] (p3) to[loop below] node {0} ();
  \draw[->] (p3) to[bend left] node[midway, left] {1} (p0);
  \draw[->] (p3) to[bend left=15] node[midway, left] {2} (p1);
  \draw[->] (p3) to[bend right] node[midway, below] {3} (p2);

\end{tikzpicture}
\end{document}

---

第二問：簡単な日本語での解説

問題の要点：

• $M_2$ は $M_1$ と同じ状態集合 $P = \{p_0, p_1, p_2, p_3\}$ を持っています。
• しかし、最終状態集合 $F_2$ は $M_1$ の $F_1 = \{p_0\}$ とは異なります。
• 問題は $M_2$ が最小化されたときに 2 つの状態で表せるような $F_2$ の例を求めています。

---

ポイント解説：

• 状態 $p_0, p_2$ は偶数の位置、$p_1, p_3$ は奇数の位置です。
• $M_1$ の遷移パターンを見ると、$p_0 \to p_2 \to p_0$ と $p_1 \to p_3 \to p_1$ のように、偶奇で循環しています。
• したがって、$F_2 = \{p_0, p_2\}$ または $F_2 = \{p_1, p_3\}$ とすることで、2 つの状態に分類できます。

---

回答例：

• $F_2 = \{p_0, p_2\}$
  または
• $F_2 = \{p_1, p_3\}$

どちらでも正しいです。偶数または奇数の状態を受理状態として選ぶことで、状態が 2 つに等価化されます。

---

第三問：M3の作り方の説明

1. 问题核心：理解 $Y(u)$ 的定义与含义

首先，重新理解 $Y(u)$ 的定义：

$$Y(u) = \begin{cases} 1 & \text{if } u \text{ is the empty string}, \\ Y(v) \times n(a) & \text{if } u = va, \ v \in \Sigma^*, \ a \in \Sigma. \end{cases}$$

这意味着：

• 如果字符串是空字符串（$\varepsilon$），则 $Y(\varepsilon) = 1$。
• 如果字符串 $u$ 由 $v$ 加上一个字符 $a$ 组成，即 $u = va$，则：

  $$Y(u) = Y(v) \times n(a)$$

  其中，$n(a)$ 是字母 $a$ 对应的整数值，具体为：

  $$n(0) = 0, \quad n(1) = 1, \quad n(2) = 2, \quad n(3) = 3$$

关键问题：$Y(u) = 0$ 是如何产生的？
根据递归定义：

• 如果字符串中包含 $0$，即 $a = 0$，则：

  $$Y(u) = Y(v) \times 0 = 0$$

  一旦某次乘法中乘以了 $0$，无论后续如何继续乘，$Y(u)$ 都将保持为 $0$。

---

2. 分析主体：字符串 $u$ 的乘积规则

• 你的分析对象是字符串 $u$，逐字符计算其对应的 $Y(u)$。
• 目标是判断 $Y(u) \bmod 6$ 的结果，并根据结果分类字符串。

分类方法：
题目已经给出了不同状态的分类规则，按照 $Y(u) \bmod 6$ 的结果，将字符串映射到不同的状态：

1. 状态 $q_0$：

   $$Y(u) = 0$$

   • 如果字符串 $u$ 包含字符 $0$，则直接进入状态 $q_0$，并在此停留。
   • 分析： $n(0) = 0$ 导致乘积结果变为 0，无论后续字符如何，状态都会停在 $q_0$。

2. 状态 $q_1$：

   $$Y(u) \bmod 2 \neq 0 \quad \text{かつ} \quad Y(u) \bmod 3 \neq 0$$

   • 表示 $Y(u)$ 既不能被 $2$ 整除，也不能被 $3$ 整除。
   • 分析： 典型情况是 $Y(u) = 1$ 或其他素数乘积。

3. 状态 $q_2$：

   $$Y(u) \bmod 2 = 0 \quad \text{かつ} \quad Y(u) \bmod 6 \neq 0$$

   • 说明 $Y(u)$ 可以被 $2$ 整除但不能被 $6$ 整除，即不能同时被 $3$ 整除。
   • 分析： 典型情况是 $Y(u) = 2, 4, 8$ 等。

4. 状态 $q_3$：

   $$Y(u) \bmod 3 = 0 \quad \text{かつ} \quad Y(u) \bmod 6 \neq 0$$

   • 说明 $Y(u)$ 可以被 $3$ 整除但不能被 $6$ 整除，即不能同时被 $2$ 整除。
   • 分析： 典型情况是 $Y(u) = 3, 9$ 等。

5. 状态 $q_6$（最终状态）：

   $$Y(u) \bmod 6 = 0 \quad \text{かつ} \quad Y(u) \neq 0$$

   • 表示 $Y(u)$ 可以被 $6$ 整除但不为 0。
   • 分析： 典型情况是 $Y(u) = 6, 12, 18$ 等。

---

3. 状态转移过程分析（构建自动机的步骤）

主体分析目标：字符串 $u$ 如何从一个状态转移到另一个状态。

• 每次读入字符 $a \in \Sigma$，执行乘法 $Y(u) \times n(a)$ 并计算结果 $\bmod 6$。
• 核心逻辑：
  1. 如果读到 $0$，无论当前状态如何，直接转移到 $q_0$ 并停留。
  2. 如果读到其他字符 $1, 2, 3$，则根据乘积的结果更新状态。

4. TikZ 状态转移图示例

下面是 $M_3$ 的 TikZ 状态转移图代码，按照上述逻辑绘制。

\usepackage{tikz}

\begin{document}
\begin{tikzpicture}

  % 定义状态
  \node (q0) at (0, 0) [circle, draw] {$q_0$};  % 状态 q0
  \node (q1) at (2, 0) [circle, draw] {$q_1$};  % 初始状态 q1
  \node (q2) at (4, 1) [circle, draw] {$q_2$};  % 状态 q2
  \node (q3) at (4, -1) [circle, draw] {$q_3$}; % 状态 q3
  \node (q6) at (6, 0) [circle, draw, double] {$q_6$}; % 接受状态 q6 (双圈)

  % 状态转移路径
  % q0 自环
  \draw[->] (q0) to[loop above] node {0, 1, 2, 3} ();
  
  % q1 自环和转移
  \draw[->] (q1) to[loop above] node {1} ();
  \draw[->] (q1) to node[midway, above] {2} (q2);
  \draw[->] (q1) to node[midway, right] {3} (q3);

  % q2 自环和转移
  \draw[->] (q2) to[loop above] node {1} ();
  \draw[->] (q2) to node[midway, below] {3} (q6);
  \draw[->] (q2) to node[midway, right] {2} (q0);

  % q3 自环和转移
  \draw[->] (q3) to[loop above] node {1} ();
  \draw[->] (q3) to node[midway, right] {2} (q6);
  \draw[->] (q3) to node[midway, left] {3} (q0);

  % q6 自环
  \draw[->] (q6) to[loop above] node {1, 2, 3} ();

\end{tikzpicture}
\end{document}

5. 结论

• 分析的主体是字符串 $u$ 的乘积 $Y(u)$ 以及它的模运算结果。
• 目标是通过逐个字符解析字符串，构建一个能根据模运算结果进行状态转移的自动机。
• 关键是理解 包含字符 $0$ 会直接使 $Y(u) = 0$，因此状态 $q_0$ 相当于失败状态。