树变换器

在理论计算机科学和形式语言理论中，树变换器（TT）是一种抽象的机器，它将一棵树作为输入，并生成输出–通常是其他的树，但也有产生词或其他结构的模型。粗略地说，树换能器扩展了树自动机，与词换能器扩展词自动机的方式相同。操作树状结构而不是词，使得树形变换器能够对形式语言或自然语言的语法定向变换进行建模。然而，在算法复杂性、闭合特性等方面，树自动机并不像它们的词自动机那样表现良好。特别是，大多数的主要类别在组合下是不封闭的。树型转换器的主要类别是。

与树状自动机一样，如果δ的两个规则没有共享相同的左手边，并且最多只有一个初始状态，那么就说TOP是确定性的（缩写为DTOP）。在这种情况下，DTOP的语义是一个从输入树（关于Σ）到输出树（关于Γ）的部分函数，DTOP的每个状态的语义也是如此。换能器的域就是其语义的域。同样，换能器的图像也是其语义的图像。

DTOP在联合下是不封闭的：这对于确定性的词转换器来说已经是这样了。DTOP的域是一个规则的树状语言。考虑到DTOP规则的左手边与DTTA的左手边相同，该领域是可被DTTA识别的，这一点并不令人惊讶。

因此，识别DTOP领域的DTTA的构造必须考虑到状态的集合，并计算其领域的交集，因此有指数。