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.

### MSC:

 68Q45 Formal languages and automata

### Keywords:

families of languages; iteration; Dyck language

Zbl 0568.00020