講義URL:
http://www.kono.cis.iwate-u.ac.jp/~yamanaka/Lecture/Automata/index.html
形式言語とオートマトン
第2回
練習問題の答え解説
山中克久
練習問題2-1
以下の決定性有限オートマトンどんな言語を受理するか?
ただし，Σ = {0,1} とする
1
start
q0
q2
0,1
1
0
q1
(a)
0
1
0
q2
1
Start
q0
0
0
q1
1
(b)
練習問題2-2
以下の言語を受理する決定性有限オートマトンの
状態遷移図を書け．ただし，Σ = {0,1} とする．
（1） { w | w は 101 を部分系列として含む}
（2） { w | w の最後から3番目の文字は 1 である}
練習問題2-3
以下の非決定性有限オートマトンどんな言語を受理するか?
ただし，Σ = {0,1} とする
1
1
start
ε
q0
ε
q1
0
0
0
0
q3
q2
1
1
q4
練習問題2-4
以下の言語を受理する非決定性有限オートマトンの
状態遷移図を書け．ただし，Σ = {0,1} とする．
{ w | w は 101 を部分系列として含む}
練習問題2-1
以下の決定性有限オートマトンどんな言語を受理するか?
ただし，Σ = {0,1} とする
1
start
q0
q2
0,1
1
0
q1
（a）
0
1
0
q2
1
Start
q0
0
0
q1
1
（b）
（a） L（M） = { w | w は，0の次に1が現れるような系列 }
（b） L（M） = { w | wに含まれる 1 の個数から wに含まれる
0の個数を引いた値を x としたとき，x を3で割った時余
が1になる}
練習問題2-2
以下の言語を受理する決定性有限オートマトンの
状態遷移図を書け．ただし，Σ = {0,1} とする．
（1） { w | w は 101 を部分系列として含む}
（2） { w | w の最後から3番目の文字は 1 である}
（1）
（2）
0
start
q0
1
q1
0,1
0
1
0
q2
0
1
q3
0
start
q0
1
0
0
q2
0
1
1
q1
1
1
q4 0
0
q3
1
q5 1
q6
1
0
q7
練習問題2-3
以下の決定性有限オートマトンどんな言語を受理するか?
ただし，Σ = {0,1} とする
1
1
start
ε
q0
ε
q1
0
0
0
0
q3
q2
1
1
q4
Ans.
系列に現れる 0 の個数が偶数か，1の個数が奇数である
ような系列
練習問題2-4
以下の言語を受理する非決定性有限オートマトンの
状態遷移図を書け．ただし，Σ = {0,1} とする．
{ w | w は 101 を部分系列として含む}
0,1
0,1
start
q0
1
q1
0
q2
1
q3
Remind: 決定性有限オートマトンの場合
1
start
q0
1
q1
0,1
0
1
0
q2
1
q3
© Copyright 2024 ExpyDoc
