<p>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 <em>principal trio</em>'s. Examples include families of <em>linear</em>, <em>blind counter</em> and <em>one turn counter</em> languages (fixed number of counters).<br>
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). </p>

CC BY-SA 3.0
2012-10-16T22:56:21.280Z
2012-10-16T22:56:21.280Z
Hendrik Jan
<p>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.</p>

CC BY-SA 3.0
2012-10-01T17:43:30.940Z
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).
Sylvain
<fl.formal-languages><context-free-languages>
Rational Functions and CFL
Alexander Rubtsov
# Rational Functions and CFL

(Asked by: username_0 on 2012-10-01)

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.

**Tags:** fl.formal-languages, context-free-languages

> **Comments:**
> **username_1**: 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).  

---

## 1 answers

### Answer by username_2 on 2012-10-16. Score: 4 | Accepted answer

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).


---

