本文へジャンプ

学科概要
  • HOME
  • 学科概要
  • 学生による学科紹介

学生による学科紹介

実際の授業をいくつか文書におこしてみました。先生方の仮想講義を体験してみてください。情報科学科の講義は90分授業です。午前中の講義は10時15分から、午後の講義は13時から始まります。14時45分からの講義がある曜日もあります。

形式言語理論 | 宮野 悟
開講時間: | 1
シラバス
形式言語とオートマトン、および、計算可能性の初歩について講義する。 形式言語とオートマトンについては、 正則言語、有限オートマトン、文脈自由言語を中心に。 計算可能性については、チューリング機械とその停止性問題に関して。
授業情報
4学期に開講される理学部の専門授業で、情報科学科では必修授業として扱われるので、進学した場合全員履修することになります。理学部他学科の選択授業でもあるため、他学科生も見受けられ、受講人数は半々といったところです。ここ最近は金曜3限に開かれているようです。
 授業方法は教員がスクリーンにスライドを映しながら説明し、その具体的な例や解法を板書していく形式です。なお、このスライドの内容は教員から教科書という形で予め無料配布されます。しかし、この教科書は抽象的な定義が書いてある部分がほとんどで、問題の解法については「授業中に説明する」とだけ書かれていたり、間違いが存在したりします。(編註:教科書が配布され始めて2年経ちましたが、まだ存在するようです。間違いは教員が授業中に修正します。)
 上記の理由により、出来るだけ出席はした方が良いと思います。実際は、最初こそ大半が出席して授業を聞いていますが、半ばを過ぎると出席人数は3分の2ほどになり、出席している人の半分ほどはうつらうつらしています。これをどう考えるかはあなた次第です。
前提知識
この授業を学ぶにあたって予め必要な知識というのは特にありません。使用する用語や定義については授業中に説明が有るので困らないでしょう。
授業概要
「形式言語理論」という名の通り形式言語について学ぶことになります。なぜ、情報科学科で形式言語を学ぶかといえば「我々が用いているプログラミング言語は、正しいプログラムならば形式言語であるといえる」からです。まず、形式言語の一つである正則言語を学ぶために、正則言語を受理する「オートマトン」について学ぶことから始めます。そのオートマトンを用いて「正則言語」を学びます。次に形式言語の一つである「文脈自由文法」について学びます。最後にオートマトンのように働く「Turing機械」について学びます。
発展
この授業は情報科学科後期授業の「言語処理系論」「言語モデル論」「情報科学演習」「コンパイラ演習」などに発展していきます。
 「正則言語」や「文脈自由文法」はコンパイラにおける「字句解析」「構文解析」を行うのに用います。
 「言語モデル論」では「我々が普段使用している言語(自然言語)は文脈自由言語ではないか」という事について考えます。
 「Turing機械」は幅広く使用されますが、「情報科学演習」の計算可能性などに用います。
試験
試験は3月の試験期間に行われる。問題は具体的では無いが、事前にある程度ばらしてくれます。例えば「正則言語のPumping Lemmaから出します」とか「過去問から出します」といった具合である。そのため試験勉強はし易い。問題は3問構成で、「正則言語」「文脈自由構文」「アルゴリズム」から各1題出る傾向です。授業では「Turing機械」についても勉強しますが、試験にはでないようです。なお、教科書には付録として過去の試験問題があるので、それを見れば傾向は簡単に掴めます。
 しかし、問題そのものは難しいため、授業や教科書を理解できていない場合、出る範囲が分かっていても、毎年単位を取れない人もいます。
 追試験は行うこともあるし、行わないこともあるため、本試験で単位を取得するのが賢明です。
まとめ(らしきもの)
基本的にこの授業は、これ単体で何かを学ぶというよりは、3年以降の授業のための知識をつけるといったものです。かといって、この授業が良く分からなかったから3年以降の授業についていけないということはまったくありません。とりあえず気軽に先生の授業を聞くのが良いのではないでしょうか。最低限、下に書いた授業内容くらいが分かっていれば「そういえば、やったなあ」と感じます。しばらくしてからもう一度教科書を読むとちゃんと理解できると思います。
授業内容
配布される教科書によると、この授業は
1章「基本的定義と記法」
2章「有限オートマトンと正則言語」
3章「文脈自由文法」
4章「Turing機械」
という4章構成+αとなっています。
 授業では各々形式的な定義を学びますが、そんなことをここで書いても読む気もしないだろうし、面白くもないので、各章の基本的な事を簡単に説明しようと思います。
有限オートマトン 〜例1〜
オートマトンなんて言葉を聞いたことがあるでしょうか? このページを読んでいるほとんどの方は聞いたことが無いのではと思います。かく言う筆者もこの授業で初めて聞いた言葉です。言葉で説明するなら「有限個の状態、状態遷移の組み合わせのモデル」ということになります。まあ、これだけじゃ何の事なのかさっぱりなので、教科書にも載っている分かり易い問題を見てましょう。

問題1
登場人物
 わたし:名前を「あんな」といいます。
 けんじ:わたしの恋人です。でも浮気っぽいのが心配です。
 ももこ:わたしの親友です。
 なおこ:わたしの親友です。
状況
 私たち4人は、あることから離れ小島に取り残されてしまった。
そこには二人乗りのボートがあるが、運転できるのは私だけです。
全員を岸まで運びたいのですが、けんじは浮気っぽいのでけんじとももこ、
けんじとなおこを二人だけにするのは危険なので嫌です。
さて、どのように運べば良いでしょうか?


 さて、この問題は「小島と岸に誰がいるかという状態」「ボートで人を運ぶ状態遷移」を考えていけば解ける。実際にこの状態遷移図を書いてみると以下のようになります。


この状態遷移図が「オートマトン」です。少しはオートマトンのイメージが掴めたでしょうか?
有限オートマトン 〜例2〜
この有限オートマトンは様々な分野で利用されますが、情報科学では0と1の文字を言語として扱うので以下のようなオートマトンを扱うようになります。

問題2
集合{x∈{0,1}*|[x]は3の倍数}を受理する有限オートマトンはどのようになるか
[x]は記号列xを2進数の整数とみた値


さて、オートマトンを作るには状態と状態遷移が必要です。3の倍数かどうかは3で割った余りを見ると分かります。そこで状態は

* 3で割った余りが0(状態q0)
* 3で割った余りが1(状態q1)
* 3で割った余りが2(状態q2)

の3つとすることが出来ます。次に状態遷移を考えます。
現在の状態、例えば11010が入力だとすると、110=6まで読み込んだ場合3で割った余りが0の状態です。次に読み込むのは1で、値としては1101 =13となります。これは現在の値100を2倍して1を足しているのと同じことです。(分かりにくい方は10進数で同じことを考えてみてください、 110→1101にするには10倍して1を足します)このように考えると、現在の値xとして2x+0or1を考えて状態遷移すればいいことになります。よって

* 3で割った余りが0の時、次が0の場合3で割った余りが0、次が1の場合3で割った余りが1
* 3で割った余りが1の時、次が0の場合3で割った余りが2、次が1の場合3で割った余りが0
* 3で割った余りが2の時、次が0の場合3で割った余りが1、次が1の場合3で割った余りが2

となります。したがってオートマトンは

となるわけです。

オートマトンについては他にも学ぶのですが、形式的な事になってくるので省略します。
正則(正規)言語
この授業では、上記の有限オートマトンによって受理される言語の集合を「正則(正規)言語」と定義します。例えば、先ほどの問題2であればその集合は(・・・・・・)となります。正則言語については「正則言語のPumping Lemma」という定理を学びます。これはその言語が正則でないことを証明する(正則か否かを判断する)定理です。具体的な説明は有限オートマトンについて学んでからでないと難しいと思うので、ここでは省略します。使いかたを簡単に説明すると、ある言語を正則だと仮定すると「Pumping Lemma」の定理において矛盾が生じる、といった背理法で用いられます。
 これに付随して、正則言語の表現方法として「正則(正規)表現」を学びます。基本的な形を簡単に説明すると、以下のようなものがあります。
 r?:rが0個か1個 例、"colou?r" = "color" or "colour"
 r*:rが0個以上 例、"go*gle" = "ggle" or "gogle" or "google" or ...
 r+:rが1個以上   例、"yaho+" = "yaho" or "yahoo" or "yahooo" or ...
といった表現です。
 最終的には、正規表現と有限オートマトンの関係を学びます。つまり、正規表現をオートマトンに直したり、逆にオートマトンを正規表現に直したりします。

(正則言語ってこれ以外に説明するべき事あるかしら、というか説明する意味があるかなー?)

* 文脈自由文法

 この言葉も聞いたことがある人は少ないと思います。単純にいうと「A → α」という形の生成規則だけで作られる言語の事です。よくわかりませんね、例を見てみましょう。

問題3
 次のような生成規則からはどのような言語が作られるでしょう? Sから始めてx,y,zになると終了とします。

S → E
E → (E + E)
E → x
E → y
E → z


 これならば大体想像がつくのではないでしょうか。例えば

S → E
→ (E + E)
→ ((E + E) + E)
→ ((x + E) + E)
→ ((x + y) + E)
→ ((x + y) + z)


となるので((x + y) + z)という表現が可能です。周りの環境に依存すること無く「A → α」という置き換えが可能な文法なので文脈自由、というわけです。このような文脈自由文法で生成される言語を「文脈自由言語」といいます。これも形式言語の一種であり、上で書いた正規言語は文脈自由言語の一つであるといえます(ただし逆「文脈自由言語は正規言語である」は言えません)。
Turing 機械
Turingとはイギリスの数学者の名前でチューリングと読みます。チューリング機械とは彼が考えた仮想機械で

* 無限に長いテープを持ち、そのテープはセルに分割されている
* 各セルは一つの文字を記憶できる
* テープに格納された情報を読んだり書いたりするヘッドを持ち、左右に動くことが可能である
* 内部状態を保存するメモリを持つ有限制御部

を持ちます。この機械は

* ヘッドがある位置のセルの情報を読み取る
* ヘッドがある位置のセルに情報を書き込む
* 機械の内部状態を変える
* ヘッドを右か左に1セル分動かす

という動作を行います。やっぱり分かりにくいですね。例えばどのように使えるか見てみましょう。

問題4
 Turing機械を用いて数字が偶数かどうかを判断するにはどうすればよいでしょうか?



与えられる数字は2進数なので、最後の数字が0か1かで偶数かどうかが判断できます。そこで、
1、ヘッドがある位置のセルを読み取り、数字ならばヘッドを一つ右に移動させ、この動作を繰り返す
2、ヘッドがある位置のセルを読み取り、数字以外(空)ならばヘッドを一つ左に移動させる
3、ヘッドがある位置のセルを読み取り、0ならば偶数、1ならば奇数である
と言えます。
 何故こんな機械について学ぶかといえば、「計算機で原理上解ける問題はチューリング機械でも解ける」と考えられているからです。後期課程ではこのチューリング機械を用いて計算可能性を考えます。