iBet uBet web content aggregator. Adding the entire web to your favor.
iBet uBet web content aggregator. Adding the entire web to your favor.



Link to original content: https://unpaywall.org/10.1007/3-540-44977-9_7
Regex and Extended Regex | SpringerLink
Skip to main content
Springer Nature Link
Log in

Regex and Extended Regex

  • Conference paper
  • First Online:
Implementation and Application of Automata (CIAA 2002)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 2608))

Included in the following conference series:

  • 524 Accesses

Abstract

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. We make a distinction between regex and extended regex; while regex present regular languages, extended regex present 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.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
USD 29.95
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
USD 39.99
Price excludes VAT (USA)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
USD 54.99
Price excludes VAT (USA)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. N. Chapman, Perl-The Programmer’s Companion, Wiley, Chichester, 1997.

    Google Scholar 

  2. Jeffrey E.F. Friedl Mastering Regular Expressions, O’Reilly & Associates, Inc., Cambridge, 1997.

    MATH  Google Scholar 

  3. J.E. Hopcroft and J.D. Ullman, Introduction to Automata Theory, Languages, and Computation, Addison-Wesley, Reading, 1979.

    MATH  Google Scholar 

  4. M.E. Lesk, “Lex-a lexical analyzer generator”, Computer Science Technical Report (1975) 39, AT&T Bell Laboratories, Murray Hill, N.J.

    Google Scholar 

  5. S. Yu, “Regular Languages”, in Handbook of Formal Languages, G. Rozenberg and A. Salomaa eds. pps. 41–110, Springer, 1998.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics and Computer Science, UPEI, PE C1A 4P3, Charlottetown

    Cezar Câmpeanu

  2. Computing and Information Science Department, Queen’ s University, K7L 3N6, Ontario, Kingston, Canada

    Kai Salomaa

  3. Department of Computer Science, University of Western Ontario, N6A 5B7, London, Ontario, Canada

    Sheng Yu

Authors
  1. Cezar Câmpeanu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Kai Salomaa
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Sheng Yu
    View author publications

    You can also search for this author in PubMed Google Scholar

Editor information

Editors and Affiliations

  1. UFR des Sciences et Techniques, Université de Rouen, LIFAR, 76821, Mont-Saint-Aignan Cedex, France

    Jean-Marc Champarnaud

  2. Departement Informatique, Laboratoire d’Informatique de l’Université de Tours École Polytechnique de l’Université de Tours, 64 avenue Jean-Portalis, 37200, Tours, France

    Denis Maurel

Rights and permissions

Reprints and permissions

Copyright information

© 2003 Springer-Verlag Berlin Heidelberg

About this paper

Cite this paper

Câmpeanu, C., Salomaa, K., Yu, S. (2003). Regex and Extended Regex. In: Champarnaud, JM., Maurel, D. (eds) Implementation and Application of Automata. CIAA 2002. Lecture Notes in Computer Science, vol 2608. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-44977-9_7

Download citation

  • DOI: https://doi.org/10.1007/3-540-44977-9_7

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-40391-3

  • Online ISBN: 978-3-540-44977-5

  • eBook Packages: Springer Book Archive

Publish with us

Policies and ethics

Search

Navigation