grammar - 決定論的有限オートマトンの構築に助けが必要ですか?

Question

ダイアグラムの形で決定論的有限オートマトンを構築するためのルールは何ですか? 私の教授は例を挙げて説明してくれましたが、すべての図がどの規則に従わなければならないのか正確にはわかりません。どんな助けでも大歓迎です、ありがとう！

Answer 1

DFA の主なルールは次のとおりです (DFA 固有の用語は二重引用符で囲みます)。

• 各「状態」には、DFA で定義された「入力」ごとに「遷移」が
  必要です。つまり、状態について、dfa で考慮されるすべての入力に対して遷移を定義する必要があるため、どこから移動するかがわかります。各入力のその状態。
  

• 各「状態」は、各「入力」に対して 1 つの「遷移」のみを持つことができます。
  このルールは一目瞭然です。そのため、特定の状態の入力の遷移を既に定義している場合は、同じ入力に対して別の遷移を作成しないでください。同じ州から。
  

ええ、これらは私が覚えているものです。それが役に立てば幸い。さらに、これらのポイントを使用して、dfa と nfa を区別することができます。描画のための他の簡単なルールは次のとおりです:-

• 状態を指す矢印で示される開始状態を作成します
  

• 状態の境界を描く同心円で示される、少なくとも 1 つの最終状態がある
  

• トランジションを矢印で描く
  

• すべての遷移をそれぞれの入力記号でマークします