finite-automata - DFAはイプシロン/ラムダ転移を持つことができますか？

Question

それについて肯定的なものを見つけることができません。そして、イプシロン遷移を伴うNFAはイプシロン-NFAですか？ありがとう。

Answer 1

DFAにはイプシロン遷移がありません。イプシロン遷移がある場合は、入力なしで、つまり{}やファイでさえも、現在の状態から他の状態に遷移する可能性があります。そして定義として、入力は入力セットからでなければならないことがわかっています。これがあなたの疑問を解決したことを願っています...

Answer 2

DFAの定義から、「決定性有限オートマトンは、入力を取得せずに他の状態に移動できないマシンです」。また、イプシロンは意味がないため、DFAはイプシロンの移動で移動できません。

一方、NFAの定義から、「非決定性有限オートマトンは、入力を取得せずに他の状態に移動する可能性があるマシンです」。したがって、NFAはイプシロン移動で移動できます。

Answer 3

DFAには、ある状態から別の状態に移動するための明確な入力記号が必要です。イプシロンの移動は、DFAをNFAに変更するため、DFAでは許可されていません。たとえば、状態Q1にあり、遷移（Q1、e）= Q2があるとします。この場合、入力を適用せずに直接Q2に移動するか、Q1状態にとどまることができるため、2つの選択の機会があります。状態Q1で。DFAの場合、選択基準を設定してはなりません。そのため、DFAにはイプシロンムーブがありません。

Answer 4

開始状態が終了状態でもある場合、faはlamdaを受け入れます。また、faがlamdaを使用してある状態から次の状態への遷移を具体的に示している場合、lamdaは入力と見なすことができます。