树变换器

编辑
本词条由“匿名用户” 建档。

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

树变换器

编辑

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

作为术语重写的语义

编辑

换能器

编辑

T的每个状态以及T本身的语义是输入树(关于Σ)和输出树(关于Γ)之间的二元关系。

确定性和域

编辑

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

树变换器

DTOP的属性

编辑

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

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

内容由匿名用户提供,本内容不代表vibaike.com立场,内容投诉举报请联系vibaike.com客服。如若转载,请注明出处:https://vibaike.com/163357/

(2)
词条目录
  1. 树变换器
  2. 作为术语重写的语义
  3. 换能器
  4. 确定性和域
  5. DTOP的属性

轻触这里

关闭目录

目录