Title :
On proving languages non-regular
Author :
Chedid, Fouad B.
Author_Institution :
Dept. of Comput. Sci., Notre Dame Univ., Zouk Mosbeh, Lebanon
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;
Conference_Titel :
Computer Systems and Applications (AICCSA), 2010 IEEE/ACS International Conference on
Conference_Location :
Hammamet
Print_ISBN :
978-1-4244-7716-6
DOI :
10.1109/AICCSA.2010.5586960