LCS Publication Details
Publication Title: PUMPING LEMMAS FOR REGULAR SETS
Publication Author: Ehrenfeucht, A.
Additional Authors: Parikh, R. and Rozenberg, G.
LCS Document Number: MIT-LCS-TM-170
Publication Date: 8-1-1980
LCS Group: No Group Specified
Additional URL: No URL Given
Abstract:
It is well known that regular languages satisfy certain conditions known as pumping lemmas or iteration theorems. However, the question of the converse result has been open. We show that the usual form of the pumping lemma falls very far short of implying regularity, but that there is a form, which we have called the blocked pumping property, that is equivalent to regularity.
To obtain this publication:

    To purchase a printed copy of this publication please contact MIT Document Services.