线性有界自动机

时间 : 18-10-30 栏目 : ag电子捕鱼 作者 : admin 评论 : 0 点击 : 160 次

  线性有界自动机是一种图灵机,是把计算限制在仅仅包含输入的那一段带上的图灵机。可用作上下文有关语言的识别接受器。

  线性有界自动机是一种图灵机,是把计算限制在仅仅包含输入的那一段带上的图灵机。可用作上下文有关语言的识别接受器。

  线性有界自动机(缩写为LBA)可形式地由来表示。其中:K 是状态的有限集;Γ 是带符号的有限集;是输人符号集;K 中的 q0是起始状态;是终结状态集;δ 是从到子集的映射,(L,R)分别是读写头左右移一格。Σ含有两个特殊的符号,通常记为 Ȼ 和 $ ,它们分别是左端标志和右端标志。这些符号开始就处在输入带的端点,其作用是阻止带头离开带上出现符号的区。

  非确定型线性有界自动机(以 NDLBA 表示)接受的语言类正好是上下文有关语言。

  确定型线性有界自动机(以DLBA 表示)的功能不会超过 NDLBA 的,以不等式表示为

  其中 L 表示该类自动机接受的语言集合。至今人们仍为能把包含关系精确为真包含关系或相等关系。这是一个著名的尚未解决的问题,简称 LBA 问题。1

  图灵机,又称图灵计算、图灵计算机,是由数学家阿兰·麦席森·图灵(1912~1954)提出的一种抽象计算模型,即将人们使用纸笔进行数学运算的过程进行抽象,由一个虚拟的机器替代人们进行数学运算。

  所谓的图灵机就是指一个抽象的机器,它有一条无限长的纸带,纸带分成了一个一个的小方格,每个方格有不同的颜色。有一个机器头在纸带上移来移去。机器头有一组内部状态,还有一些固定的程序。在每个时刻,机器头都要从当前纸带上读入一个方格信息,然后结合自己的内部状态查找程序表,根据程序输出信息到纸带方格上,并转换自己的内部状态,然后进行移动。

本文标签

除非注明,文章均为( admin )原创,转载请保留链接: http://www.treslola.com/?p=134

线性有界自动机:等您坐沙发呢!

发表评论


-----===== 博主信息 =====-----

为您推荐

0