正規表現の実現

  • 同等の状態遷移機械に変換可能
  • e.g. a(b|cd) に対応する文法と状態遷移機械
    • A ← aS
    • B ← bA
    • C ← cA
    • B ← dC