Two-way a-transducers and AFL

摘要

For each (abstract family of languages) AFL ℒ, two families of languages, the family ℐ(ℒ) of nondeterministic and the family Download : Download full-size image of deterministic two-way a-transducer mappings of languages in ℒ are defined. For each (abstract family of acceptors) AFA Download : Download full-size image, two associated AFA, Download : Download full-size image, are defined. It is proved that Download : Download full-size image. If ℒ is an AFL, then ℐ(ℒ) and Download : Download full-size image are full AFL and are closed under reversal. If ℒ is a full principal AFL, then so is ℐ(ℒ). If a full AFL ℒ is closed under substitution, then so are ℐ(ℒ) and Download : Download full-size image. If ℒ is a full AFL, then each one-letter language in Download : Download full-size image is also in ℒ. For each AFL Download : Download full-size image. In contrast, if ℒ is a subAFL of the family of context-free languages, then Download : Download full-size image and hence ℐ ℐ(ℒ) ≠ ℐ(ℒ).