New answers tagged

5

The following extended regular expression matches the language $\{ ww : w \in \Sigma^* \}$: $$ \texttt{^\\(.*\\)\\1\\\$} $$ This language is neither regular nor context-free. Matching using extended regular expressions is NP-complete; see for example this paper, which discusses efficient algorithms in some special cases.


Top 50 recent answers are included