zbMATH — the first resource for mathematics

Coordinated pair systems. I: Dyck words and classical pumping. (English) Zbl 0639.68075
The notion of a coordinated pair system, cp system for short, is a special instance of an ects system which in turn provides a common framework for quite a number of grammar and machine models encountered in the literature. In particular, the notion of a cp system corresponds very closely to (is another formulation of) the notion of a push-down automaton.
In this paper we continue the investigation of cp systems and in particular we investigate the possibility of obtaining pumping properties of context-free languages via the analysis of computations in cp systems. In order to do this we analyze the combinatorial structure of Dyck words. The properties of Dyck words we investigate stem from the combinatorial analysis of computations in cp systems. We demonstrate how this correspondence can be used for proving the classical pumping lemma.

68Q45 Formal languages and automata
Full Text: DOI EuDML
[1] J. M. AUTEBERT and J. BEAUQUIER, Une caractérisation des générateurs standard, R.A.I.R.O., R-l, 1974, pp. 63-83. Zbl0294.68031 MR341939 · Zbl 0294.68031 · eudml:92007
[2] Y. BAR-HILLEL, M. PERLES and E. SHAMIROn Formal Properties of Simple Phrase-structure Grammars, Zeitschrift für Phonetik, Sprachwissenschaft, und Kommunikationsforschung, Vol. 14, 1961, pp. 143-177. Zbl0158.25307 MR151376 · Zbl 0158.25307
[3] J. BERSTELTransductions and Context-free Languages, Teubner, Stuttgart, 1979. Zbl0424.68040 MR549481 · Zbl 0424.68040
[4] A. EHRENFEUCHT, H. J. HOOGEBOOM and G. ROZENBERG, Real-time coordinated pair systems, Dept. of Computer Science, University of Colorado at Boulder, Techn. Rep. No. CU-CS-259-83, 1983. · Zbl 0642.68133
[5] A. EHRENFEUCHT, H. J. HOOGEBOOM and G. ROZENBERG, Computations in Coordinated pair Systems, Fundamenta Informaticate (to appear). Zbl0642.68133 MR873639 · Zbl 0642.68133
[6] M. HARRISON, Introduction to Formal Language Theory, Addison-Wesley Publ. Co., Reading, Massachusetts, 1978. Zbl0411.68058 MR526397 · Zbl 0411.68058
[7] G. ROZENBERG, On Coordinated Selective Substitutions: Towards a Unified Theory of Grammars and Machines, Theoretical Computer Sciences, Vol. 37, 1985, pp. 31-50. Zbl0601.68054 MR796312 · Zbl 0601.68054 · doi:10.1016/0304-3975(85)90086-6
[8] A. SALOMAA, Formal languages, Academic Press, London-New York, 1973. Zbl0262.68025 MR438755 · Zbl 0262.68025
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.