A Pumping Theorem for EDTOL Languages ; CU-CS-047-74
Andrzej Ehrenfeucht, Grzegorz Rozenberg · CU Scholar (University of Colorado Boulder) · 1974
This paper is concerned with deterministic ETOL languages. A theorem is proved which, roughly speaking, says that if an ETOL language contains a word which a special property then it must contain an infinite set of words obtained from the given one by “synchronously pumping” a number of subwords of the given word. This theorem has numerous applications for proving that certain languages are not deterministic ETOL languages.