| 科目名 |
オートマトンと形式言語 |
| 担当教員 |
島村 和典 |
| 対象学年 |
2年 |
クラス |
学部：専門001 |
| 講義室 |
Ａ１０６ |
開講学期 |
１学期 |
| 曜日・時限 |
月４,木４ |
単位区分 |
選択 |
| 授業形態 |
一般講義 |
単位数 |
2 |
| 準備事項 |
|
| 備考 |
|
| 授業の詳細1 |
講義目標及び講義概要
オートマトンは計算機の動作を抽象的に取り扱うモデルである。現実のハードウェアやソフトウェアの詳細を捨象することにより、計算機の取り扱うことのできる問題はどのようなものなのか一般的な議論を行うことを可能にした。一方、形式言語は人工言語の定義手法の一つである。文法を厳密に定義し、文法から導出されるアルファベット列の集合を言語と捉えることで、言語を精密に扱うことを可能にした。オートマトンと形式言語とは独立の概念であるものの、両者には密接な関係があることが分かっている。オペレーティングシステムのプロセスの状態やプロトコルを用いて通信するネットワーク上のノードの動作の表現、さらにテキスト処理やコンパイラの技術に応用され、計算機に纏わる数学的手法の中では最も成功した学問である。
本講義では、特にネットワーク技術への応用を主眼にオートマトンと形式言語の概念を修得する。ネットワーク技術の様々な局面でオートマトンと形式言語が応用されていることを知り、どのような場合にどのような技術が利用されているのかを、用いられているオートマトンと形式言語の性質と合わせて理解することを目標とする。
本講義はネットワークの基礎的な概念を持っていることを前提とするため、「通信網概論」を修得した学生を対象とする。また、本授業の内容を修得することにより「計算機ネットワ ーク」の理解の準備ができる。なお本講義は、オートマトンと文法との関係における性質を議論したり、オートマトンに課す制約と計算能力の理論を重視する従来型カリキュラムでのアプローチとは全く異ることに注意せよ。このため「オートマトン」や「形式言語」がタイトルについている書籍はほとんどの場合、本授業の理解には直接は役に立たない。
|
| 授業の詳細2 |
本講義では、オートマトンとして有限状態オートマトンを学習する。これが情報システムやネットワークシステムでのコンポーネントの状態を表現するのに多く用いられていることを学び、オートマトンと表現される動作との関連を理解する。後半は文脈自由文法を定義するBNF記法を修得し、プログラミング言語やドキュメント記述言語の定義など広く用いられていること、さらにそれらの読解方法と記述手法について理解する。特にネットワーク対応ドキュメント記述言語 XML について、その文法定義の手法も含めて習熟する。
本講義の修得により以下が可能になる。
(1) オートマトンで記述されたソフトウェアコンポーネントやネットワークノードの動作を読解できる。簡単なプロトコルのオートマトン表現の改変ができる。
(2) BNF記法で定義される文法を理解する、また文がBNFに沿っているかどうかの判定を行うことができる。
(3) Pascal、XMLの文法をBNFを用いて正しく理解することができる。
(4) 基本的な XML 文書を記述することができる。
(5) XML の DTD 表記を読解することができ、それに相当するBNFを示すことができる。
|
| 授業の詳細3 |
講義計画
1. オートマトンと形式言語入門
まず、カリキュラム全体における本講義の占める位置について、特に通信網概論、計算機ネットワークとの関係について説明を受ける。その上で、本講義の授業計画と成績評価についての説明を受ける。次に、オートマトン形式言語の役割とその歴史について学習する。オートマトンの入門として、まず有限状態オートマトン(Finite State Automaton, FSA) の定義方法とその意味について学習する。オートマトンの応用例として、抽象化された自動販売機の例での説明を受ける。最後に、図によるオートマトンの表現と、表による表現とを学習し、両者が相互に変換可能であることを示す。
2. 簡単なプロトコルとオートマトン
FSAのネットワークへの応用を学習する。まず、2人のユーザと電話網を抽象化したモデルにより、ユーザの発呼・着呼の振舞いにより電話網がどのように動作するかを簡単なFSAにより表現できることを学ぶ。次に、フローグラフの記述法を学び、ユーザと電話網との基本動作をフローグラフでも記述できること、および必ずしも全ての動作をフローグラフでは記述できないことを理解する。さらに、話中の概念を導入し、FSAを拡張することで網の機能を拡張できること、フローグラフでの表現はより困難になることを理解する。
［演習1］ 電話網にキャッチホンの機能を導入する演習を行う。
|
| 授業の詳細4 |
3. トランスポート層プロトコルTP0の動作
電話網の発呼・着呼を例に直観的に捉えていたプロトコルの概念を、より一般的にトランスポート層の動作ととらえる。そのためにまず、ISO の定めるトランスポート層のモデルとトランスポート層プロトコル TP0 の概略を理解する。つぎにISOの自然言語による定義と、FSAによる表現とを比較し、FSAによる表現がより厳密であることを確認する。
4. アプリケーション層プロトコルTFTPの動作
インターネットにおけるファイル転送プロトコルTFTPの動作を、まずRFCと呼ばれる文書で読む。次に文書が意味するFSAを構成する。構成したFSAから、TP0とTFTPとの違いを理解する。
5. プロトコル記述におけるFSAの限界
動作の定義全体でFSAで自然に定義できる部分と、FSAでは定義が困難で別の表現の応援が必要な部分とに分類し、FSAの能力について議論する。また、可読性についてフローグラフによる表現や文書による表現と比較し、FSAの有効性とそこで、プロトコルの定義によって動作し、プロトコルが正しく動くことを体験する。
［演習2］ 2人でチームを作り、各々がネットワークのノードとなる。 |
| 授業の詳細5 |
6. 中間試験
［演習3］ 中間試験解説・前半のまとめ
7. BNF入門
計算機言語の構文を示すのに良く用いられる Backus-Naur Form (BNF) を学習する。まずBNFの厳密な定義を学ぶ。次に、電子メールに用いられるアドレスを例に簡単なBNF記法を理解する。さらに、この例で用いたBNFを若干修正することで、どのような言語がアドレスとして解釈され得るのかを把握する。最後に、Extended BNF (EBNF) について学び、BNFでは表現が繁雑になる文法がEBNFで簡潔に記述できることを理解する。
8. Pascal の文法
計算機言語1とコンピュータリテラシーで用いた手続き型プログラミング言語Pascalを例に BNF の本格的な使用方法を理解する。まず、Pascal の十分小さなサブセットのBNFから、どのような文がPascalプログラムとして受理されるのかを調べる。さらに正しいPascalの文で、どのような文が受理されないのかを調べる。つぎに、BNFを拡張することにより、若干仕様の大きなPascal言語を構成して、BNFの記述と表現される言語との対応を理解する。
|
| 授業の詳細6 |
9. 文脈自由文法
BNFが表現する文法を文脈自由文法と呼ぶ。文脈自由文法は、各要素を木構造として組み上げること、すなわちBNFによる記述は木構造の定義に他ならないことを学習する。構造物や社会組織などの木構造の概念を持つ対象は、すべてBNFで記述が可能であることを理解する。さらに、BNFや文脈自由文法では兄弟要素である木の枝間での制約条件を一切記述できないことを学習する。この例として、BNFでは正しいと解釈されるPascalプログラムでも、必ずしもプログラムとして正しくない場合があることを調査し、これを表現すること BNF では不可能であることを認識する。
［演習4］ 制限されたPascal文法に機能を加えることと、それを BNF で表現する演習を行う。
10. Markup Language入門
コンピュータリテラシーでは、階層的かつインターネット指向のドキュメント記述言語としてHTML (Hyper Text Mark-up Language)を学習した。HTMLやSGMLの機能を整理し、より柔軟にしたドキュメント記述言語にXML (eXtensible Mark-up Language) がある。ここでは、Markup Language と呼ばれるドキュメント記述言語群の歴史を学習する。まず CALS と呼ばれる電子商取引の概念によって誕生した SGML、次にインターネットの普及を爆発的に加速させた WWW のページを記述するための HTML、そして多くの Markup Language の蓄積と反省を活かして誕生した XML について知る。最後に HTML の復習を行い、Markup Language に対する直観的な理解を深める。 |
| 授業の詳細7 |
11. XML 入門
ここではまず、簡単な XML ドキュメントを例に、XML の基本的な記述方法を学習する。特に HTMLでの記述との差異に注意しながら学習する。HTML で許された記述が XML でできない場合の基本的な考え方について理解する。簡単なドキュメントを HTML と XML との両方で記述して慣れ親しむ。
12. DTD記述手法
前回用いたのは DTD (Document Type Definition) を使わないXML ドキュメントであった。まず、DTD の記法を知り、DTD を記述することにより XML ドキュメントの文法をユーザが定めることができることを認識する。簡単な DTD の記述により、どんな XML 文法ができるのか、どんな XML 文書が記述できるのかを例によって理解する。
13. DTD と BNF
DTD の記述により XML ドキュメントがどのような文法を持つのか、すなわちどんな BNF に相当する文法になるのかを学習する。自分が必要な XML 文法を BNF および DTD により記述できるように、互いの関係に対する理解を深める。
［演習5］ XML の記述の演習を行う。
14. クォータ末試験
15. クォータ末試験解説・全体のまとめ
（一般に試験を振り返る時間や全体を振り返る時間を取ることが望ましい）
|
| 授業の詳細8 |
◆テキスト:なし。必要に応じてハンドアウトを資料として用いる。
◆参 考 書:『XMLバイブル』，Elliotte Rusty Harold（日経BP）
『離散数学』第7.6-7.8節, 第9.3節，Seymour Lipschutz（オーム社）
◆成績評価: 演習課題20点（各5点×4回）、中間試験40点、クォータ末試験40点、計100点。60点以上を合格とする。
＜成績評価の基準＞
ＡＡ：特に優れた成績を示したもの
Ａ ：優れた成績を示したもの
Ｂ ：良好と認められる成績を示したもの
Ｃ ：合格と認められる成績を示したもの
Ｆ ：不合格
◆備 考:JABEE「情報ネットワークシステム工学教育プログラム」ネットワークコース選択必須科目 ◆履修の前提となる必須科目=「通信網概論J」「計算機言語第2J」
◆事前の履修が望ましい科目=なし
◆同時に履修すべき必須科目=なし |
| 授業の詳細9 |
|
| 授業の詳細10 |
|