R02-C-問1

题目

日文原文

【問1】
決定性有限オートマトン $M_1=(P,\Sigma ,{\delta }_1,p_1,F_1)$ を考える．ただし，$P,\Sigma ,{\delta }_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\}$,
• ${\delta }_1(p_i,a)=p_{(i+n(a))\mathrm{mod}4}$（ただし $i=0,1,2,3$）。
  ここで $n(a)$ は記号 $a\in \Sigma$ に対応する整数であり，以下が成り立つ：

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

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

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

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

$Y(u)\mathrm{mod}6=0$ かつ $Y(u)\ne 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)\mathrm{mod}2\ne 0$ かつ $Y(u)\mathrm{mod}3\ne 0$ を満たす文字列 $u$ に対応，
• $q_2$ は $Y(u)\mathrm{mod}2=0$ かつ $Y(u)\mathrm{mod}6\ne 0$ を満たす文字列 $u$ に対応，
• $q_3$ は $Y(u)\mathrm{mod}3=0$ かつ $Y(u)\mathrm{mod}6\ne 0$ を満たす文字列 $u$ に対応，
• $q_6$ は $Y(u)\mathrm{mod}6=0$ かつ $Y(u)\ne 0$ を満たす文字列 $u$ に対応．
  $M_3$ の状態遷移図を与えよ．

---

中文翻译

【问题1】
考虑一个确定性有限自动机 $M_1=(P,\Sigma ,{\delta }_1,p_1,F_1)$，其中 $P,\Sigma ,{\delta }_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\}$，
• ${\delta }_1(p_i,a)=p_{(i+n(a))\mathrm{mod}4}$（其中 $i=0,1,2,3$）。
  这里 $n(a)$ 是字母 $a\in \Sigma$ 对应的整数，定义如下：

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

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

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

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

考虑一个自动机 $M_3$，它接受的字符串 $u$ 满足 $Y(u)\mathrm{mod}6=0$ 且 $Y(u)\ne 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)\mathrm{mod}2\ne 0$ 且 $Y(u)\mathrm{mod}3\ne 0$ 的字符串 $u$，
• $q_2$ 对应 $Y(u)\mathrm{mod}2=0$ 且 $Y(u)\mathrm{mod}6\ne 0$ 的字符串 $u$，
• $q_3$ 对应 $Y(u)\mathrm{mod}3=0$ 且 $Y(u)\mathrm{mod}6\ne 0$ 的字符串 $u$，
• $q_6$ 对应 $Y(u)\mathrm{mod}6=0$ 且 $Y(u)\ne 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{array}{ll}1& \text{if }u\text{ is the empty string},\\ Y(v)\times n(a)& \text{if }u=va,v\in {\Sigma }^{\ast },a\in \Sigma .\end{array}$$

这意味着：

• 如果字符串是空字符串（$\epsilon$），则 $Y(\epsilon )=1$。
• 如果字符串 $u$ 由 $v$ 加上一个字符 $a$ 组成，即 $u=va$，则： $$Y(u)=Y(v)\times n(a)$$ 其中，$n(a)$ 是字母 $a$ 对应的整数值，具体为： $$n(0)=0,n(1)=1,n(2)=2,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)\mathrm{mod}6$ 的结果，并根据结果分类字符串。

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

1. 状态 $q_0$：

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

2. 状态 $q_1$：

   $$Y(u)\mathrm{mod}2\ne 0\text{かつ}Y(u)\mathrm{mod}3\ne 0$$
   • 表示 $Y(u)$ 既不能被 $2$ 整除，也不能被 $3$ 整除。
   • 分析： 典型情况是 $Y(u)=1$ 或其他素数乘积。

3. 状态 $q_2$：

   $$Y(u)\mathrm{mod}2=0\text{かつ}Y(u)\mathrm{mod}6\ne 0$$
   • 说明 $Y(u)$ 可以被 $2$ 整除但不能被 $6$ 整除，即不能同时被 $3$ 整除。
   • 分析： 典型情况是 $Y(u)=2,4,8$ 等。

4. 状态 $q_3$：

   $$Y(u)\mathrm{mod}3=0\text{かつ}Y(u)\mathrm{mod}6\ne 0$$
   • 说明 $Y(u)$ 可以被 $3$ 整除但不能被 $6$ 整除，即不能同时被 $2$ 整除。
   • 分析： 典型情况是 $Y(u)=3,9$ 等。

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

   $$Y(u)\mathrm{mod}6=0\text{かつ}Y(u)\ne 0$$
   • 表示 $Y(u)$ 可以被 $6$ 整除但不为 0。
   • 分析： 典型情况是 $Y(u)=6,12,18$ 等。

---

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

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

• 每次读入字符 $a\in \Sigma$，执行乘法 $Y(u)\times n(a)$ 并计算结果 $\mathrm{mod}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$ 相当于失败状态。