第１回：はじめに、11 12pdf 最近の更新履歴 Hideo Fujiwara

形式言語とオートマトン

藤原秀雄

2

講義スタイル

◆  教科書を使って講義します。

 図や表はスライド（プロジェクター）を使い、

 教科書の内容は、ホワイトボードに板書しながら説明します。

◆  毎回出席を取ります。

 講義の理解を深めるために、毎回簡単な小テストを行います。

◆  定期試験では教科書持ち込み可です。

 日頃から、授業の予習、復習に、教科書を活用してください。

 評価基準・方法：

定期試験（筆記試験）   ６０％

日常点（出席、小テスト） ４０％

3

教科書

富田悦次 _/ 横森貴 共著 オ トマトン 言語理論 第２版

^森北出版

4

講義テーマ・概要

  テーマ： コンピュータサイエンスの基礎知識

Computer Science   計算機科学 

コンピュータサイエンスの中核をなす概念

「オートマトン」と「形式言語」

5

講義テーマ・概要（つづき）

コンピュータ ＝ ハードウエア ＋ ソフトウエア

CPU

　　制御回路 論理回路 　　演算回路 論理回路

OS, ^プログ 集積回路 _LSI

オートマトン ＝ ハードウエアとしての

コンピュータの数学的モデル

形式言語  = ソフトウエアとしての

プログラミング言語の数学的モデル

6

講義テーマ・概要（つづき）

本講義の目的：

コンピュータに関する最も基本的な概念である

「計算の原理」を

数学的、論理的に理解するために必要な基礎知識を

学習すること

1.1 オートマトンと言語

1.1.1 オートマトンとは

ある入力に対して、その処理を自動的に実行し、適切な応答を出力する ディジタルシステムをできるだけ単純にモデル化したもの

１ページ

1.1.1 オートマトンとは（つづき）

例： 切符の自動販売機

入力： 逐次投入される硬貨の系列

処理： 投入された金額の合計を計算、記憶し、

その合計が所定の値に達したならば

切符と釣銭を出力

出力： 切符と釣銭

入力 出力

処理 記憶

１ページ

入力 出力

処理 記憶

1.1.1 オートマトンとは（つづき）

入力は抽象的に、0,1, …  あるいは a, b, … などの記号で表し 入力記号と呼ぶ

例：  

_Σ

010

010001

10101111 入力記号列 あるいは 入力記号 と呼ぶ

２ページ

1.1.2 形式言語とは

自然言語：  日本語  英語  フランス語

プログラミング言語： FORTRAN  Pascal  C   Java

形式言語（or 数理言語）：  それらを抽象化した言語

２ページ

1.1.2 形式言語とは（つづき）

文を構成する最小単位要素   英語では単語

それらの集合を Σ で表す

文は、それらの記号から構成される記号列

言語は、そのような記号列のうちで特定の条件を満たすものだけの集まり

これは、英語では英文法的に正しい文だけの集まり全体を 英語 という言語 とみなすことに相当する

２ページ

1.1.2 形式言語とは（つづき）

形式的には

Σ = {a₁, a₂, … , a_m}

としたとき、Σ 中の記号を重複を許して有限個並べて得られる w ＝ a_i1a_i2 … a_in

を、Σ上の記号列 あるいは 系列 という

¦w¦ 記号列wの長さ（wを構成している記号の個数）

特に、長さが０の記号列を 空記号列 あるいは 空系列 とよび ε （イプシロン）で表す

例： Σ = {0,1} w=01011 ¦w¦ = 5 ¦ε¦ = 0

３ページ

1.1.2 形式言語とは（つづき）

記号列 x と y に対して

xy xとyの連接(concatenation)

例： x = a_i1…a_in y=b_i1…b_im xy = a_i1…a_inb_i1…b_im

記号列 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 = a_i1…a_in において a_i1 = … = a_in= a のとき

w = a

空記号列εを含めて、Σ上で作り得るすべての記号列の無限集合を

_Σ*

と表し、これをΣのスター閉包(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)

４ページ

５ページ

５ページ

５ページ

６ページ

A _B

６ページ

６ページ

７ページ

７ページ

A B

７ページ

７ページ

７ページ

７ページ

A x B = {(a,b), (a,c), (b,b), (b,c)}