Skip to content

Regex / Finite Automata Hot Sheet

Use this page when the pattern is a small regular language and the right worldview is "compile to one epsilon-NFA and simulate reachable states," not "run one exact string matcher."

Do Not Use When

  • the pattern is one literal string -> reopen KMP
  • there are many literal patterns against one text -> Aho-Corasick hot sheet
  • the task expects industrial regex features, escapes, captures, or backreferences

Choose By Signal

  • one literal pattern in one text -> KMP or Z
  • many literal patterns in one text -> Aho-Corasick
  • one regex language with |, *, parentheses, and wildcard . -> Thompson NFA

Core Invariants

  • implicit concatenation is made explicit before building the automaton
  • Thompson fragments mean start + unpatched exits
  • every simulation step uses full epsilon-closure
  • full-string match means the accept state is reachable after the whole text

Main Traps

  • confusing this lane with regex-library semantics
  • forgetting that . is wildcard and every other unsupported metachar is just a literal in the starter
  • trying to use this when one exact fixed-pattern route is already enough

Exact Starter Route

Reopen Paths