# Tag Info

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.