Compiling Quantifiers to NFA

Quantifier sub-NFA constructions:

a? — zero or one. Add an ε bypass:

   ε
   ↓
(start) --ε--> (a) --ε--> (end)
        --ε----------------↑

a* — zero or more. Bypass + loop:

   ε
   ↓
(start) --ε--> (a) --ε--> (end)
                   ↑__ε____|
        --ε----------------↑

a+ — one or more. Required first match + loop:

(start) --ε--> (a) --ε--> (end)
                   ↑__ε____|

The trick: every quantifier wrapper has ONE entry and ONE exit, so they nest cleanly. (ab)*c = wrap the ab NFA in a * shell, then concat with c.

For {n,m}: unroll N copies + (M-N) optional copies. a{2,4} becomes aaa?a? essentially. For unbounded {n,}: N concatenated, then a * of the same.

Catastrophic backtracking REGEXes that explode in PCRE:

• (a+)+b — exponential in backtracking engines, linear in NFA
• (a|aa)*c — same
• (a*)* — same

NFA simulation handles all of these in O(text * states), no exceptions.