計算理論の基礎 1

メモ 計算理論

まあ、簡単なメモ

第1章 正規言語

  • 決定性有限オートマトン(DFA)の定義
  • 正規言語をDFAで認識される言語として定義
  • 正規演算の定義
    • 和集合演算、連結演算、スター演算
  • 非決定性有限オートマトン(NFA)の定義
  • DFAとNFAは等価
  • 正規言語をNFAで認識される言語として特徴付けられる
  • 正規言語のクラスは正規演算に関して閉じている
  • 正規表現の定義
  • 言語は正規表現で記述されるとき、かつそのときに限り正規言語である。
  • 正規言語に対するポンピング補題

状態数最小のオートマトンの話題は扱っていない。