Questions tagged [transducers]
The transducers tag has no usage guidance.
16
questions
10
votes
3answers
768 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 ...
6
votes
1answer
95 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 ...
4
votes
1answer
441 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 ...
3
votes
1answer
557 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 ...
3
votes
0answers
51 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 ...
2
votes
0answers
83 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
2answers
146 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 ...
1
vote
0answers
154 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
0answers
25 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?
0
votes
1answer
66 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 ...
0
votes
1answer
50 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
233 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) ...
0
votes
1answer
330 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 ...
-1
votes
1answer
138 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
votes
1answer
177 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 ...
-3
votes
1answer
88 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?
