In my work arose the problem of classification CFL under rational functions images. In other terms, what class of languages form languages $T(L)$ , for fixed context free language $L$ and deterministic finite state transducer $T$. I've obtained some easy results like Dyck language with two braces corresponds to CFL and Dyck language with one brace is a strict subset of CFL, now there are a few problems that are still interested to me, but I can't believe that nobody have discovered it yet. Are there any papers on this subject? Googling classification of CFL or Rational Functions (Deterministic FST) + CFL gives bad result.

  • 2
    $\begingroup$ The Chomsky-Schützenberger Theorem would fall in this family of results. People (i.e. Ginsburg and others) moved from there to the notion of Abstract Families of Languages (AFL). $\endgroup$
    – Sylvain
    Commented Oct 1, 2012 at 17:43

1 Answer 1


In general the determinism of the transducer seems to be no real restrition. The choices that can be made by a transducer can be moved into the input language. If that is OK for you, the objects sometimes denoted ${\cal M}(L)$ are called principal trio's. Examples include families of linear, blind counter and one turn counter languages (fixed number of counters).
The Habilitation-thesis of Kluas Reinhardt (Counting as Method, Model and Task in Theoretical Computer Science, available on-line) contains a nice inclusion diagram of several families (page 64).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.