2 ms·
The problem is when combining the complement of an expression with another expression (such as when constructing an alternation of the two), because then the co
by layer8 4y ago
The problem is when combining the complement of an expression with another expression (such as when constructing an alternation of the two), because then the complement expression has to be constructed for one of the two, and that can grow double-exponentially in length: https://en.wikipedia.org/wiki/Regular_expression#Expressive_power_and_compactness https://en.wikipedia.org/wiki/Regular_expression#Expressive_...