スライド 1

形式言語 と オートマト
第1回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
単位をとるに
は?
単位をとるに
は?
形式言語とオートマト
単位をとるに
は?
60点 以上
出 席 : 80% 以上
定期試験:
形式言語とオートマト
単位をとるに
は?
有限状態オートマトン プッシュダウンオートマトン
の時点表示・構成ができること
文脈自由文法が生成する言語・文法
を説明・構成できること
形式言語とオートマト
オートマトンは計算機のモ
デル
オートマトン
は
計算機のモデ
ル
形式言語とオートマト
オートマトンは計算機のモ
デル
オートマトン
形式言語とオートマト
オートマトンは計算機のモ
デル
自動機械 = ロボット
例)茶運び人形
(江戸時代:日本)
形式言語とオートマト
オートマトンは計算機のモ
デル
自動機械 = ロボット
例)高級人形
(ヨーロッパで流行)
形式言語とオートマト
オートマトンは計算機のモ
デル
自動機械 = ロボット
とは?
計算を自動的に行うもの
初期のコンピュータは「計算機」であった
現代のコンピュータも実は「計算するもの」
形式言語とオートマト
形式言語は言語の原型モデル
形式言語
は
言語の原型モデ
ル
形式言語とオートマト
オートマトンは計算機のモ
デル
・プログラム言語のモデル
(C,Java,PASCAL,FORTRAN,LISP,PROLOG)
・自然言語のモデル
(日本語,英語,・・・)
モデルとは・・・?
形式言語とオートマト
言語(文法)とオートマトンの関係
言語(文法)と
オートマトンの
関係
形式言語とオートマト
言語(文法)とオートマトンの関係
複雑さのレベルに応じて4段階
Chomsky階層
機械が計算する = どんな規則に従うか
自動化 = 規則
形式言語とオートマト
言語(文法)とオートマトンの関係
複雑さのレベルに応じて4段階
Chomsky階層
単純な規則の処理しかできない機械
・もう少し複雑な規則の処理ができる機械
・さらに複雑な規則の処理ができる機械
・無制限に複雑な規則の処理ができる機械(汎用)
形式言語とオートマト
言語とオートマトンのChomsky階層
言語とオートマ
トンのChomsky
階層
形式言語とオートマト
言語(文法)とオートマトンの関係
複雑さのレベルに応じて4段階
Chomsky階層
文法が言語を生成する
= どんな規則に従うか
文法 = 規則
形式言語とオートマト
言語とオートマトンのChomsky階層
複雑さのレベルに応じて4段階
Chomsky階層
単純な言語の文法
・もう少し複雑な言語を生成できる文法
・さらに複雑な言語を生成できる文法
・無制限に複雑な言語を生成できる文法(汎用)
形式言語とオートマト
簡単なオートマトンの例
簡単なオートマ
トンの例
形式言語とオートマト
簡単なオートマトンの例
・On-Offスイッチ
点灯→消灯 を繰り返す
(押す回数の奇数偶数を見分ける)
・トースタのサーモスタット
低温:On
高温:Off
形式言語とオートマト
簡単なオートマトンの例
・自動販売機
300円(100円玉3枚)でアイスクリームを
販売する自動販売機の設計
(3の倍数の値を保持)
形式言語とオートマト
簡単なオートマトンの例
繰り返し利用で最小のモデル
ON
形式言語とオートマト
OFF
ON
簡単なオートマトンの例
繰り返し利用で最小のモデル
ON
OFF
形式言語とオートマト
OFF
ON
ON
簡単なオートマトンの例
例題1
10円硬貨を入れて40円の切符を売る
自動販売機の設計
形式言語とオートマト
簡単なオートマトンの例
例題1
10円硬貨を入れて40円の切符を売る
自動販売機の設計
10円 ー 10円 ー 10円 ー 10円 ー
の連鎖で4回ごとに切符を出す
形式言語とオートマト
簡単なオートマトンの例
例題1
10円硬貨を入れて40円の切符を売る
自動販売機の設計
10円
10円
4つの状態
(同値類を使用)
10円
形式言語とオートマト
10円
簡単なオートマトンの例
例題2
10円と50円を一枚ずつ使って60円の切符を
売る自動販売機の設計(おつりなし)
形式言語とオートマト
簡単なオートマトンの例
例題2
10円と50円を一枚ずつ使って60円の切符を
売る自動販売機の設計(おつりなし)
10+50 , 50+10 , 10+10+10+10+10
のどれかなら商品を出す
形式言語とオートマト
簡単なオートマトンの例
例題2
10円と50円を一枚ずつ使って60円の切符を
売る自動販売機の設計(おつりなし)
0円
10円
2種類の入力
:2次元
50円
形式言語とオートマト
60円
言語=通信手段
言語 = 通信手段
形式言語とオートマト
言語=通信手段
戦争の合図
・↑なら進め,↓なら後退
(のろし,火花,
手旗信号,モールス信号)
・↑なら進め,↓なら後退,→なら待機
・↑進め, ↓後退, →待機, ←矢をかける
(だんだん複雑な言葉になってゆく)
・・・余談だが,複合微分の話
形式言語とオートマト