問1
以下の状態遷移図を持つ決定性有限オートマトンを とする.
- , 状態集合
- ,
- は遷移関数
- は初期状態,
- は最終状態集合.
\usepackage{tikz}
\begin{document}
\begin{tikzpicture}[->, shorten >=1pt, auto, node distance=1.5cm, thick]
% Define the states
\node (q2) at (180:1.5cm) [circle, draw, double] {$q_2$}; % q2 at 180° (leftmost point)
% Define the pentagon nodes using polar coordinates around q2
\foreach \i in {1, 2, 3, 4} {
\node (q\the\numexpr\i+2\relax) at ({180 - 72*\i}:1.5cm) [circle, draw] {$q_{\the\numexpr\i+2\relax}$};
}
\node (q1) [circle, draw, left of=q2] {$q_1$};
\node (q0) [circle, draw, left of=q1] {$q_0$};
% Draw the transitions
\path (q0) edge node {0} (q1)
(q1) edge node {0} (q2)
(q2) edge node {0} (q3)
(q3) edge node {0} (q4)
(q4) edge node {0} (q5)
(q5) edge node {0} (q6)
(q6) edge node {0} (q2);
% Start state arrow
\draw[->] (-5.5, -1) -- (q0);
\end{tikzpicture}
\end{document}このオートマトン に基づいて、決定性有限オートマトン を、
{w \in {0, 1}^* | #_0(w) \mod 5 = 2, #_1(w) \mod 5 = 0}
### 中文翻译 定义以下状态转移图的确定性有限自动机 $M = (K, \Sigma, \delta, q_0, F)$： - $K = \{q_0, q_1, \dots, q_6\}$，状态集合 - $\Sigma = \{0\}$，输入字母表 - $\delta: K \times \Sigma \to K$ 为状态转移函数 - $q_0$ 是初始状态 - $F = \{q_2\}$ 是终态集合 ```tikz \usepackage{tikz} \begin{document} \begin{tikzpicture}[->, shorten >=1pt, auto, node distance=1.5cm, thick] % Define the states \node (q2) at (180:1.5cm) [circle, draw, double] {$q_2$}; % q2 at 180° (leftmost point) % Define the pentagon nodes using polar coordinates around q2 \foreach \i in {1, 2, 3, 4} { \node (q\the\numexpr\i+2\relax) at ({180 - 72*\i}:1.5cm) [circle, draw] {$q_{\the\numexpr\i+2\relax}$}; } \node (q1) [circle, draw, left of=q2] {$q_1$}; \node (q0) [circle, draw, left of=q1] {$q_0$}; % Draw the transitions \path (q0) edge node {0} (q1) (q1) edge node {0} (q2) (q2) edge node {0} (q3) (q3) edge node {0} (q4) (q4) edge node {0} (q5) (q5) edge node {0} (q6) (q6) edge node {0} (q2); % Start state arrow \draw[->] (-5.5, -1) -- (q0); \end{tikzpicture} \end{document} ``` 基于此自动机 $M$，定义确定性有限自动机 $\tilde{M} = (\tilde{K}, \tilde{\Sigma}, \tilde{\delta}, \tilde{q_0}, \tilde{F})$，如下： $$\tilde{K} = K \times K, \ \tilde{\Sigma} = \{0, 1\}, \ \tilde{q_0} = (q_0, q_0), \ \tilde{F} = \{(q_2, q_2)\},$$ $$\tilde{\delta}((q, q'), a) = \begin{cases} (\delta(q, 0), \delta(q', 0)) & a = 0 \text{ 时}, \\ (\delta(q, 0), \delta(q', 0)) & a = 1 \text{ 时} \end{cases}$$ 对于输入字符串 $10$，自动机 $\tilde{M}$ 的状态序列为： $$(q_0, q_0) \to (q_1, q_2) \to (q_2, q_3),$$ 最终状态为 $(q_2, q_3)$。回答以下问题： 1. 给出输入字符串 $01101$ 在自动机 $\tilde{M}$ 上的状态序列。 2. 证明当 $n (≥ 1)$ 是 $5$ 的倍数时，输入字符串 $1^n$ 在自动机 $\tilde{M}$ 上的最终状态为 $(q_5, q_5)$。 3. 对于长度 $≥ 2$ 的字符串 $w ∈ \{0, 1\}^*$，自动机 $\tilde{M}$ 的最终状态记为 $(q_{iw}, q_{jw})$，其中 $iw, jw ∈ \{2, 3, 4, 5, 6\}$。请用字符串 $w$ 中 $0$ 和 $1$ 的个数（即 $\#_0(w)$ 和 $\#_1(w)$）表示 $iw$ 和 $jw$。 4. 证明自动机 $\tilde{M}$ 接受的语言是：{w \in {0, 1}^* | #_0(w) \mod 5 = 2, #_1(w) \mod 5 = 0}
其中 $x \mod y$ 表示 $x$ 除以 $y$ 的余数。 --- # o1 **先にことわり** 題意をよく読むと，「入力が $\texttt{0}$ のときは元のオートマトン $M$ の“1ステップ”遷移を両座標ともに踏む」「入力が $\texttt{1}$ のときは，第一座標は“1ステップ”，第二座標は“2ステップ”進む」という形になっていることが分かります。実際，問題文にある > 入力文字列 $\texttt{10}$ に対する状態遷移が > $$ > (q_0,q_0)\;\xrightarrow{\;\texttt{1}\;}\;(q_1,q_2)\;\xrightarrow{\;\texttt{0}\;}\;(q_2,q_3) > $$ という例がその証拠です。もし「$\texttt{1}$ を読むと両座標ともに “同じステップ” 進む」という定義であれば，第一座標・第二座標が異なる状態に分かれるはずがありません。ところが実際は - 第一座標は「1 ステップ進む」($q_0 \to q_1$) - 第二座標は「2 ステップ進む」($q_0 \to q_1 \to q_2$) という動きをしているからこそ，$(q_0,q_0) \xrightarrow{\texttt{1}} (q_1,q_2)$ になっています。 同様に，$\texttt{0}$ を読むと「両座標とも 1 ステップ進む」動きになります。元のオートマトン $M$ ではq_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3 \xrightarrow{0} q_4 \xrightarrow{0} q_5 \xrightarrow{0} q_6 \xrightarrow{0} q_2 \xrightarrow{0}\dots
という 1 ステップ遷移のサイクルがあり，$q_2 \to q_3 \to q_4 \to q_5 \to q_6 \to q_2$ の部分は「長さ 5 のループ」を形成しています。 --- ## 1. 入力文字列 $\texttt{01101}$ に対する状態系列 与えられた規則 - $\texttt{0}$ を読む $\;\to\;) $\bigl(\delta(q,0),\,\delta(q',0)\bigr)$ - すなわち「両座標とも1ステップ進む」 - $\texttt{1}$ を読む $\;\to\;) $\bigl(\delta(q,0),\,\delta(\delta(q',0),0)\bigr)$ - すなわち「第一座標は1ステップ，第二座標は2ステップ進む」 という解釈で，$\tilde{M}$ 上の状態遷移を追うと次のようになります。入力 $\texttt{01101}$ は左から順に $\texttt{0}$, $\texttt{1}$, $\texttt{1}$, $\texttt{0}$, $\texttt{1}$ の 5 文字です。 1. 初期状態は $(q_0,q_0)$。 2. **$\texttt{0}$ を読む** - 第一座標: $q_0 \xrightarrow{0} q_1$ - 第二座標: $q_0 \xrightarrow{0} q_1$ - よって $(q_0,q_0)\xrightarrow{\texttt{0}}(q_1,q_1)$ 3. **$\texttt{1}$ を読む** - 第一座標: 1ステップ $q_1 \xrightarrow{0} q_2$ - 第二座標: 2ステップ $q_1 \xrightarrow{0} q_2 \xrightarrow{0} q_3$ - よって $(q_1,q_1)\xrightarrow{\texttt{1}}(q_2,q_3)$ 4. **$\texttt{1}$ を読む** - 第一座標: 1ステップ $q_2 \xrightarrow{0} q_3$ - 第二座標: 2ステップ $q_3 \xrightarrow{0} q_4 \xrightarrow{0} q_5$ - ただし元のオートマトンで $q_3 \xrightarrow{0} q_4$, $q_4 \xrightarrow{0} q_5$ - よって $(q_2,q_3)\xrightarrow{\texttt{1}}(q_3,q_5)$ 5. **$\texttt{0}$ を読む** - 第一座標: $q_3 \xrightarrow{0} q_4$ - 第二座標: $q_5 \xrightarrow{0} q_6$ - よって $(q_3,q_5)\xrightarrow{\texttt{0}}(q_4,q_6)$ 6. **$\texttt{1}$ を読む** - 第一座標: 1ステップ $q_4 \xrightarrow{0} q_5$ - 第二座標: 2ステップ $q_6 \xrightarrow{0} q_2 \xrightarrow{0} q_3$ - ループ部 $q_6 \to q_2 \to q_3$ - よって $(q_4,q_6)\xrightarrow{\texttt{1}}(q_5,q_3)$ 以上から，$\texttt{01101}$ に対する状態系列は(q_0,q_0)
;\xrightarrow{\texttt{0}};
(q_1,q_1)
;\xrightarrow{\texttt{1}};
(q_2,q_3)
;\xrightarrow{\texttt{1}};
(q_3,q_5)
;\xrightarrow{\texttt{0}};
(q_4,q_6)
;\xrightarrow{\texttt{1}};
(q_5,q_3)
\text{第一座標は }n\text{ ステップ前進},\quad
\text{第二座標は }2n\text{ ステップ前進}
q_0 \xrightarrow{0} q_1 \xrightarrow{0} q_2
\;\xrightarrow{0} q_3 \xrightarrow{0} q_4
\xrightarrow{0} q_5 \xrightarrow{0} q_6
\xrightarrow{0} q_2 \xrightarrow{0}\dots
\#_0(w) \equiv 2 \pmod{5},
\quad
\#_1(w) \equiv 0 \pmod{5}
\{\,w \in \{0,1\}^* \mid \#_0(w) \bmod 5 = 2,\;\#_1(w)\bmod 5 = 0\}
(q_0, q_0) \to (q_1, q_1) \to (q_2, q_2) \to (q_3, q_3) \to (q_4, q_4) \to (q_5, q_5)
**2. 证明当 $n (≥ 1)$ 是 $5$ 的倍数时，输入字符串 $1^n$ 在自动机 $\tilde{M}$ 上的最终状态为 $(q_5, q_5)$。** 由于输入字符串仅由 1 组成，且转移函数定义为 $\tilde{\delta}((q, q'), a) = (\delta(q, 0), \delta(q', 0))$，对于每一个输入 1，状态转移都按照输入 0 来进行。 因此，输入 $1^n$ 时，状态序列为：(q_0, q_0) \xrightarrow{1} (q_1, q_1) \xrightarrow{1} (q_2, q_2) \xrightarrow{1} (q_3, q_3) \xrightarrow{1} (q_4, q_4) \xrightarrow{1} (q_5, q_5)
当 $n$ 是 5 的倍数时，最终状态为 $(q_5, q_5)$。 **3. 对于长度 $≥ 2$ 的字符串 $w ∈ \{0, 1\}^*$，自动机 $\tilde{M}$ 的最终状态记为 $(q_{iw}, q_{jw})$，其中 $iw, jw ∈ \{2, 3, 4, 5, 6\}$。请用字符串 $w$ 中 $0$ 和 $1$ 的个数（即 $\#_0(w)$ 和 $\#_1(w)$）表示 $iw$ 和 $jw$。** 根据转移函数定义，状态转移始终按照输入 0 来进行。因此，最终状态 $(q_{iw}, q_{jw})$ 可以表示为：iw = (#_0(w) + #_1(w)) \mod 5 + 2
jw = (#_0(w) + #_1(w)) \mod 5 + 2
**4. 证明自动机 $\tilde{M}$ 接受的语言是：**{w \in {0, 1}^* \mid #_0(w) \mod 5 = 2, #_1(w) \mod 5 = 0}
自动机 $\tilde{M}$ 的接受状态为 $(q_2, q_2)$。根据转移函数定义，状态转移始终按照输入 0 来进行。因此，要使最终状态为 $(q_2, q_2)$，需要满足：(#_0(w) + #_1(w)) \mod 5 = 2
并且，由于 $\#_1(w) \mod 5 = 0$，所以：#_0(w) \mod 5 = 2
因此，自动机 $\tilde{M}$ 接受的语言是：{w \in {0, 1}^* \mid #_0(w) \mod 5 = 2, #_1(w) \mod 5 = 0}