Regex and Finite Automata
The cluster focuses on the theoretical equivalence between regular expressions and finite state machines like DFAs and NFAs, contrasted with practical regex engines that support non-regular features such as backreferences and backtracking.
Activity Over Time
Top Contributors
Keywords
Sample Comments
Regex is equivalent to Finite Automata
Aren’t regular expressions the abstraction to state machines? They all get converted to a DFA or NFA, no?
Regular expressions (in the original computer science sense) can be matched by finite-state automata!
Why? Aren’t all regular expressions equivalent to some finite state machine?
A strict theoretical regex yes, but a lot of regex implementations in practice are not strict NFA/DFAs and may indeed be turing complete
Perl's regex engine must use something stronger than plain NFAs. The expressive power of NFAs and DFAs is exactly the same. They both recognize the regular languages, which is less than what can be expressed with Perl "regular expressions".
What are DFAs/NFAs? I didn't see them defined in the article.
Just wondering: why do you build a regex and not directly a finite state automaton? Sure, you can not have backreferences, but you can use Hopcroft minimization, etc.
Not as frequent as you might expect! Most regex engines in common use don't use an automata based implementation, and instead use backtracking. This lets them implement additional non-regular features such as backreferences and recursion.Even automata based regex engines don't usually build up a full DFA, since the size of the DFA may be exponential in the size of the regex. Instead, an NFA similation might be used, or a hybrid NFA/DFA that builds the DFA during match time, but
Why are they called regular expressions if they can parse non-regular languages?