### Abstract

We consider the following ways of extending a family of languages $K$ to an "enriched" family $X(K)$: (i) hyper-algebraic extension ($X = H$) based on iterated parallel substitution, (ii) algebraic extension ($X = A$) obtained by nested iterated substitution, (iii) rational extension ($X = R$) achieved by not-self-embedding nested iterated substitution, and (iv) a few subrational extensions ($X = M, S, P, F, C$) based on several kinds of substitution. We introduce full $X$-AFL's, i.e. nontrivial families closed under finite substitution, intersection with regular sets and under $X$, which turn out to be equivalent to well-known AFL-structures such as full hyper-AFL ($X = H$), super-AFL ($A$), substitution-closed AFL ($R$), semi-AFL ($S$), etc. Then we establish Canonical Forms for the smallest full $X$-AFL $\hat{\cal X}(K)$ containing $K$, i.e. we decompose the operator $\hat{\cal X}$ into simpler operators. Using Canonical Forms for full $X$-AFL's we obtain expressions for the smallest full $X$-AFL containing the result of substituting a family of languages into another family.

Original language | Undefined |
---|---|

Place of Publication | Enschede |

Publisher | University of Twente, Department of Applied Mathematics |

Number of pages | 34 |

Publication status | Published - 1977 |

### Keywords

- HMI-SLT: Speech and Language Technology
- EWI-3713

## Cite this

Asveld, P. R. J. (1977).

*Extensions of Language Families and Canonical Forms for Full AFL-Structures*. Enschede: University of Twente, Department of Applied Mathematics.