第2回

オートマトン
DFAの記述方法
  • A=(Q,Σ,δ,q0,F)
    • Q:状態の有限集合
    • Σ:有限のアルファベット(入力記号の有限集合)
    • δ:遷移関数
      • δ：Q×Σ→Q(×は直積)
    • q0:開始状態
    • F:最終状態・受理状態の集合
  • 遷移表
  • 遷移図
受理

遷移図に以下を満たすパスが存在する

  • 開始状態で始まる
  • 最終状態で終わる
  • ラベルの列がa1,a2,a3,…,an

とき、文字列ω=a1a2a3…anは受理される。
数学的な表現は省略

非決定性オートマトン