R06-C-問1

問1

アルファベット $\Sigma =\{a,d\}$ 上の言語 $L$ を以下のように定義する：
$L=\{w\in {\Sigma }^{\ast }\mid w\in \{xad,xadd,xdad\}\text{ for some }x\in {\Sigma }^{\ast }\}$以下の図は $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$ の状態の集合、アルファベット、遷移関数、初期状態、受理状態の集合を表す。次の各問いに答えよ：

\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以上であることを証明せよ。