2016年度ズンドコ学園入試問題

「ズン」「ドコ」「ドコキヨシ」の3つの語を持つ言語を考える．開始記号および非終端記号$S$，非終端記号$A,B,C,D$を用いると，状態遷移の定義$d$およびその生起確率$P(d)$は以下のように示される．

\begin{eqnarray}
P(&S & \rightarrow & ズン A & ) = \frac{1}{2} \\
P(&S & \rightarrow & ドコ S & ) = \frac{1}{2} \\
\\
P(&A & \rightarrow & ズン B & ) = \frac{1}{2} \\
P(&A & \rightarrow & ドコ S & ) = \frac{1}{2} \\
\\
P(&B & \rightarrow & ズン C & ) = \frac{1}{2} \\
P(&B & \rightarrow & ドコ S & ) = \frac{1}{2} \\
\\
P(&C & \rightarrow & ズン D & ) = \frac{1}{2} \\
P(&C & \rightarrow & ドコ S & ) = \frac{1}{2} \\
\\
P(&D & \rightarrow & \mbox{ドコキヨシ} & ) = \frac{1}{2} \\
P(&D & \rightarrow & ズン D & ) = \frac{1}{2} \\
\end{eqnarray}

このとき，以下の問に答えよ．途中経過も併せて示せ．

1. 状態遷移図を示せ．
2. 言語が終端するまでの平均状態遷移回数$N$および平均文字列長$L$を求めよ．
3. 言語が終端するまでの状態遷移回数が$n$になる確率$P_n$を求めよ．
   但し$n$は$n\ge5$を満たす自然数とする．

なお問題作成者は2番までしか理解していない．