Ad Astra Awards
Ad Astra Journal
Science library
White book
University rankings
Who's who
Publications
Theses and dissertations
Ad Astra association
 
Press releases
News
Events
Funding opportunities
 
Login
Registration
 
>> 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

URL: http://www.worldscinet.com/ijfcs/14/1406/S012905410300214X.html

Posted by Cezar Campeanu

Back

   
© Ad Astra 2001-2013