2014-07-20

日記

 昼頃起きて昼は冷凍食品、夜は街に出てカレーを食べた。形式言語の勉強がだいたい終わった。次は離散数学と計算量理論かなぁ。

雑記 [IS, CYK]

<所属判定問題 CYK法>
・Gを文脈自由文法とする。入力としてw∈T^*が与えられたとき、w∈L(G)であるかどうかを判定するアルゴリズムがある。
証明:
 Gについて、A⇒^*εとなるような生成規則を取り除いていけばε∈L(G)かどうかを判定できる。さらにεがあるなら、L(G)-{ε}を生成するChomsky標準形の文脈自由文法G'を作ることができる。Chomsky標準形の生成規則を前提として、次のアルゴリズムによってw=x_1,...,x_nがw∈L(G')かどうかを判定する。

 for i = 1 to n
  V_i1 <- {A | A -> a∈P, xi = a}
  next
 for j = 2 to n //j=3
    for i = 1 to n-j+1 //i=1
      V_ij = φ
      for k = 1 to j-1 //k=1
        V_ij = V_ij ∪
            {A | A -> BC∈P, B∈V_ik, C∈V_{i+k,j-k}}/V_11,V_22
      next
    next
  next

これは動的計画法の一種。
上記のようにfor文を書くとわかりづらいが、実質は以下の表のようになっている。
生成規則を
 S -> AB | BC
 A -> BA | a
 B -> CC | b
 C -> AB | a
とする。w=baabaとして、上記の規則から生成されるか調べる。
[j]
5 S,A,C
4  *  | S,A,C
3  *  |  B  |  B  
2 S,A |  B  | S,C | S,A     
1  B  | A,C | A,C |  B  | A,C
   b  |  a  |  a  |  b  |  a
   1     2     3     4     5  [i]


■1-0
まずbaabaに対応する変数に変える。左の数字はi-jに対応。
・1-1~5-1 baaba->B[AC][AC]B[AC]
 baabaに対応する変数に戻す。

■2-0
 隣接する2変数を1変数に縮めようと試みる。1,2文字目から4,5文字目までの4パターンを考える。
・2-1 B[AC][AC]B[AC]->[AS][AC]B[AC]
 1,2文字目のBAかBCを戻す。BA->AかBC->Sになる。
・2-2 B[AC][AC]B[AC]->BBB[AC]
 2,3文字目のAAかACかCCを戻す。CC->Bになる。
・2-3 B[AC][AC]B[AC]->B[AC][SC][AC]
 3,4文字目のABかCBを戻す。AB->S,Cになる。
・2-4 B[AC][AC]B[AC]->B[AC][AC][AS]
 4,5文字目のBAかBCを戻す。BA->AかBC->Sになる。

■3-0
 2-0で2変数->1変数にしたものと、その隣接の1変数の組み合わせについて考える。
・3-1 [AS][AC]B[AC]->*、 BBB[AC]->*
 候補になるのは初期1,2文字目を戻した[AS]と初期3文字目の[AC]だが、[AS][AC]を生成する規則はない。
 もうひとつの候補は初期1文字目のBと初期2,3文字目を戻したBだが、BBを生成する規則はない。
・3-2 BBB[AC]->*、 B[AC][SC][AC]->BB[AC]
 候補になるのは初期2,3文字目を戻したBと初期4文字目のBだが、BBを生成する規則はない。
 もうひとつの候補は初期2文字目の[AC]と初期3,4文字目を戻した[SC]であり、[AC][SC]を生成するのはBである。
・3-3 B[AC][SC][AC]->B[AC]B、 B[AC][AC][AS]->*
 候補になるのは初期3,4文字目を戻した[SC]と初期5文字目の[AC]であり、[SC][AC]を生成する変数はBである。
 もうひとつの候補は初期3文字目の[AC]と初期4,5文字目を戻した[AS]だが、[AC][SC]を生成する規則はない。

■4-0
 ここから少しわかりづらい。連続した4変数を生成するような1変数の候補を考えることになる。たとえば[1文字目]と[2-4文字目の圧縮]を生成する規則があるか、[1-2文字目の圧縮]と[3-4文字目の圧縮]を生成する規則があるか、[1-3文字目の圧縮]と[4文字目]を生成する規則があるか、の3通りを考える。
・4-1 BB[AC]->*、 [AS][SC][AC]->*、 *->*
 [1][2-4]も[1-2][3-4]も[1-3][4]も生成する規則がない。
・4-2 B[AC]B->B[SC]、 BB[AS]->BA、 BB[AC]->BA
 [2][3-5]も[2-3][4-5]も[2-4][5]も生成する規則がある。

■5-0
 4-0と同様に候補を探す。5-1だけであり、[1][2-5],[1-2][3-5],[1-3][4-5],[1-4][5]の4通り考えればよい。
・5-1 B[SAC]->[AS]、 [AS]B->[SC]、 *->*、 *->*
 [1][2-5]か[1-2][3-5]でSが出てくることがわかる。

広告を非表示にする