• DocumentCode
    2338788
  • Title

    On proving languages non-regular

  • Author

    Chedid, Fouad B.

  • Author_Institution
    Dept. of Comput. Sci., Notre Dame Univ., Zouk Mosbeh, Lebanon
  • fYear
    2010
  • fDate
    16-19 May 2010
  • Firstpage
    1
  • Lastpage
    3
  • Abstract
    A well known characterization of regular languages is provided by Nerode´s Theorem. However, the pumping lemma is often a more useful tool in demonstrating properties of regular languages. In this paper, we rewrite an early pumping characterization of regular languages due to Stanat and Weiss so that some extra condition is made explicit in the theorem. This should allow for writing simpler proofs. Also, we present two new variations of the non-pumping lemma of Zhang and Canfield. These are necessary conditions only for regularity. Still, a non-pumping lemma uses a simpler logic compared to the standard pumping lemma. Finally, we present a generalization of the non-pumping lemma that is applicable to our variations as well. Our generalization allows for simpler proofs.
  • Keywords
    formal languages; set theory; nonpumping lemma; nonregular language; pumping characterization; regular language; Artificial neural networks; Automata; Computer science; Doped fiber amplifiers; Facsimile; Indexes; Writing; Automata Theory; Non-Pumping Lemma; Pumping Lemma; Regular Languages;
  • fLanguage
    English
  • Publisher
    ieee
  • Conference_Titel
    Computer Systems and Applications (AICCSA), 2010 IEEE/ACS International Conference on
  • Conference_Location
    Hammamet
  • Print_ISBN
    978-1-4244-7716-6
  • Type

    conf

  • DOI
    10.1109/AICCSA.2010.5586960
  • Filename
    5586960