R06-C-問1
問1
アルファベット 上の言語 を以下のように定義する：
L = \{ w \in \Sigma^* \mid w \in \{xad, xadd, xdad\} \text{ for some } x \in \Sigma^* \}$$以下の図は $L$ を受理する非決定性有限オートマトン $M = (K, \Sigma, \delta, q_0, F)$ の状態遷移図である。ただし - $K = \{q_0, q_1, \dots, q_8\}$ - $\Sigma = \{a, d\}$ - $\delta$ - $q_0$ - $F = \{q_2, q_5, q_8\}$ は、それぞれ $M$ の状態の集合、アルファベット、遷移関数、初期状態、受理状態の集合を表す。次の各問いに答えよ： ```tikz \usepackage{tikz} \usetikzlibrary{positioning} \begin{document} \begin{tikzpicture}[node distance=1cm and 1cm] % Nodes \node (q0) [circle, draw] {$q_0$}; \node (q1) [circle, draw, above right=of q0] {$q_1$}; % q1在右上角 \node (q3) [circle, draw, right=of q0] {$q_3$}; % q3在正右方 \node (q6) [circle, draw, below right=of q0] {$q_6$}; % q6在右下角 \node (q2) [circle, draw, double, right=of q1] {$q_2$}; \node (q4) [circle, draw, right=of q3] {$q_4$}; \node (q5) [circle, draw, double, right=of q4] {$q_5$}; \node (q7) [circle, draw, right=of q6] {$q_7$}; \node (q8) [circle, draw, double, right=of q7] {$q_8$}; % Edges \draw[->] (-0.5, 0) -- (q0);% Start state arrow \draw[->] (q0) to[loop above] node {a, d} (); \draw[->] (q0) to node[midway, above left] {a} (q1); \draw[->] (q0) to node[midway, above] {a} (q3); \draw[->] (q0) to node[midway, below left] {d} (q6); \draw[->] (q1) to node[midway, above] {d} (q2); \draw[->] (q3) to node[midway, above] {d} (q4); \draw[->] (q4) to node[midway, above] {d} (q5); \draw[->] (q6) to node[midway, above] {a} (q7); \draw[->] (q7) to node[midway, above] {d} (q8); \end{tikzpicture} \end{document} ``` 1. $L$ を受理する状態数4の非決定性有限オートマトンの状態遷移図を示せ。 2. $L$ を表す正規表現を示せ。 3. $L$ を受理する状態数4の決定性有限オートマトンの状態遷移図を示せ。 4. $L$ を受理する決定性有限オートマトンの状態数は必ず4以上であることを証明せよ。