Finite state sequential transducers are considered, by using the mechanism of iterated transduction. Their power in defining classes of languages is studied by investigating the hierarchy on the number of state. This hierarchy collapses: four states are enough in order to characterize the recursively enumerable languages. Three states cover the ETOL languages, while two states can cover the EOL (hence also context-free) languages. The case of deterministic transducers remains open.
File in questo prodotto:
Non ci sono file associati a questo prodotto.