形式言語とオートマトン2013 第１回目 -Formal Languages & Automata-

Presentation on theme: "形式言語とオートマトン2013 第１回目 -Formal Languages & Automata-"— Presentation transcript:

1 形式言語とオートマトン2013 第１回目 -Formal Languages & Automata-
東京工科大学 コンピュータサイエンス学部 担当教員：亀田弘之

2 I. はじめに 科目概要 CS学部前期科目 担当教員：亀田弘之（Hiroyuki Kameda） オフィスアワー
専門分野：思考と言語、自然言語処理、機械学習、 情報検索、Webマイニング、ソフトウェア教育、クラウド図書館、高次脳機能のシステム的解明と その工学的応用（高次脳機能障害リハビリテーション用ゲームソフトウェア開発）、応用ゲーム学など オフィス：研A６階601 オフィスアワー 火曜日３時限(13:15～14:45)。 その他の場合はメールで予約してください。

3 授業概要 日本語や英語も、JavaやCなどのプログラミング言語もともに“言語”である。それではこれらの言語にはどのような共通点・相違点があるのだろうか？　はたまた、人間が日本語や英語を理解し行動する処理と、コンピュータがプログラミング言語を理解し実行する処理の間には何か関係があるのだろうか？　

4 授業概要（２） 本講義では、学生諸君がこの疑問に対して明快に答えることができ、かつ、“コンピュータ”および“計算”の本質を知るきっかけを得ることができることを目指して、“形式言語”という概念を導入し一段高い観点から言語を概観し、言語処理装置でありかつ今日のコンピュータの理論モデルでもあるオートマトンについて詳しく学ぶことを目指す。

5 授業概要（３） 学習目標は、 言語を処理する自動機械（オートマトン）の種類・仕組み・動作を自分の言葉で説明できること、
言語には階層がある、プログラミング言語が文脈自由言語と深くかかわっていることを理解すること、さらには、 言語とオートマトンの密接な相互関係を説明できること、 オートマトンの言葉を用いて計算とは何かを説明できること、である。

6 （参考）学びの深さ そんな用語は知らない。見たこともない。 その用語を見たことがある。 その用語の意味を一応説明できる。
その用語の意味を理解している。 その用語の意味を自分の言葉で説明できる。 与えられた状況の下で，その用語を利用できる。 状況にかかわらず，臨機応変にその用語を利用できる。

7 成績評価 前提：授業に出席していること （欠席する場合は，事前にメール等で 連絡すること） 評価ポイント 達成度評価方法
前提：授業に出席していること 　　　　（欠席する場合は，事前にメール等で 　　　　　連絡すること） 評価ポイント 学習目標が達成されていること 達成度評価方法 定期試験 レポート

8 学び方のポイント 前提となる科目はないが，数学的なものの言い方に慣れること。 例を通して理解すること。 復習は必ずすること。
予習は指示のあったときだけで十分。 提出期限を守る。 レポートは復習の意味もあるので，必ず取り組むこと。

9 II.　イントロダクション

10 Why we study FL & Automata?
ディジタル回路設計・分析ソフトウェア コンパイラの字句解析ソフトウェア コンパイラの構文解析ソフトウェア 大規模テキスト処理ソフトウェア 通信プロトコル等の検証ソフトウェア Bioinformatics アミューズメントゲーム　など

11 C言語によるプログラム例 #include <stdio.h> main( ){ float kingaku;
float teika = 100, shouhizei = 0.05; kingaku = teika + teika*shouhizei; printf(“%f\n”, kingaku); } プログラミング言語の設計、その言語で書かれたプログラムの意味の解析などはFLやAutomataの理論に深く関係している。一見役に立っていないようでも、本当にすごく役立っている学問分野です。

12 ここからしばらくは，聞くだけでOKです。
ちょっと先走りを．．． 東京工科大学CS学部で開講されている 授業「言語プロセッサ」（３年後期の授業）をちょっと覗いてみよう。 ここからしばらくは，聞くだけでOKです。

13 数式の例 A = B* C/A Area = 2*3.14*R

14 数式の解析 kingaku = teika + teika * shouhizei

15 数式の解析 読み込み（文字列として） “kingaku = teika + teika * shouhizei”
要素(token)の切り出し “kingaku”, “=“, “teika”, “+”, “*”, “shouhizei” 要素の相互関係の分析 ＝ kingaku teika + shouhizei *

16 ソース言語 読み込み 字句解析 分析 構文解析 中間語生成 合成 コード生成 目的言語

17 数式の解析 読み込み（文字列として） “kingaku = teika + teika * shouhizei”
要素(token)の切り出し “kingaku”, “=“, “teika”, “+”, “*”, “shouhizei” 要素の相互関係の分析 ＝ kingaku teika + shouhizei *

18 数式の解析 読み込み（文字列として） “kingaku = teika + teika * shouhizei”
要素(token)の切り出し “kingaku”, “=“, “teika”, “+”, “*”, “shouhizei” 要素の相互関係の分析 ＝ kingaku teika + shouhizei *

19 数式の解析 読み込み（文字列として） “kingaku = teika + teika * shouhizei”
要素(token)の切り出し “kingaku”, “=“, “teika”, “+”, “*”, “shouhizei” 要素の相互関係の分析 ＝ kingaku teika + shouhizei *

20 数式の解析 読み込み（文字列として） 読み込み “kingaku = teika + teika * shouhizei”
要素(token)の切り出し　 字句解析 “kingaku”, “=“, “teika”, “+”, “*”, “shouhizei” 要素の相互関係の分析　構文解析 ＝ kingaku teika + shouhizei *

21 数式の解析 読み込み 字句解析 構文解析 ファイルからの入力技法 有限オートマトンの理論 正規文法（正規言語） 正規表現
線形有界オートマトン理論 文脈自由文法（文脈自由言語）

22 前提知識 形式言語とオートマトン プログラミング技法 前期科目「形式言語とオートマトン」 抽象的・論理的な思考への慣れ
今までいろいろと習ってきましたよね！ 基本的な知識があれば一応OK ファイルの入出力が難しい人はいるかも…

23 学んで得られるもの 言語理論とオートマトン プログラミング技法 抽象的・論理的な思考への慣れ ソフトウェア分野における基本的概念
正規表現 etc. プログラミング言語へのより深い理解 プログラミング技法 プログラミング力（知識）アップ 洗練されたアルゴリズムの理解　　などなど

24 One Rank Up のICTエンジニアを目指そう！
言語プロセッサ関連は、コンピュータサイエンスの英知が集積されている！ この授業を取った人は先見の明がある！ One Rank Up のICTエンジニアを目指そう！

25 それでは基礎知識の話から (今日の本題です。) こんな風に話が続きます… 後期（月・３限）の授業をお楽しみに！

26 さて、本授業の内容に戻りましょう。 形式言語とオートマトン

27 III.　今日の講義

28 そもそも言語 とは何か？ オートマトン とは何か？
What is language? What is automaton? 講義名： 「形式言語とオートマトン」

29 そもそも言語とはなにか？ オートマトンとは何か？ （CSでは言語をどうとらえるのか？） ＝＞言語理論
一言ボックス： ことば　と　言語 　ことば（言葉）とは、体系としての言語とそれを操る処理能力を総称したもの。 Langue（ラング）、Langage（ランガージュ）そしてParole（パロール） 　フランス語では、体系としての言語をラング、言語能力をランガージュ、個々の発話されたものをパロールといって区別する。（参考：ソシュールの言語学）

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

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

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

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

34 Tut mir Leid. ???!

35 Automaton 記号列 Aha!

36

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

38

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

40 例 語彙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, … } （無限個存在する！）

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

42 そんなことできるのだろうか？

43 茜草指武良前野逝標野行野守者不見哉君之袖布流
そんなことできるのだろうか？ 茜草指武良前野逝標野行野守者不見哉君之袖布流 これ何？

44 そんなことできるのだろうか？ Es war ein König in Thule, Gar treu bis an das Grab, Dem sterbend seine Buhle einen goldnen Becher gab. これ何？

45 今日はいい天気ですね。 今日は天気いいですね。 いい天気は今日ですね。 天気は今日いいですね。 いい天気です今日はね。
そんなことできるのだろうか？ 今日はいい天気ですね。 今日は天気いいですね。 いい天気は今日ですね。 天気は今日いいですね。 いい天気です今日はね。 ね、いい天気です今日は。 今日は天気いいねです。 わかる？

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

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

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

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

50 参考メモ 自然数の集合N={ 0, 1, 2, 3, 4, ・・・, k, ・・・ } の中に、π の値が含まれているかを調べるアルゴリズムを考えてみた。 0 ≠ π，1 ≠ π，2 ≠ π，3 ≠ π，・・・ いつまでたっても止まらない！

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

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

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

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

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

56 文法は「言語政策」・「言語教育」のために重要。
現在使われている日本語に関する言語規則はどうなっているのか？ このような観点から本授業では文法を考える。 文法は、機械翻訳・電話通訳などを 実現するためにも重要である。 プログラミング言語の設計やそれで書かれたプログラムの処理にとっても重要である。

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

58 一般普遍文法（１） 前述のオートマトンの説明を思い起こすと… すべての子供はやがて言葉を話しはじめる。
日本人のこどもも、フィンランドのこどもも、 モロッコのこどもも… 人種・民族にかかわらず話し始める。 でも、日本人は日本語、フィンランド人はフィンランド語をしゃべり始める。Why?

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

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

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

62 ここからが大切

63 文法の定義 文法G=（ Vn, Vt, P, S ）： ただし、 Vn: 非終端記号の集合 Vt: 終端記号の集合 P: 書き換え規則の集合

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

65 例 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 }

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

67 文法の分類 文法にはいくつかの種類がある。 それに応じて、処理装置・処理方法が異なってくる。

68 ここまでのまとめ 文法 ： G=（ Vn, Vt, P, S ）： 言語 ：L=L(G) ただし、

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

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

71 形式文法と形式言語 文法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

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

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

74 Chomsky階層 重要 PSL CSL CFL RL

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

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

77 解析手法は重要なので 「言語プロセッサ」の授業（後期）で 取り上げます。
機械翻訳・通訳電話などの自然言語処理 コンパイラ ゲーム（ホント？　次回お話します。） などで応用されている。

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

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

80 さらに話を進めましょう！

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

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

83 Chomsky階層 重要 PSL CSL CFL RL

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

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

86 まずは有限オートマトンから

87 有限オートマトンのイメージ qk FAの概観 a1 a2 ai-1 ai an セル 入力記号 入力テープ ヘッド 内部状態 ・・・ ・・・

88 有限オートマトンの定義 FA = ( K, Σ, δ, q0, F ) ただし、 K ： 状態の集合( Kは有限集合)
Σ ：　入力アルファベット（Σは有限集合） δ ：　状態遷移関数 δ： K×Σ∋( a, qi ) → qj ∈ K q0 ：　初期状態 F ：　最終状態の集合 ( F ⊆ K )

89 この話が発展すると．．． PackManというゲームはこのあたりの理論を利用している。 こんな話も追々していきます。お楽しみに！

90 次回、この続きを話します。 有限オートマトン 正規表現 正規表現から有限オートマトンの生成 状態数最少有限オートマトン
決定性有限オートマトン 非決定性有限オートマトン 正規表現 正規表現から有限オートマトンの生成 状態数最少有限オートマトン 正規表現→非決定性有限オートマトン→決定性有限オートマトン→状態数最少有限オートマトン

91

92 この授業のキーワード (形式)言語 正規文法（正規表現） 文脈自由文法 （文脈自由言語） オートマトン 有限状態オートマトン
線形有界オートマトン プッシュダウンオートマトン 決定可能性 トラクタブル　など

93 クイズ：文法が大切な理由は？ 文をすべて覚えることができないから。 多くの言語に備わっている性質だから。 試験に出るから。
知っていると威張れるから。 答えは来週、この授業で。

94 授業のURL 上記のページの左側を 見て、辿ってください。