東京工科大学 コンピュータサイエンス学部 亀田弘之

Presentation on theme: "東京工科大学 コンピュータサイエンス学部 亀田弘之"— Presentation transcript:

1 東京工科大学 コンピュータサイエンス学部 亀田弘之
形式言語とオートマトン2008 ー第10日目ー 東京工科大学 コンピュータサイエンス学部 亀田弘之 この資料は暫定的なものです！

2 確認(1) 有限オートマトン(FA) FAの定義と記述法 FAの種類 言語認識能力はどのFAでも同じ。
テープ上を一方向に動くヘッド （テープ上の記号を順次読みながら内部状態を遷移） M = <K, Σ, δ, q0, F> 　（５つ組） 状態遷移図 様相（configuration） FAの種類 決定性FA（DFA） 非決定性FA（ε遷移のあるものとないもの） 言語認識能力はどのFAでも同じ。 正規言語（正規表現）を認識

3 確認（２） 正規表現を認識するFAの存在とその構成法 正規表現αが与えられる。 正規表現αに対して、ε-NFA を構成する。
ε-NFA をDFAに書き換える。 DFAを状態数最少のDFA(Min-DFA)に書き換える。 Min-DFAをシミュレートするプログラムを作成する。 (上記５はまだ説明していません！)

4 確認（３） プッシュダウンオートマトン(PDA) スタックの定義 PDAの定義と記述法
データ構造： ・配列（またはアレイ） ・リスト ・スタック ・キュー　など プッシュダウンオートマトン(PDA) スタックの定義 スタックの構造と動作（pop-up と push-down） LIFO (Last-In First-Out) 型のメモリ PDAの定義と記述法 テープ上を一方向に動くヘッド＋スタックメモリ （テープの記号を順次読み、スタック上の記号を準じ読み書きしながら内部状態を遷移） M = < K, Σ, Γ,δ, q0, Z0, F > 　（７つ組） 状態遷移図 様相（configuration）

5 確認（４） スタックとPDAのイメージ図 Pop up Push down LIFO (Last In First Out)
最後に入れたものが最初に取り出される。

6 確認（５） プッシュダウンオートマトン(PDA) PDAの種類 言語認識能力はNPDAの方が高い。
決定性プッシュダウンオートマトン Deterministic pushdown automaton (DPDA) 非決定性プッシュダウンオートマトン Nondeterministic pushdown automaton (NPDA) 言語認識能力はNPDAの方が高い。 FAは正規言語（正規表現）を認識 NPDAは文脈自由言語を認識 DPDAよりもNPDAの方が言語認識能力大

7 確認（６） チューリングマシン(Turing Machine; TM) TMの定義と記述法 TMの種類 言語認識能力はどのTMでも同じ。
テープ上を左右どちらにも動けるヘッド （テープ上の記号を順次読み、テープ上に時として記号を書き込みながら、そのたびごとに内部状態を遷移） M = < K, Γ, Σ, δ, q0, B, F > 　（７つ組） 状態遷移図 様相（configuration） TMの種類 決定性TM（DTM） 非決定性TM(NTM) 言語認識能力はどのTMでも同じ。 句構造言語（句構造文法に適った文）を認識

8 ここまでで分かったこと オートマトンとはどういうもので、どんな種類があり、どんな風に動作するのか？ はわかった。
さて、オートマトンの意義は何？ オートマトンって結局なんの役に立つの？ 学問的意義は？

9 でも、形式言語ってのは役に立つものなの？
オートマトンと形式言語 オートマトンは形式言語と密接な関係がある。 そこで次に「形式言語」について学ぼう。 でも、形式言語ってのは役に立つものなの？

10 第２部 形式言語 応用分野： 自然言語処理・音声処理 カナ漢字変換システム 機械翻訳システム 自動通訳システム プログラミング言語とその処理
第２部　形式言語 応用分野： 自然言語処理・音声処理 カナ漢字変換システム 機械翻訳システム 自動通訳システム プログラミング言語とその処理 コンパイラ設計 プログラミング言語設計 その他

11 ここで第１回目の講義資料を 見返してみよう！

12 そもそも言語とはなにか？ オートマトンとは何か？

13 そもそも言語とはなにか？ オートマトンとは何か？ （CSでは言語をどうとらえるのか？） ＝＞言語理論

14 「形式言語とオートマトン」の授業の 概略を一気に眺めてみよう！

15 形式言語とオートマトン Formal Languages and Automata
平成20年度開講科目 第１部 2008年4月14日に使用した資料（一部改変あり）

16 オートマトンとは Automaton (pl. automata) Αυτοματον(ギリシア語) （pl. Αυτοματα）
一般的な意味：自動機械

17 ! ? I have a book. 英語だ！

18 Tut mir Leid. ???!

19 Automaton 記号列 Aha!

20

21 一般化 単語の一般化 I ⇔x1, have ⇔x2, a ⇔ x3, book ⇔ x4,
. ⇔ x5, ・・・, kanete ⇔ xn-1, ;⇔ xn

22

23 言語の形式的定義 単語ｗ： X1, X2, X3, ・・・, Xn （はじめに単語ありき） 語彙V (Vocabulary) ： 単語の集合
V = { X1, X2, X3, ・・・, Xn } (有限集合) 文(sentence)： 単語の並び（単語の列） （注） Vの要素( X1 や X2 など)は単語 S1 = Xa Xb Xc Xd など でも何でも良いわけではない。

24 例 語彙V={ birds, fly } 文:={ birds, fly,
birds birds, birds fly, fly birds, fly fly, birds birds birds, birds birds fly, birds fly birds, fly birds birds, birds fly fly, fly birds fly, fly fly birds, … } （無限個存在する！）

25 考察 文は無限個存在する。 英語として意味のあるものとそうでないものとが混ざっている。 （単語は有限個）
⇒ 英語として意味のある文をすべて集めた集合は、 １つの言語L（今の場合は英語）を定める。 ⇒ 意味があるものとないものとを区別したい。 つまり、任意の文に対して、それが言語Lの文か 否かを判定したい。

26 そんなことできるのだろうか？ でも、人間はやっているよ！ じゃあ、できるんだね！（信念） 自動機械（オートマトン）を作ってみよう！

27 作成のためのアイデア はじめに言語Lの文すべてを知っているならば、下記のような機械ができる。 S1は言語Lの文だよ！ 文S1 オートマトン
S1　S2　S3 … Sn

28 問題点１ でも、 「言語Lの文すべてを知っている」 なんて、不可能だよ！
例：「２００8年6月23日、形式言語とオートマトンの授業が、講実4０3教室で、パワーポイントを用いて行われた。」　という文をあなたは事前に知っていましたか？

29 問題点２ もし何らかの方法により、事前に言語Lのすべての文を知っていたとしても．．． s = get_sentence();
停止しないことがある！！！ s = get_sentence(); if ( s ∈ Lの文の集合 ) then s は　Lの文である else s は　Lの文ではない end if

30 それではどうしようか？！

31 ここまでのまとめ 言語 文法の必要性 オートマトン 意味のある文の集合
ある言語（例えば日本語）の文すべてを あらかじめ知っているなんてことは不可能！ オートマトン ある文が対象としている言語Lの文なのかを自動判定する装置

32 どうも文法が大切らしい。 もう少し文法について学んでみよう！
どうも文法が大切らしい。 もう少し文法について学んでみよう！

33

34 形式言語とオートマトン Formal Languages and Automata
平成20年度開講科目 第２部

35 文法とは？ その言語を使用する人たちが皆で守り従わなければならない言語に関する規則の総体。

36 文法は「言語政策」・「言語教育」のために重要。
現在使われている日本語に関する言語規則はどうなっているのか？ このような観点から本授業では文法を考える。 文法は、機械翻訳・電話通訳などの実現のためにも重要である。

37 文法とは？ 一般的な定義： 規範としての文法 言語現象記述のための文法

38 規範としての文法（１） 「何々でなければならない」規則集 「ら抜きことば」は間違っている 若者語はけしからん！
この考え方の根底には、「言語とは社会的なものであり、みながその規約を守らなければ、言語は適切に機能しない。」という思想がある。 従って、「この事実と言語（文法）そのものを、規範として学校で教えるべきである。」という具合になる。

39 規範としての文法（２） 規範文法とは： その言語を使用する人たちが皆で守り従わなければならない言語における規則の総体。

40 規範文法への批判（１） でも、ら抜き言葉は多くの人に使われていますよ！ これって、もう日本語ではないの？
今の日本語の中には、かつての日本語では使われていないものもありますよね。 言語は変化しますよね。

41 規範文法への批判（２） 言語変化の実例： 「進歩する」（１００年ほど前は「進歩をする」） 「更なる進化」（２０年ぐらい前は「更に進歩する」）
It’s bad! It’s cool. など

42 規範文法も「言語政策」・「言語教育」のために重要だが、現在使われている日本語に関する言語規則はどうなっているのか？
このような観点からのものが、「言語現象記述のための文法」である。 このような文法は、機械翻訳・電話通訳などの実現のために重要である。

43 さらにもう一歩考えをすすめて．．． 「あらゆる言語に共通の言語規則はあるのだろうか？」と考えるのが、「一般普遍文法」である。 これについて、少し詳しく話すと．．．

44 一般普遍文法（１） 第１回目のオートマトンの説明を思い起こすと… すべての子供はやがて言葉を話しはじめる。
日本人のこどもも、エスキモーのこどもも、 エジプトのこどもも… 人種・民族・地域等にかかわらず話し始める。 でも、日本人は日本語、エスキモー人はエスキモー語をしゃべり始める。Why?

45 Because… その言語をしゃべる環境で育ったから。 環境が習得言語を決める。 でも、なぜ基本的に人は皆しゃべり始めるの？
ミミズはしゃべらないのに。 それは、．．．

46 すべてのヒトは、 言語に依存しない普遍的な処理能力をもった装置(device)を生得的に持っており、
ホントにしゃべれるようになるのかなぁ すべてのヒトは、 言語に依存しない普遍的な処理能力をもった装置(device)を生得的に持っており、 個別言語に関する知識は後天的に獲得されるからだ。 これが私の基本的考えです。 僕にもこんな装置がほしいなぁ… 写真の出典：Wikipediaより

47 その知識は、「文法」という形で獲得される。
Chomskyはそのように考えた。 それでは彼の考えを見てみよう。

48 文法の定義 文法G=（ Vn, Vt, P, S ）： ただし、 重要 Vn: 非終端記号の集合 Vt: 終端記号の集合

49 文法 文法G=（ Vn, Vt, P, S ）： ただし、 Vn: 非終端記号の集合 <= 構文木構成要素の集合

50 例１-1 G=(Vn, Vt, P, S) Vn = { S, NPs, NPo, VP, PN, DET, N }
Vt = { I, You, have, throw, a, the, book, ball } P = { ①：S → NPs VP, ②：NPs → PN, ③：PN → I, ④：PN → You, ⑤：NPo → DET N, ⑥：VP → V NPo, ⑦：DET → a, ⑧：DET → the, ⑨：N → book, ⑩：N → ball, ⑪：V → have, ⑫：V → throw }

51 例１-2 S => NPs VP by ① => PN VP by ② => I VP by ③
=> I V NPo by ⑥ => I throw NPo by ⑫ => I throw DET N by ⑤ => I throw a N by ⑦ => I throw a ball by ⑩

52 例１-2 S => NPs VP by ① => PN VP by ② => I VP by ③
開始記号 適応規則 S => NPs VP by ① => PN VP by ② => I VP by ③ => I V NPo by ⑥ => I throw NPo by ⑫ => I throw DET N by ⑤ => I throw a N by ⑦ => I throw a ball by ⑩ 非終端記号 終端記号

53 例１-2 S => NPs VP by ① => PN VP by ② => I VP by ③
=> I V NPo by ⑥ => I throw NPo by ⑫ => I throw DET N by ⑤ => I throw a N by ⑦ => I throw a ball by ⑩ 終端記号のみの列 文

54 例１-2に対する問題 これは木(tree)として記述せよ。 この文法Gにより生成される文をすべて列挙せよ。

55 言語の定義 言語Lとは、文法Gにより生成されるあらゆる文の集合のこと。 つまり、L＝L(G)。

56 問題（Palindrome） Palindromeのみを生成する文法を示せ。 ただし、 G=( Vn, Vt, P, S )
Vn = { S }, Vt = { a, b, c } とする。

57 ヒント Palidromeの性質 ε, a, b, c はPalindrome。 ｗがPalindromeならば、 xwx (x ∈ Vt)

58 文法の分類

59 オートマトンと言語 Automaton & Languages
平成１６年度開講科目 ３回目

60 ここまでのまとめ 人間の頭の中には、言語処理装置がある。 すべての文を記憶しているわけではない。 文法として記憶している。 文法とは何か？
規範文法(Prescriptive Grammar) 記述文法(Descriptive Grammar) 形式文法と形式言語

61 形式文法と形式言語 文法G = （ Vn, Vt, P, S ）： 言語L = L(G) = { x | S =*> x } ただし、
Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {α→β| α, β ∈ (Vn∪Vt)*} S: 開始記号(S∈Vn) 言語L = L(G) = { x | S =*> x } ただし、S => ・・・ => x　∈ Vt

62 形式文法と形式言語（例） 文法G = （ Vn, Vt, P, S ）： 言語L = L(G) = { x | S =*> x }
Vn ={S}, Vt={} P={ } 言語L = L(G) = { x | S =*> x }

63 言語の階層（重要） 言語は文法の種類に応じて、階層構造をなしている。 句構造言語 ⇔ 句構造文法 文脈依存言語 ⇔ 文脈依存文法
句構造言語 ⇔ 句構造文法 文脈依存言語 ⇔ 文脈依存文法 文脈自由言語 ⇔ 文脈自由文法 正規言語 ⇔ 正規文法 一般的 特殊的 Chomsky階層(Chomsky Hierarchy)とも言う。

64 句構造文法 (Phrase-Structure Grammar; PSG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {α→β| α, β ∈ (Vn∪Vt)*} S: 開始記号(S∈Vn)

65 句構造文法 (Phrase-Structure Grammar; PSG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {α→β| α, β ∈ (Vn∪Vt)*} S: 開始記号(S∈Vn)

66 句構造文法 (Phrase-Structure Grammar; PSG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {α→β| α, β ∈ (Vn∪Vt)*} S: 開始記号(S∈Vn) ここに制限が付くと他の文法になる。

67 文脈依存文法 (Context-Sensitive Grammar; CSG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {αXβ→αγβ| α, β ∈ (Vn∪Vt)*, X∈Vn, γ∈ (Vn∪Vt)+ } S: 開始記号(S∈Vn)

68 文脈自由文法 (Context-Free Grammar; CFG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 { X→α| α∈ (Vn∪Vt)*} S: 開始記号(S∈Vn)

69 正規文法 (Regular Grammar; RG)
文法G = （ Vn, Vt, P, S ）： Vn（非終端記号の集合）: 0 < #Vn < +∞ Vt: 終端記号の集合: 0 < #Vt < +∞ P: 書き換え規則の集合 {X→aY, X→b| X,Y∈Vn, a,b ∈ Vt*} S: 開始記号(S∈Vn)

70 生成規則部分の比較 PSG: α→β CSG: αXβ→αγβ CFG: X→α RG: X→aY, X→b ただし、
α，β∈V* ・γ∈V+ X, Y∈Vn ・a, b∈Vt ・V=Vn∪Vt

71 生成規則部分の比較 PSG: α→β CSG: αXβ→αγβ CFG: X→α RG: X→aY, X→b ただし、
α，β∈V* ・γ∈V+ X, Y∈Vn ・a, b∈Vt ・V=Vn∪Vt

72 生成規則部分の比較 PSG: α→β CSG: αXβ→αγβ CFG: X→α RG: X→aY, X→b ただし、
α，β∈V* ・γ∈V+ X, Y∈Vn ・a, b∈Vt ・V=Vn∪Vt

73 生成規則部分の比較 PSG: α→β CSG: αXβ→αγβ CFG: X→α RG: X→aY, X→b ただし、
α，β∈V* ・γ∈V+ X, Y∈Vn ・a, b∈Vt ・V=Vn∪Vt

74 生成規則部分の比較 PSG: α→β CSG: αXβ→αγβ CFG: X→α RG: X→aY, X→b ただし、
α，β∈V* ・γ∈V+ X, Y∈Vn ・a, b∈Vt ・V=Vn∪Vt

75 Chomsky階層 重要 PSG CSG CFG RG

76 言語の包含関係 L（PSG) ⊃ L(CSG) ⊃ L(CFG) ⊃ L(RG) このうち、大切なのはCFGとRG。

77 CFGとRG CFG（文脈自由文法）： RG（正規文法）： プログラミング言語設計 コンパイラの構文解析
自然言語処理（機械翻訳・仮名漢字変換） RG（正規文法）： 正規表現（検索・コンパイラの語彙解析）

78 CFGの特徴 CFGには標準形がある。 導出の過程を木で表現できる（導出木の存在）。 解析手法が豊富に知られている。
自然言語処理に部分的に適用できる。 プログラミング言語設計に利用されている。

79 １．CFGの標準形 Chomskyの標準形 Greibachの標準形

80 Chomskyの標準形 任意のCFGにおける書き換え規則群Pは、A→BC　または　A→a　という形だけで表現できる。　

81 Greibachの標準形 任意のCFGにおける書き換え規則群Pは、A→aα　という形だけで表現できる。ただし、X∈Vn, a∈Vt, α∈Vn*。　

82 Chomskyの標準形への変換方法 （次回のお楽しみ。事前に予習すると理解しやすいですよ。）

83 ２．導出木 導出木とは 例： 導出の過程を木構造で表現したもの。 S => SJ VP => Tom V ADV
=> Tom ran fast S SJ VP ADV V Tom ran fast

84 ３．解析手法 CKY法(Cocke-Kasami-Younger method) Early法(Early’s algorithm)
Chart法(Chart algorithm) 優先順位文法法 LK ( R ) 法 LR( k ) 法 LALR( k ) 法 SLR( k ) 法 LL( k ) 法　　　　などなど

85 解析手法は重要なので後日あらためて取り上げます。
機械翻訳・通訳電話などの自然言語処理 コンパイラ などで応用されている。

86 参考文献 文法： 英語学概論　－三大文法の流れと特徴－，松井千枝，朝日出版(1980).

87 ここまでのまとめ 言語には階層がある（Chomsky階層） 正規言語（正規文法）は語句解析に深い関係がある。
文脈自由言語（文脈自由文法）は構文解析に深い関係がある。

88 もう少し話を進めましょう！

89 文法と言語とオートマトン 句構造文法(PSG) 文脈依存文法(CSG) 文脈自由文法(CFG) 正規文法(RG)

90 言語の階層（重要） 言語は文法の種類に応じて、階層構造をなしている。 句構造言語 ⇔ 句構造文法 文脈依存言語 ⇔ 文脈依存文法
句構造言語 ⇔ 句構造文法 文脈依存言語 ⇔ 文脈依存文法 文脈自由言語 ⇔ 文脈自由文法 正規言語 ⇔ 正規文法 一般的 特殊的 Chomsky階層(Chomsky Hierarchy)とも言う。

91 Chomsky階層 重要 PSG CSG CFG RG

92 文法と言語とオートマトン -----------------------------------------------------
文　　法 　　処理装置 句構造文法(PSG) ⇔ ？ 文脈依存文法(CSG) ⇔ ？ 文脈自由文法(CFG) ⇔ ？ 正規文法(RG) ⇔ ？

93 文法と言語とオートマトン 文　　法 　　処理装置 句構造文法(PSG) ⇔ Turing 機械 文脈依存文法(CSG) ⇔ 線形有界オートマトン 文脈自由文法(CFG) ⇔ プッシュダウンオートマトン 正規文法(RG) ⇔ 有限オートマトン

94