形式言語とオートマトン
藤原秀雄
2
講義スタイル
◆ 教科書を使って講義します。
図や表はスライド(プロジェクター)を使い、
教科書の内容は、ホワイトボードに板書しながら説明します。
◆ 毎回出席を取ります。
講義の理解を深めるために、毎回簡単な小テストを行います。
◆ 定期試験では教科書持ち込み可です。
日頃から、授業の予習、復習に、教科書を活用してください。
評価基準・方法:
定期試験(筆記試験) 60%
日常点(出席、小テスト) 40%
3
教科書
富田悦次 / 横森貴 共著 オ トマトン 言語理論 第2版
森北出版
2 800円 税 �4
講義テーマ・概要
テーマ: コンピュータサイエンスの基礎知識
Computer Science 計算機科学
コンピュータサイエンスの中核をなす概念
「オートマトン」と「形式言語」
5
講義テーマ・概要(つづき)
コンピュータ = ハードウエア + ソフトウエア
CPU
制御回路 論理回路 演算回路 論理回路
OS, プログ 集積回路 LSI
オートマトン = ハードウエアとしての
コンピュータの数学的モデル
形式言語 = ソフトウエアとしての
プログラミング言語の数学的モデル
6
講義テーマ・概要(つづき)
本講義の目的:
コンピュータに関する最も基本的な概念である
「計算の原理」を
数学的、論理的に理解するために必要な基礎知識を
学習すること
7
講義スケジュール(授業計画)
第1回 はじめに 1.1 オートマトンと言語 第2回 1.2 基礎的な数学的準備
第3回 2.1 順序機械 第4回 同上
第5回 2.2 有限オートマトン 第6回 同上
第7回 同上
第8回 2.3 非決定性有限オートマトン 第9回 同上
第10回 2.4 言語演算 第11回 2.5 正規表現 第12回 同上 第13回 3.1 形式文法 第14回 3.2 正規文法 第15回 同上
第16回 定期試験(筆記試験) 評価基準・方法
定期試験 60% 日常点 40%
1.1 オートマトンと言語
1.1.1 オートマトンとは
ある入力に対して、その処理を自動的に実行し、適切な応答を出力する ディジタルシステムをできるだけ単純にモデル化したもの
1.1.1 オートマトンとは(つづき)
例: 切符の自動販売機
入力: 逐次投入される硬貨の系列
処理: 投入された金額の合計を計算、記憶し、
その合計が所定の値に達したならば
切符と釣銭を出力
出力: 切符と釣銭
入力 出力
処理 記憶
入力 出力
処理 記憶
1.1.1 オートマトンとは(つづき)
入力は抽象的に、0,1, … あるいは a, b, … などの記号で表し 入力記号と呼ぶ
例:
Σ
= {0, 1} 0と1の2記号からなる集合 Σ(シグマ)010
010001
10101111 入力記号列 あるいは 入力記号 と呼ぶ
1.1.2 形式言語とは
自然言語: 日本語 英語 フランス語
プログラミング言語: FORTRAN Pascal C Java
形式言語(or 数理言語): それらを抽象化した言語
1.1.2 形式言語とは(つづき)
文を構成する最小単位要素 英語では単語
それらの集合を Σ で表す
文は、それらの記号から構成される記号列
言語は、そのような記号列のうちで特定の条件を満たすものだけの集まり
これは、英語では英文法的に正しい文だけの集まり全体を 英語 という言語 とみなすことに相当する
1.1.2 形式言語とは(つづき)
形式的には
Σ = {a1, a2, … , am}
としたとき、Σ 中の記号を重複を許して有限個並べて得られる w = ai1ai2 … ain
を、Σ上の記号列 あるいは 系列 という
¦w¦ 記号列wの長さ(wを構成している記号の個数)
特に、長さが0の記号列を 空記号列 あるいは 空系列 とよび ε (イプシロン)で表す
例: Σ = {0,1} w=01011 ¦w¦ = 5 ¦ε¦ = 0
1.1.2 形式言語とは(つづき)
記号列 x と y に対して
xy xとyの連接(concatenation)
例: x = ai1…ain y=bi1…bim xy = ai1…ainbi1…bim
記号列 w = xyz において
x を w の接頭辞(prefix) z を wの接尾辞(suffix)という x, y, z は w の部分記号列という
ここで、x, y, z は空記号列 ε のときは εyz = yz xεz = xz xyε= xy
1.1.2 形式言語とは(つづき)
w = ai1…ain において ai1 = … = ain = a のとき
w = a
nと表すこともある
空記号列εを含めて、Σ上で作り得るすべての記号列の無限集合を
Σ*
と表し、これをΣのスター閉包(star closure)とよぶ
スター閉包の例:
Σ = {0,1}
Σ* = {ε, 0, 1, 00, 01, 10, 11, 000, 001, 010, 011, 100, 101, …}
Σ = {a, b, c}
Σ* = {ε, a, b, c, aa, ab, ac, ba, bb, bc, ca, cb, cc,
aaa, aab, aac, aba, abb, abc, aca, acb, acc, baa, bab, … }
1.1.2 形式言語とは(つづき)
1.1.2 形式言語とは(つづき)
Σ* の中からある特定の条件を満たす記号列だけを集めた集合 L を Σ上の言語という
形式文法
Σ アルファベット(alphabet) Σ上の記号列を語(word)