1 - 鳥取大学

形式言語 と オートマト
第4回
鳥取大学工学研究科
情報エレクトロニクス専攻
田中美栄子
本日の予定
形式言語とオートマト
本日の予定
“有限状態オートマトン”は
最終評価の6割を占めます。
もし、今までの授業で分かっていない人がいたら
今日の授業で追いつきましょう!
形式言語とオートマト
小テスト解説
問1 下図のように状態遷移する偶奇判定機がある、
このオートマトンを5字組みM=<Q,Σ,δ,q0,F>
で定義せよ
a
偶
奇
a
形式言語とオートマト
小テスト解説
=答=
Q={偶,奇}
Σ={a}
δ(偶, a)=奇,δ(奇,a)=偶
q0=偶
F={偶}
形式言語とオートマト
a
偶
奇
a
小テスト解説
五字組みの確認
FSA: M = <Q, Σ, d, q, F> の5字組
・ Q : 状態の集合
・ Σ : 使用するアルファベット
・ d : 動作関数
・ q :初期状態
・ F : 受理状態の集合
形式言語とオートマト
小テスト解説
問2
次の有限オートマトンMに言語”ababb”が入力された時の変遷を様相で表せ。
また、受理されるかどうかを記せ。
M=<Q,Σ,δ,q0,F>
ここで、
Q={A,B,C,D}
Σ={a,b}
δ:Q×Σ→Q
δ(A,a)=B, δ(A,b)=C,
δ(B,a)=A, δ(B,b)=D,
δ(C,a)=D, δ(C,b)=A,
δ(D,a)=C, δ(D,b)=B
q0=A
F={D}
形式言語とオートマト
とする
小テスト解説
問2
M=<Q,Σ,δ,q0,F>
Q={A,B,C,D}
Σ={a,b}
δ:Q×Σ→Q
δ(A,a)=B, δ(A,b)=C,
δ(B,a)=A, δ(B,b)=D,
δ(C,a)=D, δ(C,b)=A,
δ(D,a)=C, δ(D,b)=B
q0=A
F={D}
形式言語とオートマト
a
図で
表す
A
B
a
b
b
b
b
a
C
D
a
小テスト解説
問2
↦
=答= (A,ababb)
↦
M
M
(B,babb)
(C,bb)
↦
M
↦
M
(D,abb)
(A,b)
↦
M
(C,ε)
a
結果:受理されない
A
B
a
b
b
b
b
a
C
D
a
形式言語とオートマト
練習問題
下図の有限オートマトンが受理する入力列を書け
また、この有限オートマトンを五字組みで示せ
形式言語とオートマト
練習問題
=答え=
受理する入力列の例:
a
aaa
aaaa
など。
形式言語とオートマト
練習問題
=答え=
五字組み
Q={S0,S1,S2}
Σ={a}
δ(S0, a)=S1
δ(S1, a)=S2
δ(S2, a)=S0
q0=S0
F={S0,S1}
形式言語とオートマト
練習問題
下図の有限オートマトンが受理する入力列を書け
また、この有限オートマトンを五字組みで示せ
形式言語とオートマト
練習問題
=答え=
受理する入力列の例:
0
0111
000101
1010
など。
形式言語とオートマト
練習問題
=答え=
五字組み
Q={S1,S2,S3}
Σ={0,1}
δ(S1, 0)=S3,δ(S1,1)=S2
δ(S2, 0)=S2,δ(S2,1)=S1
δ(S3, 0)=S2,δ(S3,1)=S3
q0=S1
F={S3}
形式言語とオートマト
形式言語とオートマト