形式言語の理論
5. 文脈依存言語
Chomsky階層の4言語族




句構造
文脈依存言語
文脈自由言語
正規言語
句構造とは,
(1) N,  は N =  なる空でない有限集合.
(2) P は    の形をした記号列の有限集合
ただし,  N で, ,   (N  )* かつ
 は少なくとも1個の N の要素を含む.
(3) SN.
5.1. 文脈依存文法とその標準形


文脈依存文法
定理5.1
文脈依存文法 ⇔ 単調文法

補題5.2
単調文法の次数は下げられる

補題5.3
任意の単調文法は次数2の単調文法に変形できる

定理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
(任意の単調文法は次数2の単調文法に変形できる)

任意の単調文法 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,   の第2項の部分を使って 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階層の4言語族
句構造言語(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(正規)
有限オートマトン
正規文法
ダウンロード

Document