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
Link To Document :
بازگشت