New Iteration Lemmata for Regular Languages

• Autorzy: Dömösi P. , Kudlek M.
• Języki publikacji: EN

Abstrakty

EN

Using well-known characterizations of regular languages, on the basis of known iteration lemmas, new iteration lemmas for regular languages are given.

Słowa kluczowe

EN

regular language; finite automata; pumping lemma

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2005
• Tom: Vol. 64, nr 1-4
• Strony: 151--157
• Opis fizyczny: Bibliogr. 14 poz.

Twórcy

autor

Dömösi P.

• Universität Hamburg Fachbereich Informatik Vogt-Kölln-Str. 30 D-22527 Hamburg, Germany

autor

Kudlek M.

• Fachbereich Informatik, Universität Hamburg D-22527 Hamburg, Vogt-Kölln-Str. 30, D-22527 Hamburg, Germany

Bibliografia

• [1] Y. Bar-Hillel, M. Perles, E. Shamir, On formal properties of simple phrase structure grammars. Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung, 14 (1961), 143–172.
• [2] D.I.A. Cohen, Introduction to Computer Theory. Wiley, New York, 1991.
• [3] A. Ehrenfeucht, R. Parikh, G. Rozenberg, Pumping Lemmas for Regular Sets. SIAM Journal on Computing, 10, 3 (1981), 536–541.
• [4] J.M. Howie, Automata and Languages. Oxford University Press, Oxford, 1991.
• [5] M.A. Harrison, Introduction to Formal Language Theory. Addison-Wesley Publishing Company, Reading, Massachusetts, 1978.
• [6] J.E. Hopcroft, J.D. Ullmann, Introduction to Automata Theory, Languages, and Computation. Addison-Wesley, Reading, Massachusetts, 1979.
• [7] J. Jaffe, A necessary and sufficient pumping lemma for regular languages. SIGACT News, 1978, 48–49.
• [8] S. Marcus, Finite Grammars and Automata. The Publ. House of the Romanian Academy, Bucharest, 1964.
• [9] A. Nijholt, An Annotated Bibliography of Pumping. Bull. EATCS, 17 (1982), 34–52.
• [10] Gy.E. R´ev´esz, Introduction to Formal Languages.McGraw-Hill, New York, 1983.
• [11] A. Salomaa, Formal Languages. Academic Press, New York, 1973.
• [12] A. Salomaa, Computation and Automata. Cambridge University Press, Cambridge, 1985.
• [13] S. Yu, Regular languages. In: G. Rozenberg, A. Salomaa, Eds., Handbook of Formal languages. Vol.1, Springer, 1997, 41–110.
• [14] D. Wood, Theory of Computation.Wiley, New York, 1987.