解決済みの質問
有限オートマトンの質問です。 ε-NFAからεを除去の仕方がわかりません。 教科書...
有限オートマトンの質問です。
ε-NFAからεを除去の仕方がわかりません。
教科書の例題から除去の規則性を探そうとがんばったのですが
結局わかりませんでした。
おしえてください。
よろしくお願いします。
- 補足
- その規則性が通用しない問題があるのですが・・・
-
- 質問日時：
- 2010/1/17 18:09:21
-
- 解決日時：
- 2010/2/1 06:13:05
-
- 回答数：
- 1
-
- 閲覧数：
- 334
-
- ソーシャルブックマークへ投稿：
- Yahoo!ブックマークへ投稿
- はてなブックマークへ投稿
- （ソーシャルブックマークとは）
ベストアンサーに選ばれた回答
δε-NFA 0 1 ε
s1 ― {s1} {s2}
s2 {s2} ― {s3}
s3 {s3} ― ―
のとき
δNFA 0 1
s1 {s2,s3} {s1,s2,s3}
s2 {s2,s3} {s3}
s3 {s3} ―
とεを除去できます。
この規則は、
各節点(s1,s2,s3)からεのみで遷移できる全て節点を全ての出力(0,1)に加えます。
それだけでεの除去ができます。
追記
もう1つ規則があったのを書き忘れていましたので書きます
初期状態からεのみで受理状態に遷移できる場合、
受理状態に初期状態を追加する。
おそらくこの規則を追加したことで
”規則性が通用しない問題”
も除去できると思います。
- 違反報告
- 編集日時：2010/1/18 21:30:14
- 回答日時：2010/1/18 01:32:25
この質問は投票によってベストアンサーが選ばれました！
- この質問・回答は役に立ちましたか？
- 役に立った！
お役立ち度：
2人が役に立つと評価しています。
