Questions tagged [regular-expressions]

Questions about the theory of regular expressions, both in the sense of Kleene's original definition and of POSIX regular expressions.

Filter by
Sorted by
Tagged with
45
votes
4answers
11k views

Is finding the minimum regular expression an NP-complete problem?

I am thinking of the following problem: I want to find a regular expression that matches a particular set of strings (for ex. valid email addresses) and doesn't match others (invalid email addresses). ...
30
votes
4answers
1k views

Are there “small” machines which can efficiently match regular expressions?

It's well-known that a regular expression can be recognized by a nondeterministic finite automaton of size proportional to the regular expression, or by a deterministic FA which is potentially ...
22
votes
4answers
3k views

Where do most REGEX implementations fall on the complexity scale?

Most modern implementations of regular expressions, such as the ones in perl or .NET, go beyond the classical computer science definition of REGEXes with features like lookahead and lookbehind. Do ...
39
votes
6answers
6k views

Regular expressions aren't

Ask even someone with a background in computer science what a regular expression is, and the answer is likely to go beyond the constraint of being within reach of a finite-state automaton. For ...
16
votes
3answers
2k views

Can a nondeterministic finite automata (NDFA) be efficiently converted to a deterministic finite automata (DFA) in subexponential space/time?

Twenty years ago, I built an regular expression package that included conversions from regular expressions to a finite state machine (DFA) and supported a host of closed regular expression operations ...

1
2