Recording the use of memory in right-boundary grammars and push-down automata |
| |
Authors: | A Ehrenfeucht H J Hoogeboom and G Rozenberg |
| |
Affiliation: | (1) Department of Computer Science, Rijksuniversiteit Leiden, P.O. Box 9512, 2300 RA Leiden, The Netherlands;(2) Department of Computer Science, University of Colorado at Boulder, 80309 Boulder, CO, USA |
| |
Abstract: | Summary Within the framework of coordinated pair systems a push-down automatonA is formalized as an ordered pair (G
1,G
2) of grammars, whereG
1 is a right-linear grammar modelling the finite state control ofA and the reading of the input ofA, and G2 is a right-boundary grammar modelling the push-down store ofA. In this paper we present a systematic investigation into the use of memory of right-boundary grammars. Various methods of
recording the use of memory are introduced. The results presented concern regularity properties of each of the methods and
the interrelationships of the records obtained by different methods. Finally the translation of these results to the level
of push-down automata (coordinated pair systems) is discussed. |
| |
Keywords: | |
本文献已被 SpringerLink 等数据库收录! |
|