Donald F. Stanat
- Jaffe, Jeffrey, A Necessary and Sufficient Pumping Lemma for Regular Languages, ACM SIGACT News, Vol. 10, No. 2, Summer 1978, pp. 48--49. Google Scholar
Digital Library
- Rabin, M. O., and D. Scott, Finite Automata and Their Decision Problems, IBM Journal of Research and Development, Vol. 3, No. 2, April 1959, pp. 114--125. Reprinted in Sequential Machines: Selected Papers, B. F. Moore, ed., Addison-Wesley, 1964.Google ScholarDigital Library
Index Terms
- A pumping theorem for regular languages
Recommendations
Unambiguity in timed regular languages: automata and logics
FORMATS'10: Proceedings of the 8th international conference on Formal modeling and analysis of timed systemsUnambiguous languages (UL), originally defined by Schutzenberger using unambiguous polynomials, are a robust subclass of regular languages. They have many diverse characterizations: they are recognized by partially-ordered two-way deterministic automata ...
Restarting Transducers, Regular Languages, and Rational Relations
A (nonforgetting) restarting transducer is a (nonforgetting) restarting automaton that is equipped with an output function. Accordingly, restarting transducers compute binary relations, and deterministic restarting transducers compute functions. Here we ...
Non-regular Maximal Prefix-Free Subsets of Regular Languages
DLT 2016: Proceedings of the 20th International Conference on Developments in Language Theory - Volume 9840We investigate non-regular maximal prefix-free subsets MPFS of regular languages. We give a method to decide whether or not a regular language has any non-regular MPFS.
Next, we prove that if a regular language has any non-regular MPFS, then it also has ...
Comments