システムソフトウェア 第３回：２００７年１０月１７日（水）   

2 本日学ぶこと 文法  文字と文字列  無限集合  文法とそのクラス  オートマトン

3 文字 文字とは  文字列を作るもととなる記号のこと．  「 0,1 」や「 a, b, c, … 」などが用いられる． アルファベットとは  文字の集合．  空でない有限集合とする．  例 Σ={0, 1} Σ={a, b, c} すべての ASCII 記号の集合  この授業では，日常使われる意味の「アルファベット」は 忘れてください．

4 文字列 文字列とは  あるアルファベットから選ばれた文字の有限列  例 Σ={0, 1} のとき， 01101, 111, など Σ={a, b, c} のとき， cab, bba, ccccc など 文字列の長さとは  文字列が持つ文字の数（重複は別々に数える）  「文字列が持つ文字の位置の数」という定義もある．  |bba| = 3 のように，絶対値記号で長さを表す． 空文字列とは  0 個の文字からなる文字列のこと．  この授業では， ε と表記する． |ε| = 0 である．

5 文字列の集合 アルファベット Σ に対して  長さ 0 の文字列全体からなる集合は， Σ 0 = {ε}  長さ 1 の文字列全体からなる集合は， Σ 1 = Σ  長さ 2 の文字列全体からなる集合は， Σ 2 = {xy | x, y ∈ Σ}  長さ n の文字列全体からなる集合は， Σ n = {x 1 x 2 …x n | x 1, x 2, …, x n ∈ Σ}  任意の長さの文字列は， Σ * = Σ 0 ∪ Σ 1 ∪ … ∪ Σ n ∪ …  1 以上の長さの文字列は， Σ + = Σ 1 ∪ Σ 2 ∪ … ∪ Σ n ∪ … 注意点  φ≠ {ε} （ 「文字列がない」と「空文字列のみ」は異な る）  Σ * = {ε} ∪ Σ + （「 * 」は 0 回以上，「 + 」は 1 回以上）

6 文字と文字列の注意点 アルファベットは有限集合 文字列は有限長 長さ n の文字列全体からなる集合も，有限集合  |Σ| = s とすると， |Σ n | = s n 任意の長さの文字列全体からなる集合は，無限集合  例えば Σ={0, 1} のとき， Σ * の各要素を ε ， 0, 1, 00, 01, 10, 11, 000, … と並べると，これは非負整数全体の集合と一対一の 対応になる． Σ が空でない有限集合ならば常に成り立つ．

7 文字列の連接・繰り返し x と y を文字列としたとき， x のコピーのあとに y のコ ピーをつないでできる文字列を， x と y の連接といい， xy で表す． 例  x = abcba, y=bcba のとき， xy = abcbabcba  x = 11, y = 00 のとき， xyx =  x = 0011 のとき， x1 = xε = εx = x ．すなわち，任意の文字列と空文字列を連接 すると，空文字列は吸収される（ x = ε のときにも成り立 つ）． |xy| = |x| + |y| ．すなわち，連接した文字列の長さは，も との長さの和となる． x を文字列としたとき， x の n 回繰り返しを x n と表す． x 0 =ε である． x * = { x n | n ≧ 0 } ， x + = { x n | n ＞ 0 } と定義す る．

8 部分文字列 文字列 x, y に対して， y = wxz と表されるならば， x は y の部分文字列であるという．  x, y, w, z のいずれも， ε であってもよい．  「 y を w, x, z に分解する」ともいう．  |y| = |w| + |x| + |z|, |w| ≦ |y|, |x| ≦ |y|, |z| ≦ |y| が成り立つ． 例  101 や 010 は の部分文字列であるが， 11 や 111 は の部分文字列ではない．  abcba は abcba の部分文字列であるが， abdba は abcba の部分文字列ではない．

9 言語 アルファベット Σ ，集合 L に対して L ⊆ Σ * のとき， L を Σ 上 の言語という． 言語の例（ Σ = {0,1} とする）  {ε, 01, 0011, , …}  {ε, 10, 11, 101, 111, 1011, 1101, …} {ε} ， φ ， Σ * も， Σ 上の言語である． Σ 上の言語は，有限集合かもしれないし，無限集合かも しれない． Σ が有限集合であっても，「 Σ 上の言語全体からなる集 合」は（ Σ * よりも大きな）無限集合である．

10 「問題」を「言語」で規定する 例１：「わかやまだいがく」は，正規表現パターン 「わ.* だい」にマッチするか？  Σ = { わ, か, や, ま, だ, い, が, く } とし，  L 1 : 「わ.* だい」にマッチする文字列全体からなる集合  L 2 : 「わかやまだいがく」を部分文字列に持つ文字列全体 からなる集合  を求めた上で， L 1 ∩L 2 ≠φ か否かを判定すればよい． 例２： を 2 進数と見たときの数値 (29) は素数か？  Σ={0,1} に対して，素数の 2 進表現全体からなる集合 PRIME を求め， ∈ PRIME か否かを判定すればよい． 文字列の集合は無限集合になり得るが，「求める」こと はできるの？

11 終端記号と非終端記号（文法の準備として） アルファベットの各文字は終端記号と呼ばれる． アルファベットと別に，文字の集合を定義する．そこに 属する各文字は非終端記号と呼ばれる． 文法は，出発記号と呼ばれる非終端記号から，有限回の 導出により，終端記号のみからなる系列（文字列）を求 めるためのルールを提供する． S10 0S0 S

12 文脈自由文法 形式的には， (V, T, P, S) の四字組で表される．ここで，  V は，非終端記号の集合（空でない有限集合）  T は，終端記号の集合（空でない有限集合）  P は，「 X→α 」で記述される生成規則の集合である．ただ し， X ∈ V であり， α ∈ (V ∪ T) * ，すなわち α は終端記号と非終端記 号による長さ 0 以上の系列である．  S ∈ V であり， S は出発記号と呼ばれる． 例： V = {S}, T = {0, 1}, P = {S→ε, S→0, S→1, S→0S0, S→1S1} ．

13 文脈自由文法における導出 先ほどの例 ({S}, {0, 1}, {S→ε, S→0, S→1, S→0S0, S→1S1}, S) に対して，  S ⇒ 0S0 ⇒ 01S10 ⇒  S ⇒ 0S0 ⇒ 01S10 ⇒ 01ε10 = 0110  S ⇒ 1  S ⇒ ε のようにして， S から ， 0110 ， 1 ， ε などを導出す ることができる． 文脈自由文法 G=(V, T, P, S) に対して， S から導出できる （非終端記号のみからなる）文字列全体の集合を L(G) と書き，文法 G の言語という．  上の例で得られる言語は，アルファベット {0, 1} での回文 （先頭から見ても，末尾から見ても同じになる文字列）で ある．

14 文法 形式的には， (V, T, P, S) の四字組で表される．ここで，  V は，非終端記号の集合 (Variable)  T は，終端記号の集合 (Terminal)  P は，「 α→β 」で記述される生成規則の集合である．ただ し， α ∈ (V ∪ T) * - T * ， β ∈ (V ∪ T) * である． (Production Rule)  S ∈ V であり， S は出発記号と呼ばれる． (Start Symbol) 文脈自由文法は，上で定義した「文法」のうち，生成規 則に制限を加えたものである．  文法により導出できる言語の集合は，文脈自由文法のそれ よりも真に大きい．  ある文法（ ≠ 文脈自由文法）から導出できる言語があると き，それを導出できる文脈自由文法が存在するかもしれな い．

15 正規文法 文法の４字組 (V, T, P, S) と， V, T, S はこれまでと同じ． P は，「 X→a 」または「 X→aY 」で記述される生成規則 の集合である．ただし， X, Y ∈ V, a ∈ T である． 正規表現 "(01)+" に対応する正規文法  V = {S, A}  T = {0, 1}  P = {S→0A, A→1, A→1S}  導出の例 S ⇒ 0A ⇒ 01 S ⇒ 0A ⇒ 01S ⇒ 010A ⇒ 0101

16 文脈依存文法，句構造文法 文脈依存文法  文法の４字組 (V, T, P, S) と， V, T, S はこれまでと同じ．  P は， 「 αXβ→αγβ 」で記述される生成規則の集合である． ただし， X ∈ V ， α, β, γ ∈ (V ∪ T) * 直感的には， α と β ではさまれた「文脈 (context) 」のもと で， X を γ に書き換える． 句構造文法  前述の「文法」のこと．

17 チョムスキー階層（１） 線形拘束オートマ トン （制限有りのメ モリ） 文脈依存文法 メモリの制約を除 いて，現在の計算 機と同等の計算能 力 チューリングマシ ン （無限長のメモリ） 句構造文法 コンパイラ構成の 理論的基礎 プッシュダウン オートマトン （ス タック） 文脈自由文法 正規表現（後方参 照なし） 有限オートマトン （記憶装置がない） 正規文法 備考機械文法 文脈依存言語 句構造言語 文脈自由言語 正規言語 言語

18 チョムスキー階層（２） 言語全体 句構造言語 文脈依存言語 文脈自由言語 正規言語

19 クラス 集合の集合を，「集合族」または「集合のクラス」とい う．  集合を分類（ classify ）したいときに，「クラス」が好まれ る． 例：文脈自由言語全体の集合を L cf ，回文全体からなる言 語を L とすると，  L ∈ L cf （ L ⊆ L cf ではない）  11 ∈ L

20 オートマトン 入力に対して内部の状態に応じた処理を行う，仮想的な 自動機械．計算機の数学的なモデルである．有限個の 「状態」と，状態と入力によって次の状態が決まる「関 数」を持つ． オートマトンの例  有限オートマトン，プッシュダウンオートマトン，チュー リングマシン，セルオートマトン 英語  automaton ．複数形は automata  「自動化」は， automation

21 有限オートマトン 内部にいくつか（有限個）の状態を持つ．任意の時点で， その中の一つの状態にいる． 外界からの入力に応じて，今いる状態から次の状態へと 遷移する． 一つの開始状態と，一つ以上の終了状態を持つ． 形式的には， 5 字組 (Q,Σ, δ, q 0, F) で表現される（詳細は 省略）．

22 有限オートマトンの例（１） スイッチの状態 "int" の認識 正規表現 10+1(0|1)* オフオン "i""in""int" q1q1 q2q2 開始 押す i "" 開始 nt 0 q2q q0q0 1

23 有限オートマトンの例（２） 「偶数個の 0 と偶数個の 1 を持つ文字列」全体に対応する 有限オートマトンは？ 1 q 偶奇 q 偶偶 q 奇奇 q 奇偶 ホップクロフト，モトワニ，ウルマン著，野崎昭弘，高橋正子，町田元，山崎秀記訳 『オートマトン 言語理論 計算論Ⅰ [ 第 2 版 ] 』, p.56

24 まとめ 形式言語理論により，プログラミングをしたり，アルゴ リズムを考えたりする際の「文字」「文字列」「言語 （文字列のある集合）」の扱いが明確になる．  有限集合か無限集合かは常に注意する． 「言語」と 「言語を導出する形式的なルール（文法）」と 「言語を受理する理論的な機械（オートマトン）」には 対応関係や階層関係がある．