形式言語理論：第6回

• 実施日：2008-05-27（火）1限
• 講義内容：正則表現→DFA、正則表現の代数的性質
• 教科書3.2.1節、3.4節

正則表現のしめくくりとして、前回残っていた正則表現からDFAを構成する方法、および正則表現の代数的性質についてお話しました。正則表現からDFAを構成する方法は割と技巧的で、教科書の証明を読んだだけでは分かりにくいかもしれません。講義では、かなり直観的な解説を試みたつもりです。

正則表現も式ですから、交換則、結合則、分配則など、比較的なじみのある代数的性質が成り立ちます。ただ、一般に正則表現の式変形はあまり簡単ではありません。特に閉包が絡むと途端に式変形が難しくなります。そのため、工学的には、有限オートマトンを経由するほうが簡単です。4章で、このための基本的な手法である状態数最小化について述べます。

データベース(システム)・データマネジメント(スポーツ)：第7回

• 実施日：2008-05-23（金）2限
  
• 講義内容：関係代数による問合せの記述例
  
• 今回はちゃんとした講義ノートを用意せずに話しましたので、講義ノートはありません。
  

今回は関係代数のまとめとして、これまで紹介してきた関係代数の演算を使って、実際の問合せをどのように書くかについて、典型的な例を中心にお話しました。簡単なものから複雑なものまで、かなりいろいろな問合せが書けることに気づかれたことと思います。

実際にデータベースを使うときには、ニーズ（○○のデータが欲しい）がまずあって、それに合わせて問合せを行うことになります。つまり、今回やったような作業をその都度行います。そのため、単に関係代数の式の答を計算するだけではなく、問合せから関係代数の式を組み立てる訓練が必要となるわけです。

次に紹介するSQLによる問合せ記述と合わせて、後日、練習問題（過去問）を配布する予定です。これも用いて、問合せから関係代数の式を組み立てる作業に慣れてほしいと思います。

データベース(理大):第7回

• 実施日：2008-05-22（木）7・8限
• 講義内容：関係代数による問合せの記述例
• 今回はちゃんとした講義ノートを用意せずに話しましたので、講義ノートはありません。

今回は関係代数のまとめとして、これまで紹介してきた関係代数の演算を使って、実際の問合せをどのように書くかについて、典型的な例を中心にお話しました。簡単なものから複雑なものまで、かなりいろいろな問合せが書けることに気づかれたことと思います。

実際にデータベースを使うときには、ニーズ（○○のデータが欲しい）がまずあって、それに合わせて問合せを行うことになります。つまり、今回やったような作業をその都度行います。そのため、単に関係代数の式の答を計算するだけではなく、問合せから関係代数の式を組み立てる訓練が必要となるわけです。

次に紹介するSQLによる問合せ記述と合わせて、後日、練習問題（過去問）を配布する予定です。これも用いて、問合せから関係代数の式を組み立てる作業に慣れてほしいと思います。

休講通知：コンパイラ

5/28（水）の「コンパイラ」の講義は、休講とします。

コンパイラ：第6回

• 実施日：2008-05-21（水）1限
• 講義内容：文脈自由文法の性質
• 講義ノート：4章（前回配布分）

先週に引き続き、構文解析の基礎理論となっている文脈自由文法についてお話しました。今回は主に、構文木（解析木）、文法の曖昧性など、構文解析を理解する上で必要となる文脈自由文法の性質を紹介しました。4章で残った左再帰については、構文解析の中で説明することにします。

情報通信工学演習C：第4週

• 実施日：2008-05-20（火）3・4限
• 実施内容：成果報告会に関する説明、課題のプログラミング

サンプルデータ全てについて正しい結果を出力できたグループ、一部についてのみ正しい結果を出力できたグループ、まだ正しい結果が得られていないグループ、この3つがほぼ同数といった状況。後2週間弱でどこまで進むか。

ところで昨日、課題のプログラムをRubyでも書いてみた。まあまあの速度のものが完成した。ただ、もともと手続き型言語で実装しやすいように設定された問題なので、ちょっとRubyでは書きにくいところがあった。まあ、某講義（詳細はいずれまた）の準備には役に立ったか。あとは関数型言語でも書いてみたいんだが、どうなることか。Standard MLはコンパイルしにくいので、やるとするならOCaml、Haskell、Erlangあたりなんだけど。いっそ原点に立ち返ってSchemeという手もあるかも。

形式言語理論：第5回

• 実施日：2008-05-20（火）1限
• 講義内容：ε-NFA（受理言語の定義、DFAとの等価性）、正則表現（定義、正則表現からε-NFAへの変換）
• 教科書2.5.4〜2.5.5項、3.1節、3.2.3項

前回途中になってしまったε-NFAの話を終わらせた後、正則表現について話を始めました。

ε-NFAの受理言語やDFAとの等価性は、ほぼNFAの場合と同じです。唯一違うのは、入力なしで遷移できる状態達を考慮しなければならないという点です。そこで ε-閉包（ε-closure）という概念を導入し、受理言語の定義、およびε-閉包を考慮したサブセット構成法について説明しました。

正則表現の定義については、学部講義「コンパイラ」でもかなりちゃんとお話しています。この講義では、「コンパイラ」で触れなかった話題を中心に話を進めていきます。まず取り上げるのは、有限オートマトンとの等価性です。今日は時間の都合で、与えられた正則表現から等価なε-NFAを構成するアルゴリズムについてのみ説明しました。次回は、与えられたDFAから等価な正則表現を構成するアルゴリズムについて説明をします。

データベース(システム)・データマネジメント(スポーツ)：第6回

• 実施日：2008-05-16（金）2限
• 講義内容：関係代数(2)：直積、結合、自然結合、商
• 講義ノート（第5回と同じもの）

先週に引き続き、関係代数の演算についてお話しました。今週取り上げたのは関係2つに対する演算です。なかでも結合と自然結合は、選択、射影と並んで頻繁に用いられるもので、ひじょうに重要です。

これで、関係代数の演算の紹介は一通り終わりました。次週はこれらの応用ということで、関係に対する具体的な問合せをどのように関係代数で記述するか、例を用いながら説明する予定です。その下準備を兼ねて練習問題を出しておきました。考えてみて下さい。

データベース(理大):第6回

• 実施日：2008-05-15（木）7・8限
• 講義内容：関係代数(2)：直積、結合、自然結合、商
• 講義ノート（第5回と同じもの）

先週に引き続き、関係代数の演算についてお話しました。今週取り上げたのは関係2つに対する演算です。なかでも結合と自然結合は、選択、射影と並んで頻繁に用いられるもので、ひじょうに重要です。

これで、関係代数の演算の紹介は一通り終わりました。次週はこれらの応用ということで、関係に対する具体的な問合せをどのように関係代数で記述するか、例を用いながら説明する予定です。

コンパイラ：第5回

• 実施日：2008-05-14（水）1限
• 講義内容：文脈自由文法（資料4.1節）
• 配布資料あり（4章）

今回から構文解析の説明に入ります。まず、構文解析の基盤となる理論である文脈自由文法についてお話しました。正則表現と同様、文脈自由文法も言語を有限の記述で表すための枠組ですが、正則表現と比べると、どのような言語を表すのか直感的に分かりにくいところがあります。そのため、再帰的定義による言語の定義の例なども交えて、かなり時間をかけて説明しました。

次回は、構文解析を理解するのに必要となる文脈自由文法の性質から話を始めます。

情報通信工学演習C：第3週

• 実施日：2008-05-13（火）3〜4限
• 実施内容：Cプログラミング

比較的順調か。予想以上の班もある。

形式言語理論：第4回

• 実施日：2008-05-13（火）1限
• 講義内容：非決定性有限オートマトン（NFA）、ε-動作つき非決定性有限オートマトン（ε-NFA）
• 教科書2.3節、2.5.1〜2.5.3項

GW前にお話したDFAに引き続き、有限オートマトンの一種であるNFAとε-NFAについてお話しました。DFAとNFAの違いは、遷移関数の出力（次状態）が1状態であるか状態集合（0個以上の状態）であるか、です。またNFAとε-NFAの違いは、入力なしに状態遷移することを許すかどうか、です。見かけ上は差があるように見えますが、実はこれらは等価であることが分かっています。これらの結論とともに、サブセット構成法、模倣（simulation）という重要な考え方についてもお話しました。

教科書を受け取った人は2,800円をお支払いください。

データベース(システム)・データマネジメント(スポーツ)：第5回

• 実施日：2008-05-09（金）2限
• 講義内容：関係代数(1)：集合演算、選択、射影
• 講義ノート

今回から本講義の最初のヤマである関係代数の話をします。その名の通り、関係、すなわち組の集合に対する代数演算で、これらを使って関係に対する計算を行うことが、関係データベースでの問合せの基本になります。今回はそのうち、集合演算、および関係1つに対する関係演算である選択と射影について話しました。選択と射影は、関係代数の中でも極めて重要な演算なので、是非理解しておいて下さい。

データベース(理大):第5回

• 実施日：2008-05-08（木）7・8限
• 講義内容：関係代数(1)：集合演算、選択、射影
• 講義ノート

今回から本講義の最初のヤマである関係代数の話をします。その名の通り、関係、すなわち組の集合に対する代数演算で、これらを使って関係に対する計算を行うことが、関係データベースでの問合せの基本になります。今回はそのうち、集合演算、および関係1つに対する関係演算である選択と射影について話しました。選択と射影は、関係代数の中でも極めて重要な演算なので、是非理解しておいて下さい。

コンパイラ：第4回

• 実施日：2008-05-07（水）1限
• 講義内容：字句解析
• 配布資料あり（3章）

前回お話した正則表現と有限オートマトンを踏まえ、字句解析の概要についてお話しました。大まかには、認識したいトークンを正則表現で表し、それと等価な有限オートマトンを生成します。実際にプログラムを字句解析するときには、生成したオートマトンを動作させ、対応する文字列を受理したときにトークンを出力するわけです。その際、先読みの問題、複数のオートマトンで同じ文字列を受理してしまったときの対応などを考えておく必要があります。そのほか、バッファリングについても簡単にお話しました。

次回から構文解析の話に入ります。

データベース(システム)・データマネジメント：第4回

• 実施日：2008-05-02（金）2限
• 講義内容：キー
• 講義ノート

キーと呼ばれる考え方についてお話をしました。キーは表中で組を特定するための属性集合で、データベース独特の考え方です。よく出てくる用語ですし、実際にデータベース管理システムを使う上でも必要となるものなので、知っておいて下さい。なお、講義ノート中、外部キーについては別の機会にお話しするつもりです。

データベース(理大):第4回

• 実施日：2008-05-01（木）7・8限
• 講義内容：キー
• 講義ノート

キーと呼ばれる考え方についてお話をしました。キーは表中で組を特定するための属性集合で、データベース独特の考え方です。よく出てくる用語ですし、実際にデータベース管理システムを使う上でも必要となるものなので、知っておいて下さい。なお、講義ノート中、外部キーについては別の機会にお話しするつもりです。