# Questions tagged [transducers]

The tag has no usage guidance.

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
59 views

### How to apply insights from the theory of codes to alternating codes?

The book Theory of codes by J. Berstel and D. Perrin from 1985 studies variable-length codes. The focus is less on error-correction and compression, but more on algebraic properties, synchronization ...
34 views

### Regular string relations - proof of correctness

Let $T \subseteq \Sigma^* \times \Sigma^*$ be a regular (rational) relation. We define the obligatory rewrite relation over $T$ as follows: $$R^{obl}(T) := N(T) \cdot (T \cdot N(T))^*$$  N(T) := ...
117 views

### Which transducer models replacement in regex?

I am looking for the right transducer which allows to translate a sequence of literals into a sequence of same literals (or a subset of them) in arbitrary order. For example: ABC => CAB, which, with ...
1 vote
34 views

### Finite-state transducer to accept $i$'th word of DFA

If I have a DFA $D$ that accepts some regular language $L$, is it possible to construct some finite-state transducer $T$ that takes in an index $i$, and puts out the $i$'th word in $L$, ordered ...
1 vote
40 views

### Find a transducer that maps a given deterministic process to another

Let $S$ denote a deterministic process which generates a certain string, described through a Hidden Markov Model. More specifically, for a process with alphabet $\mathcal{A}$ and $n$ hidden states, ...
1 vote
34 views

### How to prove existance and construct finite-state transducer between two different FSM?

For example I have 2 simple FSM. I will use regular expression for clarity. ...
1 vote
33 views

### Chomsky hierarchy for finite state transducers

In this question in the first answer someone mentions a "special transduction hierarchy". I cannot find anywhere anything about it. Could someone point me to resources on this topic?
1 vote
279 views

### Regexp substitution and finite-state transducers

Many programming languages support a "regular expression substitution" operation: if r is a regular expression and s, ...
1 vote
27 views

### almost realtime push down relation vs realtime pushdown relation?

Almost realtime pushdown relation pop a symbol for each empty step. Realtime pushdown relation does not perform any empty step. What do they mean by empty step?
66 views

### Finite state transducer that multiplies numbers

How is possible to construct a finite state transducer that multiplies a number by 5? We can assume that numbers are supplied in binary notation, from least significant bits to most significant.
23 views

Let M a finite state transducer define as : $M=<X,Y,S,\delta,\lambda>$ What we mean by quasi-linear finite automata?
62 views

Can we proof the number of NFSTs with $n$ states : $n.2^{mpn}.2^{n}$ where $p$ is the cardinal of input alphabet and $m$ the cardinal of output alphabet.