Abstract
We investigate derivation-controlled $K$-iteration grammars, called $(\Gamma,K)$-iteration grammars, where $\Gamma$ stands for a family of control languages. The control consists of a language in the family $\Gamma$ over the indices ("names") of the substitutions, prescribing the specific order in which one has to apply the substitutions. We show that under certain restrictions on the families $\Gamma$ and $K$ (which we tried to keep as simple as possible) the following holds.
(1) Regular control does not increase the generating power of $K$-iteration grammars. (2) For each $(\Gamma,K)$-iteration grammar there exists an equivalent propagating $(\Gamma,K)$-iteration grammer. (3) The family of $(\Gamma,K)$-iteration languages is a full hyper-AFL. (4) For each arbitrary $(\Gamma,K)$-iteration grammar there exists an equivalent $(\Gamma,K)$-iteration grammar with exactly two substitutions.
Finally, we discusssome consequences and additional properties of (uncontrolled) $K$-iteration grammars and controlled (deterministic) ETOL systems and their languages.
Original language | Undefined |
---|---|
Place of Publication | Enschede |
Publisher | University of Twente, Department of Applied Mathematics |
Number of pages | 41 |
Publication status | Published - 1976 |
Keywords
- EWI-3675
- HMI-SLT: Speech and Language Technology