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.
|Place of Publication||Enschede|
|Publisher||University of Twente, Department of Applied Mathematics|
|Number of pages||41|
|Publication status||Published - 1976|
- HMI-SLT: Speech and Language Technology