
- 自动机理论教程
- 自动机理论 - 首页
- 自动机理论 - 开始
- 自动机理论 - 历史
- 自动机理论 - 应用
- 自动机理论术语
- 自动机中字符串的基础
- 自动机的集合论
- 语言和文法
- 计算理论中的文法
- 由文法生成的语言
- 乔姆斯基文法分类
- 有限自动机
- 确定性有限自动机 (DFA)
- 非确定性有限自动机 (NFA)
- 从 NFA 到 DFA 的转换
- DFA 的最小化
- 穆尔机与米利机
- DFA 的补集
- 正则表达式
- 自动机中的正则表达式
- 自动机中的 Arden 定理
- 将正则表达式转换为有限自动机
- 正则文法的泵引理
- 计算理论中的正则集
- 上下文无关文法
- 上下文无关文法 (CFG)
- 上下文无关文法中的二义性
- 上下文无关语言的封闭性
- 简化上下文无关文法
- 乔姆斯基范式 (CNF)
- 格雷巴赫范式 (GNF)
- 上下文无关文法的泵引理
- 下推自动机
- 下推自动机 (PDA)
- 下推自动机的接受
- 从 CFG 构造 PDA
- 下推自动机与解析
- 图灵机
- 图灵机 (TM) 基础
- 图灵机接受的语言
- 多带图灵机
- 多轨迹图灵机
- 非确定性图灵机
- 半无限带图灵机
- 线性有界自动机 (LBA)
- 可计算性和不可判定性
- 图灵语言的可判定性
- 不可判定语言
- 图灵机停机问题
- 计算理论中的 Rice 定理
- Post 对应问题 (PCP)
- 自动机理论资源
- 自动机理论 - 快速指南
- 自动机理论 - 资源
- 自动机理论 - 讨论
半无限带图灵机
带半无限带的图灵机有一端,但没有另一端。该端用结束标记限制。

它是一个双轨带:
上轨 - 它表示初始磁头位置右边的单元格。
下轨 - 它表示初始磁头位置左边的单元格,顺序相反。
无限长的输入字符串最初写在磁带上的连续磁带单元格中。
机器从初始状态q0开始,磁头从左端的“End”标记开始扫描。在每一步中,它读取磁头下磁带上的符号。它在该磁带单元格上写入一个新符号,然后它将磁头向左或向右移动一个磁带单元格。转移函数确定要采取的操作。
它有两个特殊状态,称为接受状态和拒绝状态。如果在任何时候它进入接受状态,则接受输入;如果它进入拒绝状态,则图灵机拒绝输入。在某些情况下,对于某些特定的输入符号,它会无限期地运行而不会被接受或拒绝。
注意 - 带半无限带的图灵机等效于标准图灵机。
广告