Benutzer:Schreiber/Nivat

Sei $M=(Z,V,X,\delta ,z_{0},Z_{F})$ ein rationaler Transduktor. Das Alphabet Y sei $\delta$, und es sei $R:=\{(z_{1},v_{1},\alpha _{1},z_{1}')...(z_{m},v_{m},\alpha _{m},z_{m}')|m\geq 0\ wenn\ z_{0}\in Z_{F},\ sonst\ m\geq 1\wedge z_{i-1}'=z_{i}\wedge (z_{i},v_{i},\alpha _{i},z_{i}')\in Y=\delta \wedge z_{m}'\in Z_{F}\}$. R ist regulär. Definiere die Homomorphismen $f:Y^{*}\rightarrow V^{*}$ und $g:Y^{*}\rightarrow X^{*}$ durch $f((z,v,\alpha ,z')):=v$ und $g((z,v,\alpha ,z')):=\alpha$. Dann ist $\tau _{M}=\{(f(g),g(y))|y\in R\}$.

Umgekehrt: Sei $R\subseteq Y*$ regulär. Es gibt Typ-3-Grammatik $G=(N,Y,S,P),P\subseteq N\times NY^{*}\cup N\times Y^{*}$ mit $R=L(G)$. Sei $z_{f}$ neues Symbol ($\notin N$). Betrachte den a-Transduktor $M=(Z,V,X,\delta ,z_{0},Z_{F})$ mit $Z=N\cup \{z_{f}\},z_{0}:=S,Z_{F}:=\{z_{f}\}$ und $\delta :=\{(A,f(y),g(y),B)|A\rightarrow By\in P\}\cup \{(A,f(y),g(y),z_{f})|A\rightarrow y\in P\}$. Dann ist $\tau _{M}=\{(f(g),g(y))|y\in R\}$.