理論計算機科学を読むための数学・証明・アルゴリズム基礎

第9章 形式言語の入口

章間ナビゲーション

この章で使う記号

記号 意味
Σ アルファベット
Σ* Σ 上のすべての有限文字列の集合
ε 空文字列
|w| 文字列 w の長さ
uv 文字列 u と v の連結
L ⊆ Σ* 言語 L は文字列集合である
δ 遷移関数
q0, F 初期状態、受理状態集合

この章で解消する詰まりどころ

形式言語とオートマトンでは、普段の「言語」という言葉とは違う意味で言語を扱います。ここでの言語とは、文字列の集合です。

L ⊆ Σ*

この一行を自然に読めることが、この章の最初のゴールです。

形式言語は、コンパイラ、正規表現、構文解析、計算可能性、複雑性理論に直結します。理論計算機科学の中核へ入る前に、文字列・言語・文法・オートマトンの記法に慣れておく必要があります。

本体教科書で使う箇所

  • 形式言語とオートマトン理論。
  • 計算可能性理論。
  • Turing機械、判定問題、認識可能性。
  • 複雑性理論における言語としての問題表現。
  • プログラム意味論、構文、論理式。

1. アルファベット

アルファベット Σ は、有限個の記号の集合です。

例:

Σ = {0,1}
Σ = {a,b,c}
Σ = {'(', ')'}

アルファベットは必ずしも自然言語の文字である必要はありません。トークン、命令、イベント、状態名なども記号として扱えます。

2. 文字列

文字列は、アルファベットの記号を有限個並べたものです。

Σ = {0,1} のとき、次は文字列です。

0
1
00
1011
ε

ε は空文字列です。長さ0の文字列です。

長さ

文字列 w の長さを |w| と書きます。

|ε| = 0
|0| = 1
|1011| = 4

集合の要素数 |A| と同じ記号を使うので、文脈で区別します。

3. 連結

文字列 u と v の連結を uv と書きます。

例:

u = 10
v = 011
uv = 10011

空文字列は連結の単位元です。

εw = w
wε = w

連結は一般に可換ではありません。

uv = vu

とは限りません。たとえば u=0, v=1 なら、uv=01, vu=10 です。

4. Σ*

Σ* は、アルファベット Σ 上のすべての有限文字列の集合です。

Σ = {0,1} のとき、

Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, ...}

です。

Σ* は無限集合です。ただし、各文字列は有限長です。

5. 言語

形式言語とは、Σ* の部分集合です。

L ⊆ Σ*

例:

L1 = { w ∈ {0,1}* | w は 1 を偶数個含む }
L2 = { 0^n1^n | n >= 0 }
L3 = { w ∈ {'(',')'}* | w は正しく対応した括弧列 }

言語は有限でも無限でも構いません。

6. 文字列集合の記法

0^n

0^n は、記号 0 を n 個並べた文字列です。

0^0 = ε
0^1 = 0
0^3 = 000

{0^n1^n | n >= 0}

これは次の言語です。

{ ε, 01, 0011, 000111, ... }

n=0 のとき 0^0 1^0 = ε です。

注意

0^n1^n は数値の累乗ではありません。文字列の繰り返しです。

7. 言語演算

言語は集合なので、集合演算を持ちます。

L1 ∪ L2: 和集合
L1 ∩ L2: 共通部分
Σ* \ L: 補集合

さらに、文字列特有の演算があります。

連結

L1L2 = { uv | u∈L1, v∈L2 }

Kleene star

L* = { ε } ∪ L ∪ LL ∪ LLL ∪ ...

つまり、L の文字列を0回以上連結したもの全体です。

8. 正規表現の入口

正規表現は、特定の規則で言語を記述する方法です。

基本構成:

∅        空言語
ε        空文字列だけの言語
文字 a   {a}
R|S      和
RS       連結
R*       0回以上の繰り返し

例:

(0|1)*

は、すべてのビット列を表します。

0(0|1)*

は、0で始まるビット列を表します。

9. 文法

文法は、文字列を生成する規則です。

代表的には、次の構成で定義します。

G = (V, Σ, R, S)
  • V: 非終端記号の集合。
  • Σ: 終端記号の集合。
  • R: 生成規則の集合。
  • S: 開始記号。

例

括弧列の文法:

S -> ε
S -> (S)
S -> SS

この文法は、正しく対応した括弧列を生成します。

10. 導出

導出とは、開始記号から生成規則を適用して文字列を作る過程です。

例:

S => (S) => (SS) => (()S) => (())

実際には、どの規則をどの非終端記号に適用したかを明示する必要があります。

11. 構文木

構文木は、導出の構造を木として表したものです。

プログラミング言語では、ソースコードをトークン列として読み、文法に従って構文木を作ります。したがって、形式言語はコンパイラやインタプリタの基礎です。

12. 有限オートマトン

有限オートマトンは、有限個の状態を持つ機械です。入力文字を左から右へ読み、状態を更新します。

決定性有限オートマトン、DFA は次で定義されます。

M = (Q, Σ, δ, q0, F)
  • Q: 状態集合。
  • Σ: 入力アルファベット。
  • δ: 遷移関数。δ: Q × Σ -> Q。
  • q0: 初期状態。
  • F: 受理状態の集合。

入力を読み終えた時点の状態が F に含まれていれば、その入力を受理します。

13. DFA の例

1 を偶数個含むビット列の言語を考えます。

L = { w ∈ {0,1}* | w に含まれる 1 の個数は偶数 }

状態は2つで十分です。

q_even: これまで読んだ 1 の個数が偶数
q_odd : これまで読んだ 1 の個数が奇数

遷移:

δ(q_even, 0) = q_even
δ(q_even, 1) = q_odd
δ(q_odd, 0)  = q_odd
δ(q_odd, 1)  = q_even

初期状態は q_even です。受理状態も q_even です。

14. 非決定性の入口

非決定性有限オートマトン、NFA では、同じ状態・同じ入力記号に対して複数の遷移先があり得ます。また、入力を読まずに状態を変える ε 遷移を許す定義もあります。

非決定性は「ランダム」ではありません。NFA が受理するとは、受理状態に到達する経路が少なくとも1つ存在する、という意味です。

この「存在する経路」という考え方は、複雑性理論の NP の直観にも接続します。

15. 問題を言語として見る

理論計算機科学では、判定問題を言語として表すことが多いです。

例:

PRIME = { enc(n) | n は素数 }

ここで enc(n) は整数 n の符号化です。

判定問題「n は素数か」は、入力文字列が言語 PRIME に属するかを判定する問題として見られます。

この見方により、計算可能性や複雑性を「どの言語がどの計算モデルで判定できるか」として議論できます。

16. 構造帰納法との接続

文字列は再帰的に定義できます。

ε は文字列である。
w が文字列で a∈Σ なら、wa も文字列である。

このような再帰的構造に対する証明では、構造帰納法を使います。

例

任意の文字列 u, v について、

|uv| = |u| + |v|

を証明したい場合、v の構造に関する帰納法を使えます。

17. よくある誤り

誤り1: Σ* と Σ を混同する

Σ は記号の集合です。Σ* は文字列の集合です。

誤り2: ε と ∅ を混同する

ε は長さ0の文字列です。∅ は要素を持たない集合です。

{ε}

は空ではありません。要素を1つ持つ集合です。

誤り3: 非決定性を確率と混同する

NFA の非決定性は、確率的に遷移することではありません。受理経路が存在するかどうかのモデルです。

誤り4: 正規表現と実用正規表現を同一視する

理論上の正規表現と、プログラミング言語やツールの正規表現は完全には一致しません。実用正規表現には後方参照など、理論上の正規言語を超える機能が入る場合があります。

18. 接続問題

接続1: 構文解析

プログラムの構文は、トークン列の言語として扱えます。パーサは、入力が文法で生成される文字列かを判定し、構文木を作ります。

接続2: 計算可能性

Turing機械は、言語を認識または判定する機械として定義できます。ある問題が計算可能かどうかは、対応する言語が判定可能かどうかとして議論されます。

接続3: 複雑性理論

P, NP などの計算量クラスは、言語のクラスとして定義されることが多いです。

章末チェック

次を説明できれば、この章の最低ラインは満たしています。

  • アルファベット、文字列、空文字列、言語の定義。
  • Σ* の意味。
  • ε と ∅ の違い。
  • 連結と言語演算。
  • 正規表現の基本構成。
  • 文法、導出、構文木の役割。
  • DFA の5要素定義。
  • 非決定性がランダムではないこと。
  • 判定問題を言語として表す考え方。

次に読む章

Edit this page on GitHub