形式言語の理論

形式言語の理論
5. 文脈依存言語
Chomsky階層の４言語族




句構造
文脈依存言語
文脈自由言語
正規言語
句構造とは，
(1) N,  は N =  なる空でない有限集合．
(2) P は    の形をした記号列の有限集合
ただし，  N で， ,   (N  )* かつ
 は少なくとも１個の N の要素を含む．
(3) SN．
5.1. 文脈依存文法とその標準形


文脈依存文法
定理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aSBC
aBab
SaBC
bBbb
CB  AB
bCbc
AB  AC
cCcc
AC  BC
単調文法

句構造文法 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*)
とおける
 =  の場合
A  A1 A2
A1  B C
A2  D 
   ( = E )の場合
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aSBC
SaBC
CBBC
aBab
bBbb
bCbc
cCcc
例5.1の文脈依存文法はこの生成規則の
C B  B C を書き換えたものである．
線形有界（黒田標準形）

文脈依存文法 G = (N, , P, S ) が線形有界で
あるとは，P 中のすべての生成規則が次のい
ずれかの形をしていることをいう．
ただし，A, B, C, D  N  {S} である．
SSA
SA
A B
AB CD
単調文法と同一視していることに注意
定理5.4
（任意の文脈依存文法は線形有界文法に変形できる）

任意の文脈依存文法 G に対し，G と等価な
線形有界文法 G が存在する．

線形有界文法の性質



線形有界文法においては，S  S A の形以外の
生成規則は導出される記号列の長さを変えない．
開始記号 S を右辺にもつ生成規則は，
S  S A に限られる．
任意の線形有界文法 G = (N, , P, S ) と任意の
*  S ならば，
,   (N  )* に対して，S 
G
 =  かつ   (N  {S})* である．
5.2 線形有界オートマトン

線形有界オートマトン

補題5.6
文脈依存言語 ⇒ 線形有界オートマトン

補題5.7
線形有界オートマトン ⇒ 文脈依存言語

定理5.8
文脈依存言語 ⇔ 線形有界オートマトン
線形有界オートマトン

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
$
a / a,R
r0
q0
¢ / ¢,R
sA
s0
$ / $,L
C / A,R
s1
D / B,R
¢ / ¢,R $ / $,L
A / A,{L,R} B / A,R
¢ / ¢,R
r1
S / ¢,R
r2
$ / $,L
qf
補題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.13


文脈依存言語族は正閉包について閉じている
定理5.12


文脈依存言語族は和と連接について閉じている
任意の文脈依存言語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+ は文脈依存言語である．
N∩N =  となる G のコピー G = (N, , P, S )

GL+ = (N∪N∪{S+, X}, , 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
¢
$
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階層の４言語族
句構造言語（0型）
文脈依存言語（1型）
FSL
CSL
文脈自由言語（2型） CFL
正規言語（3型） 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 } を・・・
 生成する文脈依存文法はあるので，文脈依存言語
 生成する文脈自由文法はないので，
文脈自由言語ではない
補題5.17 と補題5.18

補題5.17
すべての文脈依存言語は帰納的である．
任意の x に対し，xL かどうか判定できる
補題5.18
文脈依存言語でない帰納的集合が存在する．
［証明］
L = { xi | xi  L(Gi) } を使った対角線論法により
証明する．

定理5.19 （RGL  CFL  CSL  FSL）
RGL  CFL  CSL  FSL
［証明］
補題5.15, 5.16, 5.17, 5.18 による．

言語族
受理系
生成系
FSL（句構造）
Turing機械
句構造文法
CSL（文脈依存）
線形有界オートマトン
文脈依存文法
CFL（文脈自由）
プッシュダウン・オートマトン
文脈自由文法
RGL（正規）
有限オートマトン
正規文法

Download Report