定理 1. 任意NSST
\(T = (Q_T, \Sigma, \Sigma', \Gamma, E, q_{0, T}, F_T)\) 和 NFA
\(M = (Q_M, \Sigma', \delta_M, q_{0, M},
F_M)\)，存在NFA \(N = (Q_N, \Sigma, \delta_N, q_{0,
N}, F_N)\)，使得若\(w \in L
(N)\)，则存在\(w' \in T
(w)\)使得\(w' \in L
(M)\)，且\(N\)是可计算的。
证明.
下面构造一个N：
首先，\(Q_N = Q_T \times P (Q_M)^{Q_M \times
\Gamma}\)，\(P
(Q_M)\)表示M的状态的幂集。为了方便，之后N的状态写作\((q,
\rho)\)，其中q是模拟的T的状态，函数\(\rho
\in Q_M \times \Gamma \rightarrow P
(Q_M)\)。直观上说，\(\rho (q,
x)\)记录了当状态为q时输入变量x代表的串，M会转移到的状态集。
N的初始状态是\((q_{0, T},
\rho_{\varepsilon})\)，其中对任意状态q和变量x，\(\rho_{\varepsilon}
(q, x) = \{ q \}\)。
作用于函数\(\rho\)，变量x和字符串\(w
\in (\Gamma \cup
\Sigma')^{\ast}\)，更新算子U会返回一个新的函数\(\rho'\)，其定义为：
\(\displaystyle U (\rho, x, w' a) (q, x) = \left\{ \begin{array}{cc}
\delta_M^{\ast} (U (\rho, x, w') (q, x), a) & a \in \Sigma'\\
\bigcup_{q' \in U (\rho, x, w') (q, x)} \rho (q', a) & a \in
\Gamma
\end{array} \right.\)
\(\displaystyle U (\rho, x, \varepsilon) (q, x) = \{ q \}\)
\(\displaystyle U (\rho, x, w) (q, y) = \rho (q, y), x \neq y\)
对于NSST的并发赋值\(A \in
\Gamma \rightarrow (\Gamma \cup
\Sigma')^{\ast}\)，扩展U为\(U^{\ast}\):
\(\displaystyle U^{\ast} (\rho, A) (q, x) = U (\rho, x, A (x)) (q,
x)\)
对N的任意状态\((q,
\rho)\)，如果\((q', A) \in E (q,
a)\)，则对N有：
\(\displaystyle ((q, \rho), a, (q', U^{\ast} (\rho, A))) \in
\delta_N\)
对字符串\(w \in (\Gamma \cup
\Sigma')^{\ast}\)和函数\(\rho\)，定义集合\(R_{w,
\rho}\)为：
\(\displaystyle R_{w, \rho} = \left\{ \begin{array}{cc}
\{ q_{0, M}
\} & w = \varepsilon\\
\delta_M^{\ast} (R_{w', \rho}, a) & w = w' a
\wedge a \in \Sigma'\\
\bigcup_{q \in R_{w', \rho}} \rho (q, a) & w
= w' a \wedge a \in \Gamma
\end{array} \right.\)
最后，NFA
N的终止状态集\(F_N\)为满足下列条件的状态\((q,
\rho)\)的集合：
-
\(F_T (q)\)有定义。
-
令\(w = F_T (q)\)，则\(R_{w, \rho} \cap F_M \neq
\emptyset\)
注记 2.
其实上面的构造直观地说起来还是比较简单：NFA
N在模拟NSST
T的状态转移的同时，也同时模拟T中变量的改变。只不过不是直接模拟变量的值（这本来也是做不到的），而是模拟将T的当前格局下的变量输入NFA
M后会产生的效果（也就是转移到的状态）。由于T的每一步转移会产生一组并发的赋值，我们只需要模拟赋值对状态的改变即可。
注记 3.
值得注意的是，上面的构造方法实际上根本没用上copyless的性质。换言之，如果考虑不限制copyless的NSST，上述构造方法依旧成立。这种新的Transducer表达力比2FT更强。