锥体(形式语言)

编辑
本词条由“匿名用户” 建档。
在形式语言理论中,锥体是一个形式语言的集合,它具有一些著名的语言集合所享有的一些理想的封闭性,特别是正规语言、无语境语言和可递归列举语言家族。圆锥的概念是一个更抽象的概念,它涵盖了所有这些家族。一个类似的概念是忠实圆锥,它有一些宽松的条件。例如,上下文敏感语言不构成一个锥体,但仍然具有形成忠实锥体的必要属性。 一个圆锥体是一个家族的语言,以便{displaystyle{mathcal{S}}至少包...

锥体(形式语言)

编辑

形式语言理论中,锥体是一个形式语言的集合,它具有一些著名的语言集合所享有的一些理想的封闭性,特别是正规语言、无语境语言和可递归列举语言家族。圆锥的概念是一个更抽象的概念,它涵盖了所有这些家族。一个类似的概念是忠实圆锥,它有一些宽松的条件。例如,上下文敏感语言不构成一个锥体,但仍然具有形成忠实锥体的必要属性。

锥体(形式语言)的定义

编辑

一个圆锥体是一个家族的语言,以便{displaystyle{mathcal{S}}至少包含一个非空的语言。}至少包含一个非空的语言,并且对于任何{displaystyleLin{mathcal{S}}包含至少一个非空语言,并且对于任何L∈S},语言是指在某一时刻,在某一时刻,在某一时刻,在某一时刻,在某一时刻。那么我们就会说到一个忠实的锥体;逆向同构则不受限制。在乔姆斯基的层次结构中,常规语言、无语境语言和可递归列举语言都是锥体,而语境敏感语言和递归语言只是忠实的锥体。

与换能器的关系

编辑

一个有限状态换能器是一个既有输入又有输出的有限状态自动机。它定义了一个转导{displaystyleL}上的语言映射为另一种语言。在输入的字母表上映射成另一种语言T(L){displaystyleT(L)}。在输出字母表上。每一个圆锥操作(同构、反同构、与常规语言相交)都可以用一个有限状态转换器来实现。而且,由于有限状态转换器在组合下是封闭的,每一个圆锥操作序列都可以由一个有限状态转换器来执行。反过来说,每一个有限状态换能器T都可以分解为锥体操作。都可以被分解成锥体操作。

锥体(形式语言)

事实上,这种分解存在一个正常的形式,也就是通常所说的尼瓦特定理:也就是说,每个这种总的来说,这意味着当且仅当一个语言家族在有限状态转换下是封闭的,它就是一个圆锥。这是一个非常强大的操作集。例如,我们很容易写出一个(非确定性的)有限状态转换器,其字母表为{displaystyle{a,b}}的有限状态转换器。移除每一秒的{displaystyleb}中的每一个b在偶数长度的词中。由于无语境语言形成一个圆锥体,它们在这个奇特的操作下是封闭的。

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

(3)
词条目录
  1. 锥体(形式语言)
  2. 锥体(形式语言)的定义
  3. 与换能器的关系

轻触这里

关闭目录

目录
尊敬的全球百科用户,全球百科新系统上线了!新增排名保障卡、词条年卡,更有增值功能——百度排名保障包年服务,详情访问“glopedia.cn/261472/”关注公众号可联系人工客服。