形式言語の理論 5. 文脈依存言語

Chomsky階層の４言語族 句構造 文脈依存言語 文脈自由言語 正規言語 句構造とは， (1) N,  は N =  なる空でない有限集合． (2) P は    の形をした記号列の有限集合 ただし，  N で， ,   (N  )* かつ  は少なくとも１個の N の要素を含む． (3) SN．

5.1. 文脈依存文法とその標準形 文脈依存文法 定理5.1 文脈依存文法 ⇔ 単調文法 補題5.2 単調文法の次数は下げられる 定理5.1 文脈依存文法　⇔　単調文法 補題5.2 単調文法の次数は下げられる 補題5.3 任意の単調文法は次数２の単調文法に変形できる 定理5.4 任意の文脈依存文法は線形有界文法に変形できる

文脈依存文法 句構造文法 G = (N, , P, S ) のすべての生成規則が  A    (, ,   (N  )*,   , AN ) の形をしているとき，G は文脈依存文法とよばれる． 文脈依存文法（context-sensitive grammar: CSG）は，  を生成しないことに注意． 例5.1 L = {anbncn | n  1} を生成する CSG． S  a S B C a B  a b S  a B C b B  b b C B  A B b C  b c A B  A C c C  c c A C  B C

単調文法 句構造文法 G = (N, , P, S ) が単調であるとは， G のすべての生成規則    P が | |  | | を 満たすことをいう． 単調文法と文脈依存文法は表現力が同等である． 例5.1 の は単調文法である．

定理5.1　（文脈依存文法⇔単調文法） 任意の言語 L   * に対して，L が文脈依存言語であるための必要十分条件は，L が単調文法で生成されることである． ［ 証明 ］ 文脈依存文法は単調文法なので，必要性は明らか． 任意の単調文法に対して，等価な文脈依存文法が存在することを示せばよい．

補題5.2　（単調文法の次数は下げられる） 任意の次数 n (n  3) の単調文法 G に対して，G と等価な次数 n1 の単調文法 G が存在する． 次数：生成規則のうちの右辺の最大長 まず，任意の単調文法 G に対して，G と等価な単調文法 G = (N, , P, S ) で，すべての生成規則が 　A  a (a   , AN ) もしくは    (,   N+ ) の形をしているものが存在することに注意．

補題5.2の証明 A  a の形をしていない生成規則には非終端記号しか現れないと考えて良い．    を G の生成規則とする． | |  2 の場合はそのまま．それ以外の場合には，  = A ,  = BCD (A, B, C, D  N, ,   N*) とおける  =  の場合    ( = E )の場合 A  A1 A2 A1  B C A2  D  A E  A E A  B E   C D 

補題5.3 （任意の単調文法は次数２の単調文法に変形できる） 任意の単調文法 G に対して，G と等価な 次数 2 の単調文法が存在する． ［ 証明 ］ 　補題5.2 を繰り返して得られる G が補題5.3を満たすのは明らか．

定理5.1の証明 補題5.3より，G は次数2の単調文法としてよい． A B  C D (A  C かつ B  D) の形をした生成規則を次のように置き換えて新たな単調文法 G とする． A B  A B A B  A D A D  C D G は文脈依存文法であり，かつ G と等価．

例5.2 単調文法 G = ({S, B, C}, {a, b, c}, P, S) S  a S B C S  a B C C B  B C a B  a b b B  b b b C  b c c C  c c 例5.1の文脈依存文法はこの生成規則の C B  B C を書き換えたものである．

線形有界（黒田標準形） 文脈依存文法 G = (N, , P, S ) が線形有界であるとは，P 中のすべての生成規則が次のいずれかの形をしていることをいう． ただし，A, B, C, D  N  {S} である． S  S A S  A A  B A B  C D 単調文法と同一視していることに注意

定理5.4 （任意の文脈依存文法は線形有界文法に変形できる） 任意の文脈依存文法 G に対し，G と等価な線形有界文法 G が存在する． 線形有界文法の性質 線形有界文法においては，S  S A の形以外の生成規則は導出される記号列の長さを変えない． 開始記号 S を右辺にもつ生成規則は， S  S A に限られる． 任意の線形有界文法 G = (N, , P, S ) と任意の ,   (N  )* に対して，S G  S ならば，  =  かつ   (N  {S})* である． *

5.2 線形有界オートマトン 線形有界オートマトン 補題5.6 文脈依存言語 ⇒ 線形有界オートマトン 補題5.7 線形有界オートマトン ⇒ 文脈依存言語 定理5.8 文脈依存言語 ⇔ 線形有界オートマトン

線形有界オートマトン ¢ $ w 有限制御部 1テープ非決定性Turing機械 M = (Q, , , , q0, F) (1) {¢, $}   , (2) 任意の p, q  Q に対し，(q, a, X)   (p, ¢) ならば， a = ¢ かつ X = R， (3) 任意の p, q  Q に対し，(q, a, X)   (p, $) ならば， a = $ かつ X = L． ¢ $ w 有限制御部

補題5.6 （文脈依存言語 ⇒ 線形有界オートマトン） 任意の文脈依存言語 L   * に対して，L を受理する線形有界オートマトンが存在する． 証明の手順 L(G) = L となる G をとる． この G に基づき，（天下り的に）線形有界オートマトン M = (Q,  , , , q0, {qf}) を次のようにつくる． Q = {q0, qf, s0, s1, r0, r1, r2}{sA | ABCDP }   =  {¢, $}  = N    L(G) = L(M) を証明する．

証明 ¢ $ w r0 q0 s0 r1 sA s1 r2 qf a / a,R ¢ / ¢,R ¢ / ¢,R S / S,L C / A,R sA s1 S / ¢,R A / S,R D / B,R $ / $,L r2 qf ¢ / ¢,R $ / $,L A / A,{L,R} B / A,R

補題5.7 （線形有界オートマトン ⇒ 文脈依存言語） 任意の線形有界オートマトン M = (Q, , , , q0, F) に対して，L(M) {} は文脈依存言語である． 証明の手順 M に基づき，（天下り的に）文脈依存文法 G = (N, , P, S ) をつくる． L(G) = L(M) {} を証明する．

導出の仕組み (5.20) と (5.21) の規則から，ある語 w = a1a2・・・an に対応する初期様相を表す文形式 a1, q0¢a1a2, a2 ・・・ an, an$ を生成する． (5.22) と (5.23) の生成規則を繰り返し適用することで，非終端記号a1,   の第２項の部分を使って M の計算過程を模倣しながら導出を続ける． 模倣の過程で，M が最終状態に達するならば，非酒単記号a1,  q  が現れるので，(5.24) を用いて終端記号 a に置き換える． 後は，(5.25) を繰り返し適用し，すべての非終端記号を終端記号に置き換え，語w = a1a2・・・an を得る．

定理5.8と系5.9 L   * が文脈依存言語であるための必要十分条件は，L = L(M) なる線形有界オートマトン M が存在することである． 系5.9　（→定理5.13の証明に関係） CSL = NSPACE(n) 消去可能文脈依存文法 次の生成規則からなる文法 G は，消去可能文脈依存文法という．  A    (, ,   (N  )*, AN ) 消去可能文脈依存文法は句構造と同等の生成能力をもつ．

5.3 文脈依存言語の性質 定理5.10 定理5.11 定理5.12 定理5.13 補題5.14 文脈依存言語族は和と連接について閉じている 文脈依存言語族は正閉包について閉じている 定理5.12 文脈依存言語族は積について閉じている 定理5.13 任意の文脈依存言語L   * に対して， *Lの補集合は文脈依存言語である 補題5.14 任意の s (n)  log n に対して， NSPACE( s (n) ) = co-NSPACE( s (n) )である

定理5.10 （文脈依存言語族は和と連接について閉じている） L1, L2   * を任意の文脈依存言語とする． (1) L1 と L2 の和 L1  L2 は文脈依存言語である． (2) L1 と L2 の連接 L1・ L2 は文脈依存言語である． GL1  L2 = (N1N2 {S}, , P1 P2 {SS1, SS2}, S) GL1 ・ L2 = (N1N2 {S}, , P1 P2 {SS1S2}, S) Gi の生成規則の左辺に終端記号が現れないと仮定

定理5.11 （文脈依存言語族は正閉包について閉じている） 任意の文脈依存言語L   * に対して， L の正閉包L+ は文脈依存言語である． GL+ = (N∪N∪{S+, X}, , P+, S+) N∩N =  となる G のコピー G = (N, , P, S ) N = { A | AN } P = {     |     P かつ  ,   は  ,  の 　　　　　　　　非終端記号 A を A で置き換えたもの } P+ = P∪P∪ {S+S, XS, S+SX, X SS+ }

定理5.12 （文脈依存言語族は積について閉じている） 任意の文脈依存言語 L1, L2   * に対して， L1 と L2 の積 L1∩L2 は文脈依存言語である． [証明] Li (i = 1, 2) を受理する線形有界オートマトンを Mi = ( Qi, , i , i , q0i, Fi ) とする． この Mi から，線形有界オートマトン ML1∩L2 を構築する． ¢ $ a b a b b a b c ¢ $ a b a b b a b c

定理5.13 （文脈依存言語の補集合も文脈依存言語である） 任意の文脈依存言語L   * に対して，  *Lの補集合は文脈依存言語である． [証明] 系5.9 と補題5.14 による． 系5.9　CSL = NSPACE(n) 補題5.14 NSPACE( s (n) ) = co-NSPACE( s (n) ) CSL = co-CSL

補題5.14 （ NSPACE( s (n) ) = co-NSPACE( s (n) ) ） 任意の s(n)  log n に対して， NSPACE( s(n) ) = co-NSPACE( s(n) )である [証明] 任意の s(n) 領域有界Turing機械M に対して， *L(M) を受理する s(n) 領域有界Turing機械M が存在すること を証明する． 線形有界オートマトンは領域有界Turing機械

5.4 言語族の階層 Chomsky階層の４言語族 RGL  CFL  CSL  FSL 句構造言語（0型） 文脈依存言語（1型） 文脈自由言語（2型） 正規言語（3型） FSL CSL CFL RGL RGL  CFL  CSL  FSL 補題5.15 補題5.16 補題5.17 補題5.18

補題5.15 と 補題5.16 補題5.15 RGL  CFL ［証明］ 言語 L = { anbn | n  1 } を・・・ 生成する文脈自由文法はあるので，文脈自由言語 受理する有限オートマトンはないので， 正規言語ではない 補題5.16 CFL  CSL ［証明］ 言語L = { anbncn | n  1 } を・・・ 生成する文脈依存文法はあるので，文脈依存言語 生成する文脈自由文法はないので， 文脈自由言語ではない

任意の x に対し，xL かどうか判定できる 補題5.17 と 補題5.18 補題5.17 すべての文脈依存言語は帰納的である． 補題5.18 文脈依存言語でない帰納的集合が存在する． ［証明］ L = { xi | xi  L(Gi) } を使った対角線論法により 証明する． 任意の x に対し，xL かどうか判定できる

定理5.19 （RGL  CFL  CSL  FSL） RGL  CFL  CSL  FSL ［証明］ 補題5.15, 5.16, 5.17, 5.18 による． 言語族 受理系 生成系 FSL（句構造） Turing機械 句構造文法 CSL（文脈依存） 線形有界オートマトン 文脈依存文法 CFL（文脈自由） プッシュダウン・オートマトン 文脈自由文法 RGL（正規） 有限オートマトン 正規文法