比較プログラム言語論
平成16年5月26日
森田 彦
レポート(5/19)総括
< テーマ >

本日の講義で、あなたが最も興味を持った点はどのような点です
か?講義の全体的な感想と共に、できる限り具体的に、200字~400
字程度で記述して下さい。
<興味を持った点>



チューリング機械
オートマトン理論
形式文法とオートマトンの関係
チューリング機械

今日の講義で一番興味が持てたのは、1937年にイギリスの数学者
である。アラン・チューリングが計算理論のモデルとして提唱した
チューリング機械です。なぜなら、単純な原理だが、一定の手順に
従えば答えが求められるような計算は、理論上すべてチュー
リング機械で実行できるとされている。チューリング機械そのもの
は理論だけの存在であり、実際に製作されたわけではないが、現

在のコンピュータも突き詰めればチューリング機械の原理に従ってい
ると言える。
今日の講義で興味を持ったところは、まず、数学の世界における計算
は四則演算だけでなく、物事の問題を解決まで導ける一定のプ
ロセスも計算とされているということだというところです。さらに、そ
れを踏まえたうえでのチューリングの考えです。「計算とは紙に書か
れた記号を読み、それに基本的な思考操作を加えて新しい記号を書
くことの繰り返し」と言われて、数学世界の計算の定義を初めて知り、
漠然として、把握できなかった状態から一気に救われた気がしました。
チューリングの考え



解ける、解けない、つまり計算できる、できない、
とはどのように定式化できるのだろう?
計算できるとはどういうことか?
計算過程をどのように表現できるか?→どこま
で単純化して(しかもエッセンスを失わずに)表
せるか?→ モデル化
最終的にたどりつい
たのが、チューリン
グ機械
テープ
ヘッド
制御部
計算(思考)過程を簡単な機械で表現したところがポイント!
オートマトン


オートマトンとは受理判定機械の事であり入力に際しそこ
に記載された語を読み、それが言語に属するかを判断
する機械、入力されたものがある基準を満たしている
かどうかと言う判断をする機械、と理解することが出来
た。このオートマトンには四種類のグループ分けがあると
いうことでした。これらと、今まで学習してきた内容から言
語にはそれぞれ系統があり、やはり用途はそれぞれに向
き不向きがあるものなのだと思いました。
今日の授業では有限オートマトンの話が一番おもしろかっ
たです。チューリングマシンでは制限なく、全てを受け入れ
てしまうようですが、それでは大変だと思います。有限オー
トマシンは有限だし、定義によって受理される、されないの
制限もあるのでやはりこちらのほうが、精度が高いのでは
ないかと思います。
有限オートマトン
Σ
テープ
ヘッド
有限状態装置
Q
テープ、ヘッド、有限状態装置から構成
ヘッドは一方向のみ動く
 有限オートマトンMの定義
M=(Q,Σ,δ,q0,F)
Q:状態、Σ:入力記号、δ:状態遷移関数
q0:初期状態、F:受理状態

有限オートマトンの例
テープ
a b
ヘッド
有限状態装置
q0
Q={q0,q1,q2}、Σ={a,b}、F={q2}
δ(q0,a)=q1, δ(q0,b)=q0 ,
δ(q1,a)=q1, δ(q1,b)=q2 ,
読み取るだけ!
δ(q2,a)=q1, δ(q2,b)=q0
 入力記号“ab”が受理されるか?
δ(q0,ab)= δ(δ(q0,a),b)=δ(q1,b)=q2
受理!
 入力記号”ba”は受理されるか?
δ(q0,ba)= δ(δ(q0,b),a)=δ(q0,a)=q1
受理されない!

オートマトンの考え





人間の思考過程→(脳の)状態の変化
状態を記号で表現すれば→記号の変化規則を
状態遷移関数で表現できる。
状態遷移関数で、“思考”を数学的に表現できる。
言語は、“思考”の一例
2進数で状態を表現すれば→コンピュータで問
題を解ける。→計算可能な問題はコンピュータで
全て処理可能→初期のコンピュータ科学者の夢
オートマトンと形式文法の関係


今日の講義で興味を持ったのは、数学の分野で考えられた「オートマ
トン」という理論と、言語の分野で考えられた「形式文法理論」が対応
したということです。もちろん、対応させるまでにはいろいろな研究が
あったと思いますが、別の分野で別のことを考えていたものが、同
じような法則?のもとで対応したというのは面白いなと思いまし
た。小出先生の地学の講義で「数学と物理学の一部は言葉の通じな
い宇宙人にでも伝えることが出来る『宇宙語』である」といっていたの
ですが、そうすると数学は「世の中のものを数や式を使って一般的
(宇宙的?)に表すことはできないか」というものになると思います。そ
う考えれば言葉のならびや規則性が数学的な式で表されたとしても
不思議ではありませんが、世間的に見れば対極にあるものがうまく融
合したというのはとても不思議なことだと思います。
私が本日の講義で興味を持った点は、数学的に考えられた「オート
マトン」という理論と言語の分野で考えられた「形式言語理論」と関
係性です。例えば、文脈依存文法言語と線形有界オートマトンが関係
性を持っているようにその他にも関係性を持つものがいくつかあって、
数学的に考えられた「オートマトン」と言語の理論で考えられた「形式
言語理論」が対応しあうという点に興味を持ちました。
質問1

現在はコンピュータの進歩により、プログラムが遠回り
で複雑に作られても、性能の部分でそれを補っていると
いうことです。 たしかに私達が使っているパソコンでも、
余程難解で複雑でもないかぎり、数秒~数時間の単位
でコンパイルできます。 また、そのことからプログラムの
ソフト的進歩より、コンピュータのハード的進歩の方が早
いといえます。そこで質問ですが、 プログラムの進歩は
どのくらいの、ペースで起こっているのでしょうか。 例え
ば、パソコンなら(CPU?)ムーアの法則なるものがあっ
たような気がします。プログラムに関してそういったもの
は無いのでしょうか。
ムーアの法則



半導体メーカーIntel社の創設者の一人であるムー
ア博士が提唱した経験則(1965年)
半導体の集積密度は18~24ヶ月で倍増する。
現在では、集積密度を性能に置き換えて理解され
ている。→今でも性能向上の目安を与えてくれてい
る。
ソフトウェアに関しては・・・?
開発効率に関して対応する法則はない。
ただ、幾つかの(大きな)発展の契機はある。
高水準プロミング言語の登場 → 構造化プログラミング →
オブジェクト指向プログラミング
質問2
テープ
ヘッド
制御部



チューリング機械の動作で、「ヘッドが見えている記号を
書き換える」というものがありましたが、その後の例で説
明を聞いていたものの、なぜ記号を置き換えるのかが
わからなかったです。
チューリングマシンではなぜヘッドがどっちにでも動くよ
うになっていたのですか?1方向じゃチューリングマシン
はなりたたなかったのでしょうか?
オートマンのヘッドの動きはわかりました、左右に動いて
状態遷移関数を使うのはいいのですが、有限オートマン
の一方方向だけに動くことの、一方方向の向きは決まっ
ているのでしょうか??
レポートへのコメント



5/12の<質問>Ⅳ-2(エラーを自動的に修正し
てくれた方がよい!?)について
感想と意見
5/12の「質問Ⅴ Brew」について
質問への回答
5/12の「前回レポートへのコメントⅡ.Javaは重
い!?(4/28<質問>の3)に対して」について
レポートを書いた当事者からの補足
ホームページを参照して下さい。
Delphi VS Java
言語によって文法エラーのレベルが異なる。
<Delphi>
<Java>
var
a,b,c: Integer;
begin
a:=4;
b:=2;
c:=a/b; ← エラー
end;
文法的に厳しい
int a,b,c;
a=2;
b=3;
c=a/b; エラーなし!
皆は、どちらを好みますか?
Delphi vs Java 1
<Delphi>
個人的にDelphiとJavaを比
べての私の好みですが、例だ
けを拝見すると、Delphiの方
が、勝手が良い気がします。
コンパイラが間違いを細かく
指摘してくれれば見落とし
がちな小さな間違いが少
なくなる気がします。
<Java>
自分もよくプラグラムを打ち間違え
エラーを起こしています。どこが間
違っているか分かれば非常に便利
だと思いますが、便利なのは素人
だけだと思います。プロからしてみ
ればいちいちエラーが表示さ
れるのは不便だと思われます。
「どこが、どう、間違っているか」指
摘される(訂正される)機能が優先
か、個人(プログラマー)の能
力の向上が(優先か)については、
後者だと思います。個人的には楽
なのはいいが、物に頼ってばかりな
のはどうかと思います。
Delphi vs Java 2
<Delphi>

私はDelphiの方が好ましいと
思います。Javaは曖昧である
分、長いプログラムでのエ
<Java>
に厳しいほうの言語がいい
DelphiとJavaのエラーレベルの
比較では私はJavaの方が好きで
す。なぜなら、動かせるのに、動
かさずエラーを出すDelphiは
ちょっと融通が利かないように
思えるからです。
言語によってエラーのレベルが異
なるという点についてはエラー
がゆるい方がいいと思います。
理由は間違った状態で実行する
と動作の段階でどのようなエ
間違っているところがすぐ
にわかるからいいと思った。
ラーが出るのかを体験して
おきたいからです。

ラーの特定が、非常に難し
いと思えるからです。その点、
始めから厳しく書いておく、
Delphiなら特定しやすいと

思えるからです。
DelphiとJavaの文法エラーの
レベルが言語によって異なると
いうことを知った。私は文法的
と思いました。エラーがでれば

Delphi vs Java (現時点での整理)
Delphi派、Java派が主張する(各々の)メリット
<Delphi>
<Java>
文法的に厳しいので、エ
ラーを未然に防ぐことが
できる。
 これにより、エラーの特
定がしやすくなる。

<もう一つの視点>
 記述の自由度が(相対的
に)高いので書き方に融
通が利く。
 エラーを体験することで実
践的な理解が深まる。
エラー検出について
 文法的に厳しくし、コンパイラのレベルで検出できるようにすべき。
 文法あるいはコンパイラに頼るのではなく、プログラマーの技量を伸ば
すべき!
<本日のテーマ>
次の2点について、皆の意見を述べてもらいます。
1.
2.
初めて学習するプログラミング言語としては、文法が
厳密でエラーを未然に防ぐタイプのものが良いですか、
それとも、記述の自由度が高く融通が利くタイプの方
が良いと思いますか?
プログラム開発の効率を上げるためには、次のどちら
の要因を(より)重視しますか?
① 言語の文法を厳しくし、文法エラーのチェックレベルを高めることで、
エラー発生をできるだけ未然に防ぐようにする。
② プログラム開発の手法をプログラマが身につけ、結果的にエラーを
減らすようにする。
第6回目レポート




前の2点について、あなたはどちらの意見です
か?あなたの意見と、そう考える理由をできる限
り明確に説明して下さい。いずれも200字程度。
なお、上の記述を行った上で,(いつも通り)講義
の感想や質問等を付加しても結構です。
提出先:[email protected]
件名:「学籍番号(半角)+半角空白+氏名」を
記入して下さい。
例) s02xxx 学院太郎
形式言語理論との関係
言語の種類
受理するオートマトン
句構造文法言語
チューリング機械
文脈依存文法言語
線形有界オートマトン
文脈自由文法言語
プッシュダウンオートマトン
正規文法言語
有限オートマトン
コンパイラ(+コンピュータ)→オートマトンの一種
数学による統一的理解の例(補足)
ガリレオ・ガリレイの言葉
自然は、数学という言語によって書かれている。
 同時に彼は、当時の数学の限界も認識していた。
 その数学とは・・・ 微積分学
 ガリレオの死後、ニュートンによって完成される。
 地上の運動と、天上の運動を(微積分学に基づ
く)力学として統一的に理解することに成功。

リンゴが木から落ちることと、月が地球を回る運動は同じ。
ダウンロード

講義スライド