• UNIXのegrepコマンドで使用
• 任意の正規表現パタンを使用可能
• アルゴリズム
  • 正規表現からNFA(非決定性状態遷移機械)を作成
  • NFAからDFA(決定性状態遷移機械)を作成
  • DFAを表現する遷移テーブルを作成
• パタン作成の手間はかかるがパタンマッチ実行は高速