### Abstract

We investigate derivation-controlled $K$-iteration grammars, called $(\Gamma,K)$-iteration grammars, where $\Gamma$ can be any family of control languages. We prove that already under very weak restrictions on $\Gamma$ and $K$ the following hold: (i) Regular control does not increase the generating power of $K$-iteration grammars, (ii) for each $(\Gamma,K)$-iteration grammar there exists an equivalent propagating $(\Gamma,K)$-iteration grammar, (iii) the family of $(\Gamma,K)$-iteration languages is a full hyper-AFL, (iv) for each $(\Gamma,K)$-iteration grammar there exists an equivalent $(\Gamma,K)$-iteration grammar with exactly two substitutions. We also discuss some additional properties and applications of (uncontrolled) $K$-iteration grammars and controlled (deterministic) ET0L systems and their languages in a wider context.

Original language | English |
---|---|

Pages (from-to) | 248-269 |

Number of pages | 22 |

Journal | Information and Control |

Volume | 34 |

Issue number | 3 |

DOIs | |

Publication status | Published - 1977 |

### Keywords

- HMI-SLT: Speech and Language Technology
- MSC-68A30

## Fingerprint Dive into the research topics of 'Controlled Iteration Grammars and Full Hyper-AFL's'. Together they form a unique fingerprint.

## Cite this

Asveld, P. R. J. (1977). Controlled Iteration Grammars and Full Hyper-AFL's.

*Information and Control*,*34*(3), 248-269. https://doi.org/10.1016/S0019-9958(77)90308-4