Regex and extended regex
Cezar Câmpeanu, Kai Salomaa, Sheng Yü · 2002
Regex are used in many programs such as Perl, Awk, Python, egrep, vi, emacs etc. It is known that regex are different from regular expressions. In this paper, we give regex a formal treatment making a distinction between regex (regular expressions) and extended regex (extended regular expressions). We prove a pumping lemma for the languages expressed by extended regex. We show that the languages represented by extended regex are incomparable with context-free languages and a proper subset of context-sensitive languages.