スライド 1

形式言語 と オートマト
第2回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
復習
復
形式言語とオートマト
習
復習
機械(オートマトン)による仕事
一定の規則を与えられ,
その通りに作業する
単純な仕事:単純な規則(例:偶奇判別)
複雑さのレベルを上げると
できる仕事のレベルも上がる
複雑な仕事:複雑な規則(例:計算,言語)
形式言語とオートマト
復習
単純な仕事は単純な仕掛けで
2状態だけで判断できるのは
↑
{偶,奇},
形式言語とオートマト
↓
{点,滅},
{合,否}
復習
単純な仕事は単純な仕掛けで
2状態を二つ使えば、4つを区別できる
↑
↑
↓
↓
{(↑↑),(↑↓),(↓↑),(↓↓)}の4つ
形式言語とオートマト
復習
単純な仕事は単純な仕掛けで
8
2状態を3つ使えば、、
{(↑↑↑),(↑↑↓),(↑↓↑),(↑↓↓),
(↓↑↑),(↓↑↓),(↓↓↑),(↓↓↓)}
8つを区別できる
形式言語とオートマト
復習
単純な仕事は単純な仕掛けで
8
2状態をN個使えば、、
{(↑↑…↑↑), (↑↑…↑↓),(↑↑…↓↑),
(↑↑…↓↓),…,(↓↓…↑↓),(↓↓…↓↓)}
2N個を区別できる
形式言語とオートマト
オートマトンの状態遷移図表現
状態遷移図で表す
有限オートマトン
形式言語とオートマト
オートマトンの状態遷移図表現
言語理解の原理 : aとbからなる文字列
規則: bで読み終われば受理する (例abbb,ab)
条件を満す時→「受」で文字列を読み終わる
条件を満さない時→「拒」で文字列を読み終わる
a
b
b
拒
a
形式言語とオートマト
受
オートマトンの状態遷移図表現
例えば,aaを入力してみる
a
a
b
b
拒
a
形式言語とオートマト
受
オートマトンの状態遷移図表現
例えば,aaを入力してみる
a
b
b
a拒
a
形式言語とオートマト
受
オートマトンの状態遷移図表現
例えば,abを入力してみる
a
a
b
b
拒
a
形式言語とオートマト
受
オートマトンの状態遷移図表現
例えば,abを入力してみる
a
b
b拒
形式言語とオートマト
b
1文字読むたびに
受
a 機械の状態が変化
有限オートマトンの5字組み表
現
5字組みで表す
有限オートマト
ン
形式言語とオートマト
有限オートマトンの5字組み表
現
5字組み表現
M= <Q,Σ,δ,q0,F>
Q… 状態の有限集合
Σ … 入力記号
δ … 動作関数
q0 … 初期状態
F … 受理状態の集合
形式言語とオートマト
有限オートマトンの5字組み表
現
5字組み表現(1つめ)
Q = {q1 , q2}
状態の集合
a
b
q1
b
a
形式言語とオートマト
q2
有限オートマトンの5字組み表
現
5字組み表現(2つめ)
Σ = {a , b}
a
b
q1
b
a
入力記号
形式言語とオートマト
q2
有限オートマトンの5字組み表
現
5字組み表現(3つめ)
δ (q1 , a) = q1
δ (q1 , b) = q2
δ (q2 , b) = q2
a
b
q1
δ (q1,b) = q2
b
q2
a
機械が状態q1にいるときに入力bを読むと状態q2に移る
形式言語とオートマト
有限オートマトンの5字組み表
現
5字組み表現(4つめ)
q0 = q 1
a
b
b
q1
q2
a
どの状態が初期状態かを指定する
形式言語とオートマト
有限オートマトンの5字組み表
現
5字組み表現(5つめ)
F = {q1}
a
b
b
q1
q2
a
どの状態が終了状態かを指定する
形式言語とオートマト
有限オートマトンの5字組み表
現
5字組み表現
M= <Q,Σ,δ,q0,F>
Q = {q1 , q2}
Σ = {a , b}
δ :Q×Σ→Q
δ (q1 , a) = q1
δ (q1 , b) = q2
δ (q2 , a) = q1
δ (q2 , b) = q2
q0 = q 1
F = {q1}
形式言語とオートマト
a
q1
b
q2
a
状態遷移図と
5字組みが等価
b
有限オートマトンの5字組み表
現
問題:下図の有限オートマトンを
5字組みで表せ
{a,b}の組み合わせでできる単語のうち
bで終わる単語ばかりを元とする集合
L={b, ab, bb, aab, abb, bbb, …}
a
b
b
q1
a
形式言語とオートマト
q2
復習
小テスト
形式言語とオートマト
(1)
復習
お疲れ様です!
おわり
形式言語とオートマト