1. Qiita
  2. 投稿
  3. ズンドコキヨシ

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

  • 14
    いいね
  • 9
    コメント

「ズン」「ドコ」「ドコキヨシ」の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番までしか理解していない.

Comments Loading...