Questions tagged [transducers]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
17 views

Why are sensors transducers when analogue-to-digital-converters (ADC) do the actual conversion?

As sensors only sense continuous quantities whereas an ADC is a device which actually converts one form of input to another.
2
votes
0answers
28 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) := ...
0
votes
0answers
21 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?
0
votes
0answers
17 views

Mealy machine and moore machine

Can we compute the number of machine of two kind of transducers (mealy and moore) with $n$ states, and lenght of input symbols $m$, and lenght of output symbols $p$.
0
votes
0answers
18 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.
0
votes
0answers
23 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 ...
1
vote
0answers
19 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
1answer
51 views

Is it possible to constract Moore or Mealy machine with a different size of input and output?

Is it possible to constract Moore or Mealy machine to take input tape: 0011 and output: 00001111 (or vice versa). In other words, input and output have different size. I want to construct FSMs to ...
3
votes
1answer
759 views

Are finite state transducers and Mealy machines the same machines?

There are several versions of the definitions of the FST and the Mealy machine. Some of the definitions are almost same. Some have a little differences. But it seems that they both are a kind of DFA ...
4
votes
1answer
70 views

Is the power of a natural number logspace-computable?

Given a constant $n\in\mathbb{N}_+$, is the simple power function $$ λ\,x\in\mathbb{N}_+.\,x^n $$ logspace computable by a logspace transducer (which has a read-only input tape, a working read-write ...
0
votes
0answers
35 views

Are polynomials in one variable logspace-computable?

Given a polynomial function $$p\quad=\quad \lambda\, x\in\mathbb{N}_0.\ \sum_{i=0}^n a_i x^i$$ with $a_i\in\mathbb{Z}$ for all $i\leqslant n$, can you compute $p$ by a logspace transducer if the input ...
2
votes
0answers
94 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 ...
0
votes
1answer
69 views

Show that the regular language is contained in another

Let L1 and L2 be two non empty regular language. How can I show that the following expression is correct with an example ? $\bigotimes$ denote the transducer cross product. $L_1^+ \bigotimes L_2^+$ ...
0
votes
1answer
295 views

Is the output of a Mealy/Moore automaton a regular language?

How can I prove that the output sequence of Mealy Moore Machine is a Regular Language ? And what if transition outputs more than one character ? How can we prove for this case that the language in (1) ...
1
vote
0answers
202 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
votes
1answer
168 views

Can a finite state transducer emit $\epsilon$?

Can a deterministic finite state transducer output ϵ (epsilon) ? A Deterministic Finite-state Transducer (DFT) is a device much like a DFA, except that its purpose is not to accept strings or ...
1
vote
0answers
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?
3
votes
0answers
52 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 ...
6
votes
1answer
99 views

Can Tree Transducers Self-Interpret?

Is it possible for MSO graph/tree transducers to reflect themselves, namely to create an interpreter of tree/graph transducers using tree/graph transducers? If yes, I'll be happy for some design ...
1
vote
2answers
183 views

What is the expressive power of finite-state transducers and pushdown transducers?

One would assume that a finite state transducer can perform any translation such that the resulting string is from a regular grammar. Similarly, that a pushdown transducer can generate strings from ...
-3
votes
1answer
98 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?
4
votes
1answer
582 views

NL and NP compute different binary relations, so what?

Let the binary relation computed by a nondeterministic transducer be the relation between input strings and the possible output strings the transducer can produce (and accept) for the given input ...
0
votes
1answer
75 views

Why not just use FSTs for combining syntactic and semantic analysis?

I've just found the finite state transducer. Since the FST processes two tapes: one for input, one for output, shouldn't it be possible to use FST to "pack together" some compiler stages, such as ...
-1
votes
1answer
190 views

How would a finite state transducer with no output function work?

Say I have a finite state transducer, 6 tuple FST with a set of states, input symbols, output symbols, transition function, a start state, and an output function. If I combine the output function into ...
0
votes
1answer
355 views

Closure properties of finite state transducers

Given $T_1, T_2\colon \Sigma^* \to \Gamma^*$ ($\Gamma$ is output alphabet), let $\Delta(T_1, T_2)$ consist of all input strings $w \in Σ^*$ where $T_1(w) \neq T_2(w)$. Prove that FSTs ...
11
votes
3answers
1k views

Algorithms for minimizing Moore automata

Brzozowski's algorithm can be extended to Moore automata but its time complexity is exponential in general. Is there any other algorithm for minimization of Moore automata? What are the running times ...