什么是队列自动机？

队列自动机类似于下推自动机 (PDA)，只是堆栈被队列替换。

  • 队列是一条磁带，只能在左侧写入符号，只能在右侧读取符号。

  • 每个写操作（我们称之为推入）都会在队列的左侧添加一个符号，每个读操作（我们称之为拉出）都会读取并删除右侧的符号。

  • 与 PDA 一样，输入放在单独的只读输入带上，输入带上的磁头只能从左到右移动。

  • 输入带包含一个带有空白符号的单元格，该单元格位于输入之后，以便可以检测输入的结尾。

  • 队列自动机通过在任何时间进入一个特殊的接受状态来接受其输入。

形式化定义

确定性队列自动机 (DQA) 定义为七元组

(Q, Σ, Γ, δ, q0 , ⊥, F)

其中，

  • Q 是一组状态，

  • Σ 是输入字母表，

  • Γ 是一个有限的队列符号集，

  • q0 是起始状态，

  • ⊥ 是一个空队列符号 ⊥6= Γ，

  • 转移函数 δ 定义为 Q × Σ ∪ {λ} × (Γ × Γ) ∪ ({⊥} × {⊥}) → Q × Γ ∪ {λ} × {keep, remove}，其中 λ 表示空符号。它绝不能用作输入符号。

  • F 是一组接受状态 (F ⊆ Q)。

示例

为语言 {anbn | n >= 0} 构造队列自动机。

对于给定的语言，自动机中存在的状态数为 4，

Q={q0,q1,q2,q3}，

输入字母表 ={a,b}

队列自动机如下所示 -

更新于: 2021年6月15日

470 次浏览

开启你的 职业生涯

通过完成课程获得认证

开始学习
广告