形式言語

言語の認知科学第 7 回配布資料
浅川伸一
2009 年 11 月 18 日
1
言語に関与する遺伝子
発話と言語の異常には，遺伝学的な基盤が関与している可能性が示唆され
ているが，家系図は複雑であり特定の遺伝子を推測するのは難しい。
1990 年に KE としてだけ知られるイギリスの家系について発表された。KE
家族 3 世代のうち約半数が，発話のための筋の協調運動ができないという発
話失行を持っていた。彼らが話す言葉は，一般人にも家族の他のメンバーに
も理解不能であった。実際，彼らは話し言葉を補うために信号を使っていた
らしい。KE は発話失行に加えて，文法を含む広い範囲で障害があり，他の
障害を持たない家族に比べて低い IQ を示したらしい。脳画像によって，こ
の障害を持つ者は，尾状核とブローカ野がいくらか小さいことがわかったと
言うことである (尾状核の位置を図 1(Pinel, 2005) に示した)。
図 1: 尾状核の位置
以前の研究によって明らかになっていたことは，言語には複数の遺伝子が
関与するらしいということであったが，KE 家族の遺伝子パターンは単一遺
伝子の変異によるものと一致していたらしい。この遺伝子は，脳の構造と顔
面下部の筋の協調運動に影響を与えることが明らかとなった。変異を持つ遺
1
伝子は FOXP2 であることが同定されたらしい。この遺伝子は，他の遺伝子
を働かせたり，止めたりする転写因子をコードしているらしい。
FOXP2 を言語遺伝子と呼ぶのはふさわしくないが，誰しも両親から受け
継いだ 2 組の FOXP2 遺伝子を持っているらしい。重度な言語障害を生じる
ためには，両親のどちらか一方に変異遺伝子があれば十分であるらしい。
FOXP2 はマウスやチンパンジーでも見つかっている。ヒト型の FOXP2
タンパク質とチンパンジーなどの霊長類の型とは，わずか 2 個のアミノ酸の
違いしかないらしい。ヒトとチンパンジーが枝分かれしたのは 600 万年前で
あるが，FOXP2 遺伝子の変異が起こったのは，わずか 10 万年前のことだと
推定されている。その後の爆発的な文明の進化を考えると感慨深い気もする
(^^)
2
言語の統計
言語の中でもっとも簡単に調べられるのは頻度（何回出現したか）データ
である。図 1 に「不思議の国のアリス」に出現する文字の頻度を示した。表
表 1: 「不思議の国のアリス」に出現する各文字の頻度
SP 24639 d 4931 f 2001 ; 194
e
13575
l
4716
p
1524
x
148
t
a
10688
8791
u
’
3468
2871
b
k
1475
1158
j
”
146
113
o
i
h
8146
7514
7374
w
g
,
2675
2531
2418
.
v
!
989
846
450
z
*
)
78
60
56
n
s
r
7016
6500
5438
c
y
m
2399
2262
2107
&
q
?
233
209
202
(
56
中の SP は空白を表している。図から明らかなとおりもっとも出現頻度の高
い文字は空白であり，その次が e である。
英語の文字列の特徴を表すものとして，単独文字の出現頻度だけではなく，
2 文字，3 文字が隣接して生じる頻度を問題にする。これは共起関係と呼ば
れ，2-gram, 3-gram などと表す。同じく「不思議の国のアリス」から 2-gram,
3-gram を調べたものを以下に記す。この表は，t の後に e が来た回数が 755
回であったことを表している。おのおのの n に対して n-gram を作成すれば，
英単語の綴りの特徴が見えてくると考えて良いであろう。
一方，日本語の場合は文字数が 8000 文字を越えることから 2 次の相関表
を作るだけでも大変である。宮沢賢治の「銀河鉄道の夜」から文節区切りソ
2
表 2: 「不思議の国のアリス」にみられる 2 次の共起関係
SP
e
t
a
o
SP
e
4487
337
484
3957
348
3005
775
1279
44
t
a
2578
616
755
364
1167
259
1008
3
o
i
1152
383
48
191
425
1325
25
32
445
174
フト mecab を使って一単語を切り出し，そのの頻度をとってきたのが，表 3
である。
表 3: 「銀河鉄道の夜」にみられる単語の頻度情報
の
1276
。 1120
、
が
533
451
ジョバンニ
309
」 293
な
まし
987
948
と
866
780
693
「
693
625
よう
は
を
565
た
て
に
》
《
い
189
185
181
181
293
237
215
から
209
209
その
し
ん
156
144
か
205
へ
126
も
で
です
だ
166
161
157
表 4 では，太宰治「人間失格」の中から，2 次の相関の高い単語の組み合
わせを表示したものである。この表をみると，
（は，
、）の組み合わせが一番多
く 1.51% を占めていることが分かる。日本語の格助詞で主格を表す格助詞の
後に読点（、）が来ることが多いことが分かる。
3
マルコフ過程 Markov process
時刻 t に偶然量のとる値の分布が過去の (t 以前の) 以前任意の 1 時刻 t0 に
とった値だけに関係し，t0 以前の履歴には影響されない確率過程。正確には，
確率過程 Xt(t∈T ) において，T 内の時刻 s1 < s2 < s3 < · · · < sn < t を任
意に選んだとき，X s1 , X s2 , · · · , X sn を与えたときの Xt の条件付き確率が，
X sn だけをあたえたときの Xt の条件付き確率に等しいとき，{Xt }(t ∈ T )
をマルコフ過程という。マルコフ過程が与えられたとき，時刻 s で Xs の値を
3
表 4: 「人間失格」にみられる単語の共起頻度情報 (%)
は,、 725 (1.51)
た,。 591 (1.23)
て,、 406 (0.84)
まし, た
、, 自分
365 (0.76)
363 (0.75)
でし, た
313 (0.65)
自分, は 290 (0.60)
が,、 279 (0.58
し, て
。, 278 (0.57
268 (0.55
て, い
で,、 153 (0.31)
226 (0.47)
も,、 219 (0.45)
て, いる 214 (0.44)
に,、 191 (0.39)
、, その
190 (0.39)
自分, の
178 (0.37)
176 (0.36)
169 (0.35)
た, の
に, は
」, の, です
166 (0.34)
157 (0.32)
です,。 148 (0.30)
」,「
131 (0.27)
、, それ
123 (0.25)
と,、 120 (0.25)
の, でし 116 (0.24)
。,「
自分, に
ませ, ん
よう, な
111 (0.23)
107 (0.22)
104 (0.21)
98 (0.20)
あたえたきに，時刻 t(≥ s) における Xt が領域 A に落ちる条件付き確率を推
移確率 transition probability P (s, x; t, A)(x ∈ S, A ∈ B(S), S は Xt の値域
といい，正確には次のように定義する。
1. P (s, x; t, A) は x について B(S) 可測， A については確率分布である。
2. P (s, x; s, A) = 1(x ∈ A), 0(x ∈
/ A)
3. 確率 1 で P (Xt ∈ A|Xs = xs ) = P (s, xs ; t, A).
推移確率は確率保存の関係式であるチャップマン・コルモゴロフ方程式 Chapman–
Kolmogorov equation
∫
P (s, x, µ, A) =
P (s, x; t, dy)P (t, y, µ, A)
(1)
s
を，x について Xγ の分布に関し測度 0 の点を除いて満足する。逆にこの方
程式と上の 3 条件を満たす関数 P (s, x; t, A) があたえられ，初期時刻 t = 0
における X0 の分布 F が任意に指定されたとき，P (s, x; t, A) を推移確率と
し，F を初期分布 (ΦX0 ) とするマルコフ過程 {Xt }(t∈T ) が存在する。推移
確率が t と s との差だけに関係して，P (s, x; t, A) = P (t − s, x; A) と表せる
とき，このマルコフ過程は時間的に一様であるという。また実数値（または
Rn 値）マルコフ過程において，推移確率が位置のずれによって変わらないと
き，すなわち集合 A を x だけずらせたもの {y − x|y ∈ A} を A − x と書い
て，P (s, x; t, A) = P (s, t; A − x) で表せるとき，このマルコフ過程は空間的
に一様であるという。空間的に一様なマルコフ過程は加法過程であり，加法
過程 {Xt − X0 }(t∈T ) を初期値 X0 だけずらせた {Xt − X0 }(t∈T ) は空間的に
一様なマルコフ過程である。Xt の値域 S が加算集合であるマルコフ過程を
マルコフ連鎖という。また確率 1 で見本過程が連続なマルコフ過程を拡散過
程という。
4
3.1
マルコフ連鎖
マルコフ過程 {Xt }t∈T のとる値が有限個または加算個のときマルコフ連
鎖という。ときに離散的な時間助変数のマルコフ過程をマルコフ連鎖という
こともある。以下，時間的に一様な場合を考える。Xt の値域を S とする。
Xs = X のとき t > 0 に対し Xs+t = y となる条件付き確率
pt (x, y) = P (Xs+t = y|Xs = x)
(2)
をマルコフ連鎖の推移確率 transition probability という。これは次の 2 条
件を満たす。
1.
Pt (x, y) ≥ 0,
∑
pt (x, y) = 1,
y∈S
2.
pt+s (x, y) =
∑
pt (x, z)ps (z, y).
z∈S
2 をチャップマン・コルモゴロフ方程式という。逆にこの 2 条件を満たす
{pt (x, y)} があれば，これを推移確率とするマルコフ連鎖が存在し，初期分
布を与えればただ１つに定まる。とくに確率行列 A = (a(x, y)), すなわち
∑
a(x, y) ≥ 0, y∈S a(x, y) = 1 となる行列があるとき，pn (x, y) = An (n =
1, 2, · · ·) とおけば，pn (x, y) は上の 2 条件をみたし，これを推移確率とする
離散時間助変数のマルコフ連鎖が存在する。Xt が N 次元格子点上を動き，
a(x, y) が y − x だけの関数 a(x, y) = b(y − x) となるとき，これから構成さ
れるマルコフ連鎖をランダムウォークという。
岩波，理化学事典より
4
言語の有限オートマトン理論
言語の形式的モデルにはいくつかある。そのうち有限オートマトン理論は
最も単純なものであり，マルコフモデルの延長上にあると考えて良い (長尾
真, 1996)。
たとえば英語では，主語が複数形ならば動詞は対応する複数形でなければ
ならないし，ドイツ語やフランス語では，格，性，などと一致する必要があ
る。また，インドヨーロッパ語族系のほとんどの言語は SVO 型であるのに
対し，ツングースモンゴル語族系の日本語，韓国語，モンゴル語，トルコ語
などは SOV 型である。こうした文の並び方の規則を syntax（統語論） と呼
ぶ。文の構造に関する規則の集合を grammar(文法) と呼ぶ。
5
文の基本的な考え方は，隣接する単語同士が持つべき制約である。すなわ
ちある単語が発話されたら，次にどのような単語が続きうるかを明らかにす
ることが言語学者の仕事ということになる。これを同時確率，条件付き確率
で表現したモデルがマルコフモデルである。
マルコフモデルは，文の生じやすさを確率によって表現したものというこ
とができる。ある言語の文として許されるもの，発生しうるものはすべて同等
に取り扱うという立場に立てば，マルコフモデルでの確率という概念のかわ
りに，可能かどうかという 2 値の確率をもったモデルを作ることになる。この
ようなモデルを有限オートマトンモデル
finite automata model
と呼ぶ。
有限オートマトンモデルで，ある与えられた文字列がある言語の文となっ
ているかどうかを検定したいという場合を考える。その文字列をモデルの初
期状態 initial state に対して与えると，入ってくる文字列の各文字と内
部状態の組み合わせで，次に移るべき状態が決定され，有限オートマトンの
状態推移 state trasition が行われる。文字列を最後まで入れ終わった
状態でオートマトンがあらかじめ定められている最終状態 final state と
なっている場合，この文字列は受理 accept されたという。このようにし
て文字列がその言語に属するかどうかが判別できる。このようなオートマト
ンは次のように定式化でき，
1. 状態の集合を K = {q0 , q1 , · · · , qn } とする。qi は状態で，n は有限で
ある。
2. 入力文字列の集合を S とする。S は有限である。
3. 状態推移関数の集合を P とする。P は有限である。
4. 初期状態を q0 とする。q0 ∈ K である。
5. 最終状態の集合を F とする。F ⊂ K である。
このような有限オートマトンを
M =< K, S, P, q0 , F >
(3)
と表記する。M がある状態 qi にあるとき，入力 a が与えられたら，状態 qi
に移行する場合，
δ(qi , a) = qi
(4)
と書き，状態推移関数という。P はこのような関数の集合である。この状
態推移関数に対応して，次の図 2
簡単のため，文字 a が任意個並んだ文字を受理する有限オートマトンを
作ってみる。これは
S ∗ = λ + a + aa + aaa + · · · + an + · · ·
6
(5)
a
qi
qj
図 2: 状態遷移図
a
q0
図 3: 状態遷移図その２
という集合を受理するものである。これは図 3 に示すように これは１つの状
態をもつオートマトンで実現できる。これを詳しく書くと，
K
S
P
= {q0 }
= {a}
= {δ(q0 , a) = q0 }
初期状態
= 最終状態 = q0
(6)
英語の論文は多くの場合次のような形をしている。
N + PREP N +
(7)
ここに N は名詞であり，N + は N が１つ以上並んでいることを表している。
PREP は前置詞であり，of, at, for, などが入る。このような名詞句を受理す
るオートマトンは図 4 と書ける。このオートマトンを詳しく書くと
N
q0
N
q1
N
PREP
q2
N
q3
図 4: 英語の論文のタイトルを表すオートマトン
7
K = {q0 , q1 , q2 , q3 }
S = {N, PREP}
P = {δ(q0 , N ) = q1 , δ(q1 , N ) = q1 , δ(q1 , PREP) = q2 , δ(q2 , N ) = q3 , δ(q3 , N ) = q3 }
初期状態 = q0 , 最終状態 = q3
(8)
状態推移関数を 1 文字の入力に対する推移から，文字列 X に対する推移
に拡張しよう。すなわち，初期状態 q0 に文字列 X が入って状態が qi になっ
たとする。これを
δ(q0 , X) = qi
(9)
δ(qi , a) = qj
(10)
δ(q0 , Xa) = δ(δ(q0 , X), a) = δ(qi , a) = qj
(11)
と表現する。
であるとすると
と書くことができる。X として特別な文字列 λ(空列) をとると，
δ(qi , λ) = qi
(12)
である。二つの文字列 X, Y があって
δ(q0 , X) = q
δ(q0 , Y ) = q
}
(13)
であったとすると，X と Y とは同じクラスに属すると定義する。このとき
文字列 XZ, Y Z について
δ(q0 , XZ) = δ(q0 , Y Z) = q 0
(14)
である。ここに δ(q, Z) = q 0 とする。
以上のように有限オートマトン M の状態 q は文字列に対して 同値類
equivalent set を定義する。すなわち M を状態 q に対する文字列 X, Y
は同値関係にあるとする。この同値関係は右合同関係 right equivalent
relation であるという。すなわち X と Y とが同値関係にあれば XZ と
Y Z も同値関係にある。
アルファベット S 上の任意の文字列は M をいずれかの状態に導くから，
S ∗ は M によって M の状態の数だけ同値類に分けられる。
たとえば図 5 に示すような単純なオートマトンを考えよう。このオートマ
トンの推移関数は次のようになる。

δ(q0 , 0) = q0 , δ(q0 , 1) = q1 

δ(q1 , 0) = q1 , δ(q1 , 1) = q2


δ(q2 , 0) = q2 , δ(q2 , 1) = q0
8
(15)
0
q2
1
q0
1
1
q1
0
0
図 5: 単純なオートマトン
{0, 1} からなる任意の文字列が与えられたとき，このオートマトンが状態 q0
から出発して，どのような状態遷移を行うかをみると，0 が来たときは同一
状態にとどまり，1 がきたら次の状態に遷移することがわかる。したがって

q0 : 文字列 ω 中の 1 の数が 3 の倍数


(16)
q1 : 文字列 ω 中の 1 の数が 3 の倍数+1


q2 : 文字列 ω 中の 1 の数が 3 の倍数+2
という対応関係を知ることができる。すなわち {0, 1} からなる任意の文字列
が 3 つの同値類に分類された。
逆にアルファベットのすべての文字列の集合 S ∗ が有限個の右合同関係に
よる同値類に分けられたとき，これに対応するオートマトンを作ることがで
きる。
英単語辞書の中で，ly で終わる語とそれ以外の語とを区別するオートマト
ンを考えよう。これは図 6 のように作ることができる。ly より左にはどんな
文字が来ても良いが，l がきたときは次が y であるかどうかを知る必要があ
り，さらにその次に空白 t が来なくてはならないという条件がある。ly で終
わる単語は q3 に行き，そうでない単語は q4 に行って終了する。このオート
マトンの最終状態は 2 つあり F = {q3 , q4 } である。
4.1
正規言語
図 7 の左図は
{an } n = 1, 2, · · ·
9
(17)
not l and
not l and
l
l
l
q0
y
q1
q3
q2
not l ,y and
q4
図 6: ly で終わる英単語を受理する
a
q1
a
d
c
q0
q2
q3
b
b
図 7: 3 つのオートマトン
という文字列を受理する。中央の図は同様にして
{λ, ab, abab, · · · , (ab)n , · · ·} = {(ab)n |n = 0, 1, 2, · · ·}
(18)
という文字列を受理する。任意の n について an の集合 {an |n = 0, 1, 2, · · ·}
は，a∗ と表記することができるから，図 7 の左と中央の有限オートマトンは，
それぞれ
a∗ , (ab)∗
(19)
という文字列を受理することになる。図 7 の右図のオートマトンは，文字 a
と b のいずれもが任意の回数と組み合わせを受理できる。これは，
(a + b)∗
(20)
と表現できる。ここで + は a と b のどちらでも良いという意味で論理和 OR
の意味である。また，
(a + b)∗
= λ + (a + b) + (a + b)2 + (a + b)3 + · · ·
(21)
= λ + a + b + aa + ab + ba + bb + aaa + aab + aba + · · ·(22)
10
となり，a と b の任意の組み合わせができたことがわかる。
状態遷移図と受理される文字列の集合との間には、以下のような関係がある。
1. 状態遷移を二つ直列に繋いだ状態に対しては，入力文字を二つ連接し
た文字列が対応する。
2. 二つの状態遷移が同じ二つの状態の間に存在する場合には，二つの入
力文字の集合が対応する。
3. １つの状態から出て，同じ状態に戻ってくるループがある場合，その
ループをたどる文字列を x としたとき，文字列 x の閉包 ∗ が対応する。
すべてのオートマトン M はこの 3 つの場合に分解することができる。ゆえ
に，上記３つの組み合わせを合成することで M が受理する文字列の集合が
明らかとなる。(1) の場合は文字列が順序づけられた積の形となり，記号 “・”
の記号を用いて連接を表現する。一般の積の概念の拡張であり，記号 “・” は
省略が可能である。(2) に場合は和として “+” を用いる。(3) の場合は “*” と
表記する。文字列をこれらの記号によって表現した文字列の集合を正規集
合 regular set と呼ぶ。
a
q1
a
d
c
q0
q2
q3
b
b
図 8: (a + b)c(b(a + b)c)∗ a
図 8 では，状態 q0 から q1 へは文字列 (a + b) で推移し，q0 から q2 に至
るためには
(a + b)c(b((a + b)c)∗
(23)
なる文字列の集合が対応する。最終状態 q3 に至るためには
(a + b)c(b((a + b)c)∗ a
(24)
という集合が対応する。すなわちこのオートマトンが，このようにしてが与
えられれば，それが受理する正規言語を得ることができる。
5
文脈自由型文法
自然言語の文の構造を取り扱うときには，文脈自由型句構造文法を用いる。
11
図 9: トリの文法 (岡ノ谷，2004)
5.1
形式文法
有限オートマトンは，閉包の演算によってのみ無限の文を生成することが
できる。正規言語において，ある文字の影響は有限の長さにしか及ばない。す
なわちある言語のアルファベットの文字 a が現れた後，何文字離れて文字 b
が生じるかという形の依存関係は，有限オートマトンが持っている内部状態の
数以上には及ばない。ということを明白に述べたのがチョムスキーであった。
彼の説明によれば，
{an bn |n = 0, 1, 2, · · ·}
(25)
という言語では，任意の n について a が n 個並べは，続いて b が n 個並ぶ
という意味で n 個先まで依存関係が存在するが，このような任意の n を計
数し記憶するためには，有限の記憶しか持たない有限オートマトンでは不可
能であることがわかった。
チョムスキーが挙げた例に
if
s1
then s.
(26)
either
s3
or s4
(27)
the man who said that s5 is arriving tody
(28)
がある。これらの文の s1 , s2 ,· · ·,s5 には任意の長さの文を入れることができ
るので，それぞれ自分自身の文を何重にも繰り返しいれてみる。たとえば，式
(26) に対して代入を繰り返すと
if(ifs1 thens2 )thens2 if(if(ifs1 thens2 )thens2 )thens2 · · · · · ·
(29)
これは結局
(if)n s1 (then)n (thens2 )n n = 1, 2, · · ·
12
(30)
という形の文となる。この言語も正規言語ではない。
これを克服したのが，チョムスキーの文脈自由型句構造文法
context–
1
free phrase structure grammar:CFG である 。
すなわち，文は主語と述語から成り立っており，以下同様に句を分解して
行く。文の構造を全体から細部に向かっての句の形で順次処理していく。そ
の中心は句構造規則（書き換え規則）にある。以下に例を載せる。
文
→
主語 述語 (S→ SUB PRED)
(31)
主語
→
固有名詞 (SUB→ PROPN)
(32)
主語
→
名詞句 (SUB→ NP)
(33)
名詞句
→
名詞 (NP→N)
(34)
名詞句
→
冠詞 名詞 (NP→DET N)
(35)
名詞句
→
冠詞 形容詞 名詞 (NP→DET ADJ N)
(36)
述語
→
自動詞 (PRED→V1)
(37)
述語
→
自動詞 前置詞句 (PRED→VT PP)
(38)
述語
→
他動詞 名詞句 (PRED→VT NP)
(39)
前置詞句
→
前置詞 名詞句 (PP→PREP NP)
(40)
固有名詞
→
Tom, John, Shin,· · ·
(41)
名詞
→
piano, desk, boy,· · ·
(42)
動詞
→
plays, is, hit,· · ·
(43)
形容詞
→
beautiful, healthy,· · ·
(44)
冠詞
→
a, the, · · ·
(45)
ここに矢印の左辺に表れる記号を非終端記号
non-terminal symbol
といい，その集合を Vk で表す。矢印の右辺にしか現れない 非終端記号
terminal symbol といい，その集合を VT で表す。
このような文法の規則は生成規則 generation rule または書き換
え規則 rewriting rule と呼ぶ。たとえば上の第一行目は「文は主語と
述語とからなる」と読むことができる。ある文 S から出発して順次書き換え
規則を適用して文を作り出すことができる。
S
⇒
SUB PRED ⇒ PRPON PRED ⇒ PROPN VT NP
(46)
⇒
PROPN VT DET N
(47)
⇒ · · · ⇒ Tom plays the piano
(48)
∗
⇒ は左辺から右辺が導出 derive されると読む。導出の繰り返しを ⇒ で
表現し，
∗
(49)
S ⇒ Tom plays the piano.
1 文脈規定型句構造文法
context sensitive phrase structure grammaer とも呼ばれる
13
などと書く。すなわち非終端記号に書き換え規則を順次適用していって，書
き換える規則がなくなったとき，文が生成されたと考えるのである。これが
チョムスキーが提唱した生成文法 generative grammar の本質であった（こ
の辺りは前回までの復習）。
より一般的には，文法は以下の 4 つの要素によって定義される。
1. 非終端記号の集合：VN
2. 終端記号の集合：VT
3. 生成規則の集合：P
4. 初期記号：sigma σ ∈ VN
文法はこれら 4 つの要素の組によって
G =< VN , VT , P, σ >
(50)
と表される。文法 G によって初期記号 σ から生成される文の集合を L(G)
と書き，これを文法 G によって生成される言語であるという。すなわち言語
L(G) は
∗
L(G) = {w|w ∈ VT∗ , σ ⇒ w}
(51)
である。これは w は VT の要素からなる文字列で，σ から導出されるものす
べてであることを表している。VT∗ は集合 VT の任意の長さの記号列であって
空列 λ を含む。空列 λ を含まない場合は VT+ と表記する。
5.2
文法の分類
書き換え規則の一般形は，
α → β, α ∈ V + , β ∈ V ∗ , V = VN ∪ VT
(52)
と書くことができる。ただし，ここで，α には非終端記号の集合 VN 中の記
号がすくなくとも一つ含まれていなければならない。上式 52 は記号列 α が
文字列中に存在すれば，これを記号列 β に置き換えることを意味する。そし
て，α は空列を含まない，その言語に属するすべての文字列の要素であり，β
は空列を含んだ全ての文字列からなる集合である。
5.2.1
0 型文法
初期記号 σ から，この形の生成規則を順次適用していって生成される言語
L(G) を 0 型言語 という。この場合の文法を 0 型文法と呼ぶ。
14
5.2.2
1 型文法
式 52 に
|α| ≤ kβ|
(53)
という制限，すなわち，初期記号の要素の方が書き換え規則を適用した後の
要素よりも少ない，という制限をつけた文法を 1 型文法, あるいは文脈規
定定型句構造文法, 文脈依存文法と呼ぶ。
5.2.3
2 型文法
さらに生成規則，式 52 が以下のように
A → B, A ∈ VN , β ∈ V +
(54)
すなわち A から β への書き換え規則のうち A は非終端記号の集合 VN の要
素であり，β は，その言語で生成されるすべての文の集合 (より正確にはそこ
から空列を除いた集合) V + の要素であるという制約を加えた文法のことを
2 型文法, あるいは文脈自由型句構造文法と呼ぶ。
5.2.4
3 型文法
文脈自由文法をさらに制約して
A
→ αB A, B ∈ VN
(55)
A
→ α α ∈ VT
(56)
と制限した場合を 3 型文法, あるいは正規文法 と呼ぶ。すなわち A, B
ともに非終端記号の集合 VN の要素であり，α は終端記号である場合である。
5.2.5
それぞれの文法の能力
0 型文法から 3 型文法までのそれぞれの文法は本質的に異なった能力を持っ
ているとされる。図に示すと図 10 のようになる。ここで，RL は正規言語，
CFL は文脈自由形言語，CSL は文脈規定型言語，TM はチューリング機械で
ある。
3 型言語を受理するのは有限オートマトンであり，2 型言語を受理するのは
プッシュダウンオートマトン pushdown automaton と呼ばれる。
1 型言語を受理するモデルは線形拘束オートマトン linear bounded
automaton であり，0 型言語を受理するモデルはチューリング機械
Turing machine と呼ばれている。
15
TM
CSL
CFL
RL
図 10: 形式言語相互間の関係
引用文献
Pinel, J. P. (2005). バイオサイコロジー. 西村書店.
長尾真 (1996). 自然言語処理. 岩波書店.
16