About two-way transducers. (English) Zbl 0574.68067

Fundamentals of computation theory, Proc. 5th Int. Conf., Cottbus/Ger. 1985, Lect. Notes Comput. Sci. 199, 371-379 (1985).
[For the entire collection see Zbl 0568.00020.]
We consider the families of languages produced by two-way transducers, and prove iteration lemmas for them. Thus it is shown that the Dyck language \(D'{}^*_ 1\) doesn’t belong to the deterministic family, and consequently that the Dyck language \(D'{}^*_ 2\) doesn’t belong to the non-deterministic one. Therefore the Dyck language \(D'{}^*_ 1\) is not an EDTOL language.


68Q45 Formal languages and automata


Zbl 0568.00020