Beyond regular : pattern matching with extended regular expressions
Benjamin Carle · ProQuest Demo Repository · 2010
Regular expression pattern matching or some variant thereof is present in almost all software that deal with textual data. In this work we have considered three types of extensions to the traditional regular expression, or regex pattern matching format. Regex pattern matching tools such as those in the Unix utility egrep and the popular scripting language Perl commonly include extended functionality beyond the classical definition of regular expressions. The main focus is on Extended Regular Expressions as studied by Câmpeanu, Salomaa and Yu [1]. We offer an additional pumping lemma that will show that a new class of languages is not recognizable by extended regular expressions and discuss closure properties, decidability, and complexity issues relating to these languages. Another extension of the regular languages considered is the class of Extended Multi-Pattern Languages (EMPL), introduced by Nagy in [2]. We show that this class is a strict subclass of the family of languages recognized by extended regular expressions and discuss the decidability of the equivalence problem for these languages. Synchronized Regular Expressions, as introduced by Penna, Intrigila, Tronci and Zilli [3], extend the EREG languages by allowing exponent variables that range over the natural numbers. We offer some clarifications of the matching semantics and a surprising result regarding linear synchronized regular expressions. A simplified proof of the language of palindromes is provided, showing that the family of languages defined by synchronized regular expressions is not a superset of the context-free languages. Finally, we provide an overview of the relative expressive power of these three classes of languages and relate them to other significant language classes. In conclusion we discuss some current and potential future applications of extended pattern matching and some open problems.