**Rational Transductions**

A rational transducer \(M\) is a 6-tuple \((S, \Sigma, \Delta, \tau, s_0, F)\), where \(S\) is a finite set of states, \(\Sigma\) and \(\Delta\) are input and output alphabets respectively, the transition relation \(\tau\) is a finite relation between \(S \times \Sigma^*\) and \(S \times \Delta^*\), \(s_0 \in S\) is the initial state and \(F\subseteq S\) is the set of final states.

For alphabets \(\Sigma, \Delta\), a *transduction* is a subset of \(\Sigma^*\times\Delta^*\). If \(A\) is a transducer as above, then \(\top (A)\) denotes its generated *transduction*, namely the set of all pairs \((u, v)\in X^*\times Y^*\) such that \((s_0, u, f, v)\in \tau\) for some \(f \in F\).

For a transduction \(T\subseteq X^*\times Y^*\) and a language \(L\subseteq X^*\), we write \[TL=\{v\in Y^*|\exists u\in L:(u,v)\in T\}\].

Prove/disprove the following statements:

- Composition of two rational transductions is a rational transduction.
- Inverse of a rational transduction is a rational transduction.
- For a regular language \(R\subseteq X^*\) and a rational transduction \(T\subseteq X^*\times Y^*\), \(TR\) is regular.

This problem is a part of Tessellate S.T.E.M.S (2019)

No vote yet

1 vote

×

Problem Loading...

Note Loading...

Set Loading...

Easy Math Editor

`*italics*`

or`_italics_`

italics`**bold**`

or`__bold__`

boldNote: you must add a full line of space before and after lists for them to show up correctlyparagraph 1

paragraph 2

`[example link](https://brilliant.org)`

`> This is a quote`

Remember to wrap math in \( ... \) or \[ ... \] to ensure proper formatting.`2 \times 3`

`2^{34}`

`a_{i-1}`

`\frac{2}{3}`

`\sqrt{2}`

`\sum_{i=1}^3`

`\sin \theta`

`\boxed{123}`

## Comments

There are no comments in this discussion.