計算機数学入門

計算機数学入門
高畑 弘
2006 年 4 月 13 日
目次
第1章
1.1
1.2
1.3
集合
集合 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
基本的演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
その他の演算 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
第2章
2.1
2.2
2.3
2.4
2.5
2.6
写像と関係
写像 (関数) . . . . . . . . .
集合のべき乗 . . . . . . . .
部分関数 . . . . . . . . . . .
グラフと関数 . . . . . . . .
関係 . . . . . . . . . . . . .
記号列、言語、帰納法 . . .
2.6.1 帰納法 . . . . . . . .
2.6.2 再帰的定義 . . . . .
2.6.3 記号列 . . . . . . . .
2.6.4 言語 . . . . . . . . .
2.6.5 単位半群、群、準環
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
2
2
3
6
8
8
9
11
12
13
16
16
17
19
20
21
第 3 章 形式言語理論
23
3.1 言語とオートマトン . . . . . . . . . . . . . . . . . . . . . . . . . . . 23
3.2 文脈自由文法 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25
1
第1章
1.1
集合
集合
「物の集まりで、その中にあるものとないものを判定することのできる集まり」
を取りあえず、集合という。
集合を構成する各個体を、この集合の要素、あるいは元という。記号 x ∈ A によっ
て、x が集合 A の要素であることを表す。また、記号 x 6∈ A によって、x が集合 A
の要素ではないことを表す。x ∈ A のとき、「x は A に属する」あるいは「x は A
に含まれる」などという。
集合の定義（規定）の方法として次の２つがある。
外延的な定義: 当該集合の要素の一つ一つをすべて挙げて（連想させることもある）
その集合を規定する方法。
内包的な定義: 任意の個体について、それが当該集合の要素であるか否かを明確に
判定できる規準（別名を述語命題）があるとき、その述語命題が真となる
すべての個体の全体としてその集合を規定する方法。
例（外延的な定義）
√
1. A1 = {0, 2, 5, 9, −1000000}.
2. A2 = {1, 4, 9, 16, 25, . . .}.
3. A3 = {{1, 3}, {−5, 8}, {−12, −4}}.
4. A4 = {ac, abc, abbc, abbbc, . . .}.
5. A5 = {(1, 2), (2, 3), (3, 4), . . .}.
例（内包的な定義）
1. B1 = {x | x は奇数の整数 }.
2. B2 = {n | n は自然数の平方数 }.
3. B3 = {(x, y) | 2x + 3y = 6, x, y は整数 }.
4. B4 = {t | t は二等辺三角形 }.
2
5. B5 = {n | n ≡ 123 (mod 127)}.
注意 1. 集合 B の内包的な定義は A = {x | P (x)} といった形で与えられる。ここ
で、P (·) は（述語）命題関数である。A = {x | P (x)} は、各個体 x について、P (x)
の値が真であれば、x ∈ A であるし、P (x) の値が偽であれば、x 6∈ A であることを
示している。
注意 2. 外延的な定義と内包的な定義は相反するものではない。例えば、上の例の
中で、A2 = B2 であるし、{0, 2, 4, 6} = {n | n は偶数、0 ≤ n ≤ 6}.
以後において、数の集合を扱うとき、次の記号を用いる。
N ; 自然数の全体、ただし、ゼロ (0) を含む
N + ; ゼロを含まない自然数の全体
Z; 整数の全体
Q; 有理数の全体
R; 実数の全体
C; 複素数の全体
1.2
基本的演算
二つの集合 A, B に対して、A が B の一部であるとき、すなわち
A の元はすべて B の元である
または
∀x(x ∈ A =⇒ x ∈ B)
のとき、「A は B に含まれる」、または「B は A を含む」という。このとき、A は
B の部分集合であるという。A が B の部分集合であることを
A⊂B
または
B⊃A
と書く。
A⊂B
and
∃x (x ∈ B, x 6∈ A)
のとき、A は B の真部分集合であるといい、
A$B
または
3
B%A
と書く。
A⊂B
かつ
B⊃A
のとき、A と B は等しいといい、A = B と書く。
(A = B)
⇐⇒
(A ⊂ B) ∧ (A ⊃ B).
二つの集合 A, B に対して、A, B のいずれにも属する要素の全体を、A と B の共
通部分、または交わりといい、A ∩ B で表す。
A ∩ B = {x | x ∈ A, x ∈ B}
一般に、集合の系列 A1 , A2 , . . . , An に対してそれらの共通部分を
n
\
A1 ∩ A2 ∩ · · · ∩ An
または
Ak
k=1
と書く。
二つの集合 A, B に対して、A, B のいずれかに属する要素の全体を、A と B の
和集合、または結びといい、A ∪ B で表す。
A ∪ B = {x | x ∈ A または x ∈ B}
一般に、集合の系列 A1 , A2 , . . . , An に対してそれらの和集合、すなわち、それらの
どれか一つにはいっている要素の全体からなる集合を
n
[
A1 ∪ A2 ∪ · · · ∪ An
または
Ak
k=1
と書く。
二つの集合 A, B に対して、A に属してかつ B に属さない要素の全体からなる
集合を、A と B の差集合といい、A − B または A\B で表す。
A − B = {x | x ∈ A, x 6∈ B}.
なお、便宜上要素を全く含まない集合を導入して、φ で表し、これを空集合と呼ぶ。
重要な注意 どんな集合 A に対しても、φ ⊂ A が成り立つ。
考察の対象となるすべての要素の集合を全体集合という。全体集合 Ω を固定する
とき、その部分集合 A について、差集合 Ω − A を A の補集合といい、Ac で表す。
Ac = Ω − A = { x | x ∈ Ω, x 6∈ A} = { x | x 6∈ A}.
これまで複数の集合から別の集合を作る演算を述べてきた。これらの演算の間に成
り立つ事柄を下に定理として明記しておく。
4
定理 1.1. Ω をある全体集合とし、この定理の中に現れる集合はすべて Ω の部分集
合とする。
(1) A ∩ B = B ∩ A,
A ∪ B = B ∪ A.
(2) A ∩ (B ∩ C) = (A ∩ B) ∩ C,
A ∪ (B ∪ C) = (A ∪ B) ∪ C
(3) A ⊂ B ⇐⇒ A ∩ B = A ⇐⇒ A ∪ B = B.
(4) A ⊂ A ∪ B,
A ∩ B ⊂ A.
(5) A ⊂ C and B ⊂ C =⇒ A ∪ B ⊂ C.
(6) C ⊂ A and C ⊂ B =⇒ C ⊂ A ∩ B.
(7) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∩ C).
(8) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C).
(9) (A ∩ B)c = Ac ∪ B c ,
(A ∪ B)c = Ac ∩ B c .
(10) B ⊂ A, C ⊂ A ならば A − B ∩ C = (A − B) ∪ (A − C).
(11) B ⊂ A, C ⊂ A ならば A − B ∪ C = (A − B) ∩ (A − C).
注意 定理の中の９はドモルガンの定理として知られている。この命題は集合列 {A1 , A2 , . . . , An }
に対してつぎのように一般化される。
Ãn
!c
Ãn
!c
n
n
[
\
\
[
Ai =
Aci ,
Ai =
Aci
i=1
i=1
i=1
i=1
ここで、有限集合の記法について簡単な注意を与えておく。有限集合 A は {2, 3, 4, 5, 6}
のようにすべての元を列挙できる場合がある。このとき、つぎに示される表現はす
べて同じものである。
{2, 3, 4, 5, 6},
{2, 3, 6, 5, 4},
{6, 2, 6, 3, 5, 4, 2, 6}
なお、順列の立場からすると、上の３つの記号はまったく異なる順列を表す。順列
とは元を一定の順序に並べたものであり、集合とは異なる。すなわち
(x1 , x2 , · · · , xm ) = (y1 , y2 , · · · , yn )
とは、m = n かつ x1 = y1 , x2 = y2 , · · · , xm = yn であることである。順列には
有限の場合も、無限に続く場合もある。無限に続く場合として、区間 (0, 1) に属す
る数の小数展開を考えてみるとよい。
最後に、計算機科学に頻繁に現れる二つの集合について触れる。
5
ブール集合
B = {T, F }
B はブール集合あるいは真理値集合といい、二つの元 T (True) と F (False) とか
らなる。
素数の集合
P = {n k n は素数 } ⊂ N
P を外延的に表すと
2, 3, 5, 7, 11, 13, . . .
となる。P についての次の命題を証明しておくと便利かも。
[命題]： P は無限集合である。
次の補助定理をまず証明しよう。
補助定理 すべての 2 以上の自然数は P のいずれかの元で割り切れる。
補助定理の証明 帰納法を用いる。N P = N − P とおく。自然数の 2 については、
命題は成り立っている。いま、k 以下の自然数すべてに命題が成り立っていると仮
定する。k + 1 について検討しよう。k + 1 ∈ P の場合は明らかに命題が成り立って
いる。k + 1 ∈ N P と仮定すると、定義により、k + 1 = nm (n, m ≤ k) と分解で
きる。仮定によって、n, m については命題が成り立つから、k + 1 についても命題
が成り立つ。
命題の証明 P が有限集合であると仮定しよう。P = {p1 , p2 , p3 , . . . , pn } と
する。
M = (p1 ∗ p2 ∗ p3 ∗ · · · ∗ pn ) + 1
なる自然数 M を考えるとき、M はどんな素数で割っても必ず１が余る。これは上
の補助定理に矛盾する。よって、P が有限集合であるという仮定は成立しない。す
なわち、P は無限集合である。
1.3
その他の演算
n 個の集合 A1 , A2 , . . . , An のそれぞれから一つづつ元を取り出して作られる順列
の集合
A1 × A2 × · · · × An =
n
Y
Ai = {(a1 , a2 , . . . , an ) k ai ∈ Ai , 1 ≤ i ≤ n }
i=1
6
を集合 A1 , A2 , . . . , An の積集合という。とくに、Ai がすべて同じ集合 (A) の場合、
この積集合を An で表す。
集合 A が与えられたとき、A のすべての部分集合の集合を集合 A のべき集合とい
い、PA または 2A などで表す。
PA = 2A = {X k X ⊂ A }
集合 A が有限集合のとき、A に含まれる元の個数を |A| で表し、これを集合 A の濃
度という。
定理 1.2. m 個の元を含む集合 A のべき集合の濃度は 2m である。すなわち
|PA| = 2|A| = 2m .
濃度ついては次の事柄が成り立つ。
1. |Pφ| = 1
2. |A × B| = |A| ∗ |B|
すでに和集合や交わりなどについては定義した。二つの集合 A, B について、あ
る異なる要素 tA , tB をとり、
A × {tA } ∪ B × {tb }
という集合をつくる。これを集合 A, B の直和といい、A + B で表す。一般に、n 個
の集合 A1 , A2 , . . . , An に対して n 個の異なる要素 t1 , t2 , . . . , tn をとり
n
[
Ai × {ti }
i=1
なる集合を作る。これを集合 A1 , A2 , . . . , An の直和といい、
n
X
Ai
A1 + A2 + · · · + An
i=1
などで表す。
A, B が有限集合であるとき、次の命題は明らか。
|A × B| = |A| ∗ |B|
|A ∪ B| ≤ |A| + |B|
|A ∩ B| ≤ Min{|A|, |B|}
|A − B| ≤ |A|
|A + B| = |A| + |B|
7
第2章
2.1
写像と関係
写像 (関数)
定義 2.1. 集合 A から集合 B への写像 f を f : A → B と表す。これは集合 A の各
元 a に集合 B の元をひとつ割り当てることで、f のよって元 a に割り当てられた集
合 B の元を f (a) で表す。この割り当てを a 7→ f (a) と表す。集合 A, B をそれぞれ
写像 f の定義域、値域という。
f (A) = {b k b ∈ B, ∃a ∈ A such that b = f (a) }
によって定義される B の部分集合 f (A) を f による A の像という。写像を関数とも
いう。
ここで、論理に関する注意を与えておく。我々は「P ならば Q である」というこ
とがある。論理の出発点に関して再考しておく必要がある。以下、P, Q は命題を
表す。
P ∨Q
⇐⇒
P or Q
P ∧Q
P
⇐⇒
⇐⇒
P and Q
not P
実は、P ∧ Q は P ∨ Q として表せる。ここで、“ならば ”に戻ろう。
P ⇒ Q
⇐⇒
P ∨Q
が “ならば ”の定義である。このようにすると、“ならば ”の意味が明確で「P なら
ば Q である」が「真」であるとは、P が「偽」であるか、または Q が「真」である
ことである。このことを納得するには少し時間が掛かるだろう。「P ならば Q であ
る」が「真」であるためのひとつの充分条件として、P が「偽」であることがある。
すなわち、P が「偽」つまり前提が「偽」であれば、結論 Q がなんであれ、「P な
らば Q である」は「真」なのである。
集合 A が空集合 φ のとき、次の命題は「真」である。
A の元 a が存在すれば、それに対して B の元 b がただひとつ定まる
8
この写像を Λ で表す。えっ、このへんな写像はひとつなの？ よろしい、二つの写
像 Λ1 , Λ2 があったとしよう。このとき、次の命題は「真」である。
∀ a ∈ φ, Λ1 (a) = Λ2 (a).
よって、Λ1 = Λ2 。ところで、A 6= φ だが、B = φ のときは、A から B への写像は
存在しない。なぜならば、もし存在したとして、そのひとつを f とすると、a ∈ A
に対して、f (a) ∈ B となり、B = φ に反することになる。
定義 2.2.
(1) 写像 f : A → B が f (A) = B のとき、上への写像または全射という。
(2) 写像 f : A → B が a 6= b =⇒ f (a) 6= f (b) のとき、1 対 1 の写像または
単射という。
(3) 写像 f : A → B が全射でかつ単射のとき、全単射または双射という。
定理 2.1. A, B を有限集合とする。A から B への全単射があるとき、このときに
限って |A| = |B| である。
例題 2.1. 関数 f : N + × N + → N + を次のように定義する。
f (x, y) =
(x + y − 1)(x + y − 2)
+y
2
これは、全単射となる。
2.2
集合のべき乗
集合 A から集合 B への写像の全体を [A → B] で表す。この集合を B A で表すこと
もある。
集合 {1, 2, 3, . . . , n} を n で表す。このとき、
[n → A] = An .
とくに
[0 → A] = Aφ = {Λ}.
ところで、[n → A] の各元 f に対して、An の元
(f (1), f (2), . . . , f (n))
9
がただひとつ定まる。逆に、An の元 (a1 , a2 , . . . , an ) に対して、f (i) = ai (1 ≤ i ≤ n)
をみたす [n → A] の元 f がただひとつ定まる。前者、後者の対応のさせ方をそれぞ
れ F, G で表す。すなわち
Fn
:
[n → A] → An
Gn
:
An → [n → A].
これらの写像 Fn , Gn が全単射であることはあきらかである。いま述べたことは、
A0 = {Λ} と定義すれば、n = 0 のときもまったく同様に成り立つ。
定義 2.3. ふたつの写像 f : A → B, g : B → C に対して、それらの合成写像
g · f : A → C とは、集合 A の各元 a に対して、集合 C の元 g(f (a)) を割り当てる写
像をいう。すなわち
g · f (a) = g(f (a)).
これを
f
g
A→B→C
とかくこともある。
定理 2.2. 集合 A, B に対して、全単射 f : A −→ B があるとき、全単射 g :
B −→ A で、g(f (a)) = a (∀a ∈ A) かつ f (g(b)) = b (∀b ∈ B) をみたす写像 g
が存在する。この写像 g を写像 f の逆写像という。 f は g の逆写像である。
定義 2.4. A から B への全単射 f が存在するとき、A と B とは同型であるといい、
f を A と B との間の同型写像という。
一般に二つの集合 A, B が同型であることを、
A ∼
= B
で表す。
定理 2.3. 関係 ∼
= について次の事柄が成り立つ。
(1) A ∼
=A
(2) A ∼
= B =⇒ B ∼
=A
(3) A ∼
= C.
= C =⇒ A ∼
= B and B ∼
すなわち、関係 ∼
= は同値関係である。
集合 A に対して、A 上の恒等写像を idA で表す。すなわち、idA (a) = a
10
(∀a ∈ A).
定理 2.4. 集合 A と自然数 m, n に対して
Am × An ∼
= Am+n
が成立する。
注意 この定理において、mn = 0 の場合についてはコメントが必要であるが、今
のところ、深入りは避けたほうがよかろう。質問があれば誤魔化すことにする。し
かし、証明は与えておいたほうがよかろう。
証明 mn 6= 0 のときは、明らかであるから、m = 0 の場合について証明を与え
る。m = 0 より、Am = {Λ}。したがって左辺は {Λ} × An となる。しかし、あきら
かに集合 An と {Λ} × An との間には全単射が存在する。ゆえに、A0 × An ∼
= An が
成立する。
全体集合 S の部分集合 A に対して、写像 χA : S → B = {T, F } をつぎのように
定める。この写像 χA を集合 A の特性関数ともいう。
(
T, (a ∈ A)
χA (a) =
F, (a ∈ Ac ).
逆に、χ : S → B = {T, F } があたえられると、S の部分集合 {skχ(s) = T } が決ま
る。すなわち、2S と [S → B] との間に同型写像が存在する。
定理 2.5. 二つの有限集合 A, B に対して |[A → B]| = |B||A| が成り立つ。
証明
明らか。
系 1. 有限集合 S には 2|S| 個の部分集合がある。
2.3
部分関数
関数 f : A → B が与えられても、すべての a ∈ A に対して f (a) が決まらない場
合がある。
例 f : N 2 → Z 2 を次のように定める。(a, b) ∈ N 2 に対して、au+bv = 1 (0 < u < b)
をみたす (u, v) ∈ Z 2 を対応させる。GCD(a, b) = 1 のような (a, b) ∈ N 2 に対して
は f (a, b) が求まるが、GCD(a, b) = d > 1 の場合は f (a, b) は求まらない。
例 関数 f : N 2 → N 2 を次のように定義する。
(
(a mod b, a div b), b > 0 のとき f (a, b) =
定義されない,
b = 0 のとき.
計算機科学では、関数はプログラムで与えられることが多い。プログラムにおいて
は、入力が不適切であれば、無限ループに入ったり、出力が得られな勝ったりする。
したがって、次の定義がよく用いられる。
11
定義 2.5. 集合 A から集合 B への部分関数 f とは、集合 A の部分集合 dom(f ) （こ
れを f の定義域という）の各元 a に、集合 B のひとつの元 f (a) を割り当てるもの
で、これまでと同じく、f : A → B,
a 7→ f (a) と書く。
次の二つの関数はいずれも全域関数である。
(
˝
m − n, if m ≥ n
− : N2 → N,
(m, n) 7→
0,
if m < n
− : N 2 → Z,
(m, n) 7→ m − n.
後者は値域を N に代えると、関数 − は部分関数となる。しかし、全域関数も部分
関数も見方を変えればおなじものと考えることができる。
部分関数 f : A → B に対して、B に属さない新しい元 ⊥ をとり、集合 B ∪ {⊥}
を作る。部分関数 f の代わりに全域関数 f ⊥ を次のように定義する。
(
f (a), if a ∈ dom(f )
⊥
f (a) =
⊥
if a 6∈ dom(f )
逆に f : A → B ∪ {⊥} という（全域）関数は、f (a) =⊥ のとき、元 a の像は “定義
されない” と考えれば、部分関数である。それでは、部分関数などという余計な概
念は必要ないではないか？ところが違う。計算機科学と数学は違うのであるよ。
計算機科学においては、関数はプログラムを意味するが、ちゃんと出力が得られ
る入力がどんな範囲のものかは、最初は厳密には考えることができないようなプロ
グラムもある。プログラムを作成してからその範囲を厳密にかんがえればよいよう
なこともあるので部分関数という概念が必要なのではないかとボンヤリ考えている。
しかし、上で述べたように、（全域）関数の全体 [A → B ∪ {⊥}] と部分関数の全
体 Pfn[A,B] との間には同型写像 f 7→ f ⊥ が存在する。
系 2. 二つの有限集合 A, B に対して A から B への部分関数は全部で
(|B| + 1)|A| = (|B ∪ {⊥}|)|A|
個ある。
2.4
グラフと関数
定義 2.6. n (n ≥ 2) 個の集合の直積 A1 × A2 × · · · × An の部分集合をグラフ (graph)
という。
定義 2.7. n (n ≥ 2) 個の集合の直積 A1 × A2 × · · · × An のグラフ G に対して定まる
Ak の部分集合
Projk (G) = {ak k ak ∈ Ak , ∃(a1 , a2 , . . . , ak , . . . , an ) ∈ G}
をグラフ G の第 k 成分への射影 (projection) という。
12
定義 2.8. 関数 f : A → B に対して、A × B のグラフ
graph(f ) = {(a, b) ka ∈ A, b ∈ B, b = f (a)}
を関数 f のグラフという。
f が部分関数のときは、
graph(f ) = {(a, b) ka ∈ dom(f ), b ∈ B, b = f (a)}
を部分関数 f のグラフという。
定理 2.6. A × B の部分集合 G がある部分関数のグラフであるための必要十分条
件は
(a, b) ∈ G and (a, b0 ) ∈ G =⇒ b = b0
が成り立つことである。
2.5
関係
定義 2.9. 集合 A から集合 B への（２項）関係 R : A V B とは直積集合 A × B の部
分集合である。(a, b) ∈ R のとき、aRb と書き、元 a は元 b と関係 R にあるという。
一般に、関係 R : A V A に対して次の概念が重要である。
(1) （反射律）
aRa
for ∀a ∈ A (2) （推移律）
aRb, bRc =⇒ aRc
(3) （対称律）
aRb =⇒ bRa
関係は必ずしもこれら３つの性質をもつとは限らない。
定義 2.10. A から A への関係 R が反射律、推移律、対称律を満たすとき、関係 R
は A 上の同値関係であるという。
関係 R : A V B に対して、
b
R(a)
= { b k aRb } ⊂ B
(a ∈ A)
とおくと、部分関数
b : A −→ PB,
R
b : a 7−→ R(a)
b
R
が求まる。
b
例題 2.2. 関係 R が N × N の部分集合 { (m, n) k m 5 n } とすると、R(m)
=
{ n k n = m } となる。
13
例題 2.3. 素数 p に対して、Z × Z の部分集合 { (a, b) k p|a − b } を考えると、こ
の部分集合に対応する関係 R については
aRb ⇔ a ≡ b
mod p
b
がいえる。また、R(a)
= { a + kp k k ∈ Z } となる。
定義 2.11. n = 1 に対して、直積集合 A1 × A2 × · · · × An の部分集合を集合
A1 , A2 , . . . , An の間の n 項関係 R という。
例題 2.4.
def
R = { (a, b, c) k a + b 5 c} ⊂ N × N × N
定義 2.12. n 項関係 R ⊂ A1 × A2 × · · · × An の特性関数
χR
:
χR (a1 , a2 , . . . , an ) =
A1 × A2 × · · · × An −→ {T, F }
(
T, if(a1 , a2 , . . . , an ) ∈ R
F,
otherwise
を n 項関係 R の述語という。さらに、一般に関数
p : A1 × A2 × · · · × An −→ {T, F }
を n 項の述語という。
明らかに、n 項関係と n 項の述語との間には全単射が存在する。
普通の用語法では述語は主語に対して用いられ、
“主語” は “述語” である
という形をとる。しかし、ここで述べる「述語」の意味はそれとはすこし異なる。
本質的にはおなじであるが。例えば、「甚平さんは農業を職業にしている。」という
型の命題を考える。A = { 人名の全体 } , B = { 職業の全体 } とする。a ∈ A と
b ∈ B の元をとり、a と b との取り合わせが正しいとき、aRb とする。上述した特性
関数 χR は各 (a, b) ∈ A × B の関係 R についての真偽を判定する機能をもつもので
ある。
一般的な述語についても説明をしておこう。A を人間のある集団とする。
n times
p
:
p(a1 , a2 , . . . , an ) =
}|
{
z
A × A × · · · × A −→ {T, F }
(
T, a1 , a2 , . . . , an は親戚同士
F, otherwise
この場合も「述語」が真偽の判定を表す。したがって、プログラムに関する理論に
おいて重要な意味をもつことが理解されるだろう。
最後に関係の合成についてのべる。
14
定義 2.13. 二つの関係 R : A V B と S : B V C に対して、R, S の合成
S·R : AVC
を次のように定義する。
def
S · R = { (a, c) k ∃b ∈ B s.t. aRb and bSc} ⊂ A × C
関係 R が R : A V A のとき、関係 R のべき乗を次のように定義する。
R0
=
idA = { (a, a) k a ∈ A }
R
1
=
R
R
2
=
R·R
R
3
=
R2 · R
···
Rn+1
=
Rn · R.
定義 2.14. いくつかの関係 Si : A V B について、関係を積集合の部分集合という
立場から見ることによって、それらの関係の和 S をつぎのように定義することがで
きる。
[
def
S =
Si
i
定義 2.15. 関係 R : A V A に対して
[
def
R+ =
Ri ,
i>0
def
R∗ =
[
Ri
n=0
とおき、R+ , R∗ をそれぞれ、関係 R の推移的閉関係（推移的閉包）、推移反射的
閉関係（推移反射的閉包）という。
関係を集合 (グラフ）とみなすことにより、次の定義は受け入れられるであろう。
定義 2.16. 積集合 A × A の中で、関係 R を含んで、推移律をみたすようなすべて
の関係の共通部分を関係 R の推移的閉包という。これを別の言葉でいえば、積集合
A × A の中で、関係 R を含んで、推移律をみたす最小の関係である。
定理 2.7. R+ は関係 R の推移的閉包である。R∗ は関係 R の推移反射的閉包 である。
証明
に対して
結合則の証明一般に、３つの関係 R : A V B, S : B V C, T : C V D
T · (S · R) = (T · S) · R
が成り立つことを示す。(a, d) ∈ T · (S · R) とすると、ある c ∈ C が存在して、
cT d, a(S · R)c となる。また、ある b ∈ B が存在して、bSc, aRb となる。このとき、
15
b(T · S)d となるが、aRb であるから、(a, d) ∈ (T · S) · R が得られる。逆の包含関
係も同様に証明されるから、結合則が示されたことになる。
R の推移的閉包を R で表す。まず、R+ が推移律を満たすことを示そう。そのた
めには、最初に Rn · Rm = Rn+m を示す必要がある。
Rn · Rm = Rn+m の証明。
m = 1 の場合は定義より明らか。m = k の場合に命題が正しいと仮定する。m =
k + 1 の場合。仮定により、
右辺 = Rn+k · R = (Rn · Rk ) · R = Rn · (Rk · R) = Rn · Rk+1 = 左辺.
本来の証明に戻る。aR+ b, bR+ c とする。定義により、aRn b, bRm c となる n, m ∈
N が存在する。したがって、aRm · Rn c。すでに証明したことから、aRn+m c。した
がって、aR+ c。すなわち、関係 R+ は推移律を満たしている。いま、関係 S が R を含
んで、しかも推移律を満たしているとする。aRb, bRc つまり aR2 c ならば aSb, bSc
であるから、aSc, すなわち R2 ⊂ S. 次に、aRb, bR2 c つまり aR3 c ならば aSb, bSc で
あるから、aSc, すなわち R3 ⊂ S. 以下同様ににしてすべての n = 1 に対して Rn ⊂ S
となり、R+ ⊂ S が得られる。よって、関係 R+ は関係 R を含んで推移律を満たす
最小の関係となる。
2.6
2.6.1
帰納法、再帰的定義
帰納法
イタリアの数学者ペアノ（Giuseppe Peano:1858–1932）は自然数の理論を打ち立
てるために、次のような公理（ペアノの公理) をまとめた。
(P0) 集合 N は元 0 を含み、以下の性質をもつ写像 σ : N −→ N が存在する
(P1) σ(n) 6= 0 (∀n ∈ N )
(P2) m 6= n ならば σ(m) 6= σ(n)
(P3) 集合 N の部分集合 S が 0 を含み、さらに集合 S の任意の元 n ∈ S に対して
σ(n) ∈ S ならば、集合 S は集合 N に等しい
上の公理において、各 n ∈ N に対する σ(n) を n の後者という。また、公理 (P3) を
帰納法の公理という。帰納法はすでに関係のところで、R+ が推移的閉包であること
を証明するのに用いたし、諸君も高校で、学習してきたであろう。しかし、少し触
れておく。
一般に、命題 P (n) がすべての自然数 n に対して成立することを示すためには次
の 2 つのステップを踏めばよい；
16
1. P (0) が成り立つことを証明する（初期段階)
2. P (k) が成り立つことを仮定して P (σ(k)) が成り立つことを証明す
る（帰納段階)
帰納法で証明する場合、次のような形で行うこともある。
1. P (0) が成り立つことを証明する（初期段階)
2. k 以下のすべての m に対して P (m) が成り立つことを仮定して P (σ(k))
が成り立つことを証明する（帰納段階)
実際、素数が無限に存在することの証明のところで用いた帰納法はこの形であった。
ただ、初期段階が P (2) ではあったが。
帰納法の練習として、これまでに証明された次の命題を改めて証明しよう。
定理 2.8. 集合 A の濃度が n ならばそのべき集合 PA の濃度は 2n である。
証明 n = 0 の場合（初期段階）
：この場合は A = φ であるから、PA = {φ}. よっ
0
て、|PA| = 1 = 2 .
n = k の場合に命題が正しいと仮定する。|A| = k + 1 とすると、a ∈ A を選び、
A = B ∪ {a} と書ける。ここで、B = A − {a}。PA の各元が a を含むグループ I と
a を含まないグループ II とに分けられる。II は PB に他ならないから、仮定によっ
て |II| = 2k 。一方、I と PB との間には全単射が存在する。よって、やはり |I| = 2k
を得る。したがって、|PA| = 2k + 2k = 2k+1 が成り立つ。
2.6.2
再帰的定義
帰納法を利用して関数を定義することを再帰的定義または帰納法的定義という。
自然数に関する関数 f : N −→ A を定義するのに、次の２ステップを踏む:
Step 1 f (0) = a ∈ A とする。[初期段階]
Step 2 自然数 k に対して f (k) が定義されたとして、f (k + 1) を定義する。
[帰納（再帰）段階]
例題 2.5. 漸化式 an = 3an−1 + 2 (n = 1),
a0 = 3 は再帰的に定義されている。
上に述べたものとは少し異なるが、次の例も再帰的定義である。
例題 2.6.
Step 1 f (0) = a0 , f (1) = a1 , . . . , f (h) = ah ∈ A とする。[初期段階]
Step 2 自然数 k > h に対して f (k − h + 1), f (k − h + 2), . . . , f (k − 1), f (k)
が定義されたとして、f (k + 1) を定義する。[帰納（再帰）段階]
17
この例として
例題 2.7. a0 = 2, a1 = 3, an = 2an−1 − an−2 (n = 2)
再帰的定義はプログラムにおいて重要な役割を果たす。プログラムを見やすくす
る。例えば、階乗 f (n) = n! は f (0) = 1, f (n) = n ∗ f (n − 1) で定義されるが、再帰
的プログラムを許すプログラム言語では、次のような構造のプログラムを許容する。
例題 2.8.
n! := if n = 0 then 1 else n ∗ (n − 1)!
たとえば、数式処理ソフト Mathematica では次のようなプログラムができる。
例題 2.9.
f [0] = 4; f [1] = 2; f [x ] := f [x] = f [x − 1] + 2 ∗ f [x − 2]
再帰的定義は関数の定義のみならず、情報科学の諸分野で頻繁に用いられる。そ
の例として、次の例題を考えよう。
例題 2.10. 自然数の 10 進法表示を文字列として考えて、それぞれの自然数 k の後者
σ(k) を定義することを試みる。そのために、まず、自然数の 10 進法表示の全体 ND
を定義しなければならない。D = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} を 10 進法の数字とする。
(1) 初期段階：D の各要素 d は ND に属する。
(2) 帰納段階：w が ND に属し、数字 d が D に属するとき、w のあとに
続けた wd も ND に属する。
(3) (1) および (2) の手順で得られる文字列のみが ND に属する。
次のような、関数 m : D → D を定義する。
m(0) = 1, m(1) = 2, m(2) = 3, m(3) = 4, m(4) = 5,
m(5) = 6, m(6) = 7, m(7) = 8, m(8) = 9, m(9) = 0.
これらの準備をもって、10 進法による表示の自然数の後者を表す関数 σ : ND −→ ND
の再帰的定義をあたえる。
(1) 初期段階：v = d ∈ D ⊂ ND （１文字の数字）に対して
(a) d 6= 9 ならば σ(v) = m(d),
(b) d = 9 ならば σ(d) = 10
(2) 再帰段階：w ∈ ND , v = wd と分解できるときは
(a) d 6= 9 ならば σ(v) = wm(d),
(b) d = 9 ならば σ(v) = σ(w)0
18
例題 2.11.
σ(465) = 46m(5) = 466
σ(6799) = σ(679)0 = σ(67)00 = 6m(7)00 = 6800
σ(349) = σ(34)0 = 3m(4)0 = 350
例題 2.12. 自然数の加法はつぎのように、再帰的定義によって与えられる。
1 初期段階：m + 0 = m
2 再帰段階：m + n が定義されたとして m + σ(n) = σ(m + n)
この定義から、加法 (+) に関する結合法則や交換法則が証明される。
例題 2.13. 自然数の乗法 (∗) はつぎのように、再帰的定義によって与えられる。
1 初期段階：m ∗ 0 = 0
2 再帰段階：m ∗ n が定義されたとして m ∗ σ(n) = m ∗ n + m
この定義から、乗法 (∗) に関する結合法則や交換法則および分配法則が証明される。
2.6.3
記号列
情報科学において、データとは文字列の集積である。したがって、最初に文字の
集合を定めておく必要がある。集合 X を使用する文字の集まりとする。これをアル
ファベット集合という。集合 X の有限個並べたものを文字列という。文字列の集合
を X ∗ で表す。X ∗ の各元 w にその中に含まれる文字の個数を `(w) で表し、文字列
w の長さという。X ∗ の中に長さ 0 の文字列を想定して、Λ で表す。これを空列とい
うことにする。文字列は w = (x1 , x2 , . . . , xn ) または x1 x2 · · · xn で表す。空列を考慮
しないときは、X ∗ の代わりに X + = X ∗ − {Λ} を用いる。
二つの文字列 w = (x1 , x2 , . . . , xm ) と w0 = (x01 , x02 , . . . , x0n ) の結合を、文字列
ww0 = (x1 , x2 , . . . , xm , x01 , x02 , . . . , x0n )
と定義する。このとき、次の事柄が成立する。
(a) `(ww0 ) = `(w) + `(w0 )
(b) w(w0 w00 ) = (ww0 )w00
(c) wΛ = Λw = w
例題 2.14. 自然数の 10 進法表示の全体の集合 ND は D+ である。
19
例題 2.15. X = {1} の場合、X 0 = {Λ}, X 1 = {1}, X 2 = {11}, X 3 = {111}, . . .
となり、X ∗ = {Λ, 1, 11, 111, 1111, . . .}.
X∗ は Xn
X∗
(n = 0) の直和と考えることもできる：
X
=
Xn = X0 + X1 + X2 + X3 + · · ·
n=0
= {Λ} + X + X × X + X × X × X + · · ·
定義 2.17. 集合 X ∗ と関数 ` : X ∗ −→ N の帰納的定義。
初期段階： X ∗ は空列 Λ という元を含み、`(Λ) = 0 とする。
帰納段階： X ∗ の元 w と X の元 x があるとき、これを結合した (x, w) = xw も
X ∗ の元であり、`(xw) = `(w) + 1 とする。
次に結合写像 conc : X ∗ × X ∗ −→ X ∗ , (w, w0 ) 7→ ww0 を帰納的に定義する。
初期段階： w ∈ X ∗ に対して conc(Λ, w) = conc(w, Λ) = wΛ = Λw = w
帰納段階： x, v, w ∈ X ∗ に対して、conc(conc(x, v), w) = conc(x, conc(v, w)) =
(x, conc(v, w))
この定義に従えば、conc(v, w) = conc(vΛ, w) = (v, conc(Λ, w)) = (v, w) である。
最後の項を vw で表す。すると conc(conc(x, v), w) = (x, conc(v, w)) = (x, (v, w)) =
(x, vw) = x(vw) = (xv)w となる。
2.6.4
言語
アルファベット集合 X（その元を文字という）から作った有限列の集合 X ∗ の部分集
合を X 上の言語という。英語の単語の集合はアルファベット集合 X = {a, b, . . . , y, z}
上の言語である。言語に関する演算を定義する。
定義 2.18. A, B を有限アルファベット集合 X 上のふたつの言語とする。
1 言語 A と言語 B との和とは言語 A ∪ B = {wk w ∈ A または w ∈ B} を意味
する。A + B と書くこともある。直和ではない。
2 言語 A と言語 B との結合 A · B とは、言語 A の元の後に言語 B の元を結合し
て得られる言語である。
3 言語 A の繰り返し A∗ とは、言語 A に属する元を有限個任意に選んで結合して
得られる言語である。すなわち、A∗ = {w1 w2 · · · wn k n = 0, wi ∈ A } であ
∞
[
∗
∗
る。もちろん、n = 0 の場合も考えて、Λ ∈ A 。A =
An となることは
n=0
明白。
20
例題 2.16. X = {a, b} として、二つの言語を A = {a}∗ , B = {b}∗ とする。このと
き次の言語を求めよ。
1 C =A∪B
2 D =A·B
3 C∗
4 D∗
例題 2.17. 次の言語を求めよ。
1 ({a} ∪ {bb})∗
2 ({a4 } ∪ {a6 })∗
2.6.5
単位半群、群、準環
定義 2.19. 集合 M と M 上の２項演算 m : M × M → M および、M の特別な元 e
が次の条件をみたすとき、組 (M, m, e) を単位半群（モノイド）という。
1 演算 m は結合則をみたす。つまり、任意の x, y, z ∈ M に対して
m(m(x, y), z) = m(x, m(y, z))
2 元 e は演算 m の単位元、つまり、任意の x ∈ M に対して
m(x, e) = m(e, x) = x
例題 2.18. (N, +, 0) は単位半群である。0 は加法単位元。
(m + n) + p = m + (n + p),
m+0=0+m=m
また、(N, ∗, 1) も単位半群である。1 は乗法単位元。
(m ∗ n) ∗ p = m ∗ (n ∗ p),
m∗1=1∗m=m
定理 2.9. 単位半群に単位元はひとつしかない。
定義 2.20. (M, ·, e) を単位半群とする。２項演算は · で表す。
x·y =y·x=e
が成立するとき、元 x は元 y の逆元という。集合 M のどの元にも逆元があるとき、
M は群をなすという。
21
次の事柄は容易に確かめられる。
1. (N, +, 0) は可換単位半群である。
2. (N, ·, 1) は可換単位半群である。
3. 乗法は加法に対して、分配的である。すなわち、任意の m, n. p ∈ N に対して
m ∗ (n + p) = m ∗ n + m ∗ p
これらのことを一般化して、つぎの定義を与える。
定義 2.21. 集合 S 上の二つの２項演算 +, · について、次の事柄が成り立つとき、組
(S, +, ·, 0, 1) は半環と呼ばれる。
1 (S, +, 0) は可換単位半群である。
2 (S, ·, 1) は単位半群である。
3 乗法 · は加法 + に対して分配的である
a · (b + c) = a · b + a · c
例題 2.19. X ∗ のべき集合 LX = PX ∗ はアルファベット集合 X 上のすべての言語の
集合である。このとき、あきらかに組 (LX , ∪, ·, φ, {Λ}) は半環である。このこと
を示すには、(LX , ∪, φ) が可換単位半群であること、(LX , ·, {Λ}) が単位半群であ
ること、A · (B ∪ C) = A · B ∪ A · C が成り立つことを示せばよい。
22
第3章
3.1
形式言語理論
言語とオートマトン
上の節で、言語を代数的立場から見てきた。この節では、ある言語の構造を機械
の立場から見る。
例 次の図は言語 {a}∗ · {b}∗ を受容し認識する機械の構造を示す。
一般に、上の図の q0 , q1 , q2 のような場所のことを「状態」とよび、q0 , q1 のよう
に二重丸で囲んだ状態を「受容状態」と呼ぶ。また、q0 のように、そこから出発す
る状態を「初期状態」と呼ぶ。
定義 3.1. アルファベット集合を X とする有限状態（受容）機械または有限受容器
(FSA、finite − stateacceptor) とは、次の四つ組 (Q, δ, q0 , F ) の構造をもつ機械のこ
とである。すなわち、Q は状態を元とする有限集合で、
1 δ : Q × X → Q は状態遷移関数 で、機械が状態 q にいるときに入力文字 x を
読むと次に状態 δ(q, x) に移る。
2 q0 ∈ Q は初期状態 で、機械の状態は初めはこの状態にある。
3 F ⊂ Q は受容状態の集合で、機械が状態 q ∈ F で終われば、入力文字列は受
容される。
例 先の例を定義の形に書くとつぎのようになる。
(Q = {q0 , q1 , q2 }, δ, q0 , F = {q0 , q1 })
ただし、アルファベットの集合は X =
示される。
δ
q0
q1
q2
{a, b} であり、状態遷移関数 δ は次の表で
a b
q0 q1
q2 q1
q2 q2
23
例 言語 {a, b}∗ − ({a}∗ · {b}∗ ) を受容する FSA を考えよう。
有限状態機械 M は X 上の有限文字列の集合 X ∗ を次の方法により二つに分ける。
1. 文字列 w ∈ X ∗ の左端の文字 a1 を用いて δ(q0 , a1 ) = p1 を決める。w の
左から２番目の文字 a2 を用いて δ(p1 , a2 ) = p2 を決める。以下同様にして、
w = a1 a2 · · · am ならば δ(pm−1 , am ) = pm が定まる。pm ∈ F ならば機械は文
字列 w を受理する。
2. 上と同様にして、pm 6∈ F ならば機械は文字列 w を受理しない。
有限状態機械 M によって受理される文字列の集合を T (M ) で表す。T (M ) の性
質を調べよう。
文字列 w について、上の１. の手続きにより、最終的に到達する状態を δ ∗ (q0 , w)
で表そう。この関数
δ ∗ : Q × X ∗ −→ Q
を厳密に定義する。
初期段階： すべての状態 q ∈ Q に対して、δ ∗ (q, Λ) = q.
帰納段階: すべての状態 q ∈ Q 、すべての文字 x ∈ X 及びすべての文字列 w ∈ X ∗
に対して δ ∗ (q, wx) = δ(δ ∗ (q, w), x) とする。
定義 3.2. 有限状態機械 M = (Q, δ, q0 , F ) が受容する記号列の集合（受容集合）
T (M ) ⊂ X ∗ は
T (M ) = {w|δ ∗ (q0 , w) ∈ F }
によって定義される。逆に、X ∗ の部分集合 L に対して、L = T (M ) となる有限状
態機械 M が存在するとき、L は有限状態言語と言う。有限状態言語は正則言語と
も呼ばれる。
例 以下の例では X = {0, 1} とする。
(i) L = {w| 文字列 w の中に 1 が奇数個ある }
(ii) L = {Λ}
(iii) L = {1011}
(iv) L が X ∗ の有限集合の場合を、L = {0, 11, 101} として考える。
上の例 (ii) と (iv) から、X ∗ の有限集合は有限状態言語であることがわかる。
24
3.2
文脈自由文法
英語の構文を解析する際、文章 S を次のような逐次置き換えを行う。昔の英文法
の時間が懐かしいですね。
S → N P V P : 文章 S は名詞句 (N P ) と動詞句 (V P ) とに分かれる。
N P → Det Adj N : 名詞句 (N P ) は冠詞 (Det)、形容詞 (Adj)、
名詞句 (N ) に分かれる。
V P → V N P : 動詞句 (V P ) は動詞と名詞句に分かれる。
もちろん、英語の完全な（？）文法はもっとたくさんの置き換え規則からなる。こ
のように、ある言語（文字列）の構造をを置き換え規則によって定めることは計算
機科学において大変重要である。プログラム言語の構文規則を定め、どんな形の記
号列がそのプログラム言語のプログラムとして正しいかを決めるのに、以下に述べ
る文脈自由文法が大変役に立つのである。
例として、10 進法表示によって数を表す記号列を生成する規則を考える。
179 −−− 数字の列 .394 −−− 小数点のあとに数字の列 15.64 −−− 小数点をはさんで前後に数字の列
記号 M を記号 D かまたは列 M D に置き換えられる規則を
M −→ D | M D
で表す。また、記号 D を１０個の数字に置き換えられる規則を
D −→ 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
で表す。さらに次の規則を付け加える。
N −→ M | .M | M.M
記号列 w の中のひとつの文字を許された規則を用いて置き換えられた文字列を w0
とするとき、この関係を
w ⇒ w0
で表す。15.64 は記号 N から出発して次のようにして得ることができる。
N ⇒ M.M ⇒ M D.M ⇒ M D.M D ⇒ DD.M D ⇒ DD.DD
⇒ 1D.DD ⇒ 15.DD ⇒ 15.6D ⇒ 15.64
25
定義 3.3. 文脈自由文法 G = (V, T, S, P ) とは、非終端記号（または変数）とよぶ記
号の有限集合 V 、終端記号とよぶ記号の有限集合 T (T ∩ V = φ) 、開始記号とよぶ
V の元 S 、生成規則とよぶ V × (V ∪ T )∗ の有限集合 P で指定される構造のことで
ある。
上の数の例で説明すると、文法 G1 は
V = {N, M, D},
T = {., 0, 1, 2, · · · , 9},
S=N
P = {(N, M ), (N, .M ), (N, M.M ), (M, D),
(M, M D), (D, 0), · · · , (D, 9)}
となる。ある文法において、生成規則 v → w があるということと、(v, w) ∈ P とは
おなじことである。
定義 3.4. 文脈自由文法 G = (V, T, S, P ) に対して、(V ∪ T )∗ 上の２項関係 ⇒、す
なわち列 w0 は列 w から直接に得られるという関係 ⇒ を次のように定義する。ここ
で、w, w0 ∈ (V ∪ T )∗ とする。
w ⇒ w0 とは、列 w のどれかひとつの記号を G に許されている生成規
則にしたがって書き換えると w0 になるということである。
この文法が自由文脈文法とよばれる所以は、生成規則 A → z があり、記号列 w
のなかに記号 A があるならば A の前後がどのような記号列であろうと、すなわち
文脈に関係なく、A を記号列 z に置き換えることが許されることである。
関係 ⇒ は (V ∪ T )∗ 上の２項関係である。すでに関係 R : A + A から推移的閉関
係 R∗ : A + A を作る方法を説明した。この方法で、関係 ⇒ の推移的閉関係である
∗
(V ∪ T )∗ 上の２項関係 ⇒ が作れる。すなわち、列 w から列 w0 が導出されると
いうことは、w ⇒ w0 であるか、または w1 , w2 , · · · , wn (n ≥ 2) という N ∪ T 上の
記号列があって、w1 = w, wn = w0 , wi ⇒ wi+1 (1 ≤ n − 1) が成り立っていること
である。
定義 3.5. 文法 G について、開始記号 S から文法 G にしたがって導出できる終端
記号列の全体
∗
L(G) = {w | w ∈ T ∗ , S ⇒ w}
を文法 G から生成される言語という。G が文脈自由文法のとき、L(G) は文脈自由
言語と呼ばれる。
例 （回文）。日本語で ’
’シンブンシ ”は前から読んでも後ろから読んでも同じであ
る。このような文を回文という。簡単のため、使用するアルファベットを T = {a, b, c}
とする。T 上のすべての回文を生成する文法 G = (V, T, P, S) は次のように構成さ
26
れる。
V
= {S}
T = {a, b, c}
P = {S → ε, S → a, S → b, S → c, S → aSa, S → bSb, S → cSc}.
さて、前節で有限状態機械を媒介として有限状態言語を定義したが、自由文脈言語
も有限状態機械で実現されないものかな？一般には実現できないことを以下に示す
ことにする。
例 言語 L = {an bn | n ≥ 1} は有限状態言語ではない。
証明 機械 M が言語 L を受容するとする。機械 M の状態の集合 Q の元の個数を k
とする。いま、n > k なる自然数 n をとり、L の元 x = an bn を考える。初期状態 q0
から順次に記号 a を読み込みながら状態を変えていく。x の前半の部分 yi = ai を
読み込み終わったときの状態を pi とする。yn = an を読み込み終わるまでに機械は
状態を
q0 → p1 → p2 → · · · → pn−1 → pn
のように変える。仮定 n > k より、pi = pj (1 ≤ i < j ≤ n) を満たす i, j が存在
する。これは状態 pi からいくつかの a の入力によって pi にもどることを意味する。
その「いくつか」を e 個としよう。a を i 個まで入力して状態 pi にたどり着き、こ
こからさらに a を e 個入力すると pi に戻る。また a を e 個入力すると、pi に戻る。
文字列の残りの部分は最初に pi に入ったときと同じであるから、残りを読み込んで
いけば最終状態に入り、このあとから余計に a が追加された文字列 y = an+2e bn も
機械 M により受容される。これは矛盾である。
27