Questions tagged [transducers]

The tag has no usage guidance.

14 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
3 votes
0 answers
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 ...
user avatar
2 votes
0 answers
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) := ...
user avatar
2 votes
0 answers
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 ...
user avatar
1 vote
0 answers
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 ...
user avatar
  • 206
1 vote
1 answer
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, ...
user avatar
  • 111
1 vote
0 answers
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. ...
user avatar
  • 287
1 vote
0 answers
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?
user avatar
  • 143
1 vote
0 answers
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, ...
user avatar
  • 143k
1 vote
0 answers
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?
user avatar
0 votes
0 answers
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.
user avatar
  • 99
0 votes
0 answers
23 views

About quasi-linear finite automata

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

About number of NFSTs

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.
user avatar
0 votes
0 answers
26 views

What is the optimal combination of transducers with limited capabilities to a more powerful transducer?

Assume we have a number of transducers with limited information processing capabilities. Are there theoretical results (proofs) on how these transducers can be combined by some sort of communication ...
user avatar
-3 votes
1 answer
139 views

State machine that multiplies a binary number with a constant

I'm trying to create a FSM that multiplies a bitstream with a constant value (e.g 3). I don't have a clue how to design such a FSM. Any hints?
user avatar
  • 101