Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Theses and dissertations
Ad Astra association
Press releases
Funding opportunities
>> Românã

CEZAR CAMPEANU, KAI SALOMAA, SHENG YU. A FORMAL STUDY OF PRACTICAL REGULAR EXPRESSIONS. International Journal of Foundations of Computer Science, 14, No. 6, pp. 1007-1018, 2003.

Abstract: Regular expressions are used in many practical applications. Practical regular expressions are commonly called "regex". It is known that regex are different from regular expressions. In this paper, we give regex a formal treatment. We make a distinction between regex and extended regex; while regex represent regular languages, extended regex represent a family of languages larger than regular languages. 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. Other properties of the languages represented by extended regex are also studied.

Keywords: Regular expressions; regex; extended regex; formal languages; programming languages


Posted by Cezar Campeanu


© Ad Astra 2001-2013