システムソフトウェア 第３回：２００７年１０月１７日（水）   . 2 本日学ぶこと 文法  文字と文字列  無限集合  文法とそのクラス  オートマトン.

Presentation on theme: "システムソフトウェア 第３回：２００７年１０月１７日（水）   . 2 本日学ぶこと 文法  文字と文字列  無限集合  文法とそのクラス  オートマトン."— Presentation transcript:

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

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

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

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

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

7 7 文字列の連接・繰り返し x と y を文字列としたとき， x のコピーのあとに y のコ ピーをつないでできる文字列を， x と y の連接といい， xy で表す． 例  x = abcba, y=bcba のとき， xy = abcbabcba  x = 11, y = 00 のとき， xyx = 110011  x = 0011 のとき， x1 = 00111 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 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 は 10101 の部分文字列であるが， 11 や 111 は 10101 の部分文字列ではない．  abcba は abcba の部分文字列であるが， abdba は abcba の部分文字列ではない．

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

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

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

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

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

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

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

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

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

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

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

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

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

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