下推自动机

本文概述

• PDA组件
• PDA的正式定义
• 即时描述（ID）
• 旋转记号法

• 下推自动机是一种实现CFG的方式，与我们为常规语法设计DFA的方式相同。 DFA可以记住有限数量的信息，而PDA可以记住无限数量的信息。
• 下推式自动机只是添加了“外部堆栈存储器”的NFA。堆栈的添加用于向Pushdown自动机提供后进先出的内存管理功能。下推式自动机可以在堆栈上存储无限量的信息。它可以访问堆栈上的有限信息。 PDA可以将元素推到堆栈的顶部，然后从堆栈顶部弹出一个元素。要将元素读入堆栈，必须弹出顶部的元素并将其丢失。
• PDA比FA更强大。 FA可以接受的任何语言也可以被PDA接受。 PDA还接受FA甚至无法接受的一类语言。因此，PDA比FA更为优越。

PDA组件

输入磁带：输入磁带分为许多单元格或符号。输入头是只读的，一次只能从左向右移动一个符号。

有限控件：有限控件具有一些指针，该指针指向要读取的当前符号。

堆栈：堆栈是一种结构，在该结构中，我们只能从一端推入和取出物品。它具有无限大小。在PDA中，堆栈用于临时存储项目。

PDA的正式定义

PDA可以定义为7个组件的集合：

问：有限状态集

∑：输入集

Γ：可以从堆栈中弹出的堆栈符号

q0：初始状态

Z：在Γ中的开始符号。

F：一组最终状态

δ：用于从当前状态移动到下一状态的映射函数。

即时描述（ID）

ID是PDA如何计算输入字符串并决定接受还是拒绝字符串的非正式表示法。

瞬时描述是一个三元组（q，w，α），其中：

q描述当前状态。

w描述剩余的输入。

α描述堆栈的内容，在左上方。

旋转记号法

⊢符号描述旋转门符号，代表一动。

sign *符号描述一系列移动。

例如，

（p，b，T）⊢（q，w，α）

在上面的示例中，在从状态p过渡到q的同时，输入符号’b’被消耗了，堆栈’T’的顶部由新的字符串α表示。

范例1：

设计用于接受语言的PDA {anb2n | n> = 1}。

解决方案：在这种语言中，n个n后面应该是2n个b。因此，我们将应用一个非常简单的逻辑，即如果读取单个“ a”，则将两个a压入堆栈。一旦我们读了“ b”，那么对于每个单个“ b”，只有一个“ a”应该从堆栈中弹出。

ID可以构造如下：

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)

现在，当我们读取b时，将状态从q0更改为q1并开始弹出相应的’a’。因此，

δ(q0, b, a) = (q1, ε)

因此，除非读取所有符号，否则将重复执行弹出“ b”的过程。请注意，弹出动作仅在状态q1中发生。

δ(q1, b, a) = (q1, ε)

读取所有b后，所有对应的a都应弹出。因此，当我们将ε读作输入符号时，堆栈中应该没有任何内容。因此，此举将是：

δ(q1, ε, Z) = (q2, ε)

哪里

PDA =（{q0，q1，q2}，{a，b}，{a，Z}，δ，q0，Z，{q2}）

我们可以将ID概括为：

δ(q0, a, Z) = (q0, aaZ)
δ(q0, a, a) = (q0, aaa)
δ(q0, b, a) = (q1, ε)
δ(q1, b, a) = (q1, ε)
δ(q1, ε, Z) = (q2, ε)

现在，我们将为输入字符串“ aaabbbbbb”模拟此PDA。

δ(q0, aaabbbbbb, Z) ⊢ δ(q0, aabbbbbb, aaZ)
                    ⊢ δ(q0, abbbbbb, aaaaZ)
                    ⊢ δ(q0, bbbbbb, aaaaaaZ)
                    ⊢ δ(q1, bbbbb, aaaaaZ)
                    ⊢ δ(q1, bbbb, aaaaZ)
                    ⊢ δ(q1, bbb, aaaZ)
                    ⊢ δ(q1, bb, aaZ)
                    ⊢ δ(q1, b, aZ)
                    ⊢ δ(q1, ε, Z)
                    ⊢ δ(q2, ε)      
                      ACCEPT

范例2：

设计用于接受语言{0n1m0n | m，n> = 1}。

解决方案：在此PDA中，n个数字为0，后跟任意数量的1，后跟n个数字为0。因此，这种PDA的设计逻辑如下：

遇到第一个0时将所有0压入堆栈。然后，如果我们读1，则什么也不做。然后读取0，每次读取0时，从堆栈中弹出一个0。

例如：

这种情况可以以ID形式编写为：

δ(q0, 0, Z) = δ(q0, 0Z)
δ(q0, 0, 0) = δ(q0, 00)
δ(q0, 1, 0) = δ(q1, 0)
δ(q0, 1, 0) = δ(q1, 0)
δ(q1, 0, 0) = δ(q1, ε)
δ(q0, ε, Z) = δ(q2, Z)      (ACCEPT state)

现在，我们将为输入字符串“ 0011100”模拟此PDA。

δ(q0, 0011100, Z) ⊢ δ(q0, 011100, 0Z)
                  ⊢ δ(q0, 11100, 00Z)
                  ⊢ δ(q0, 1100, 00Z)
                  ⊢ δ(q1, 100, 00Z)
                  ⊢ δ(q1, 00, 00Z)
                  ⊢ δ(q1, 0, 0Z)
                  ⊢ δ(q1, ε, Z)
                  ⊢ δ(q2, Z)
                    ACCEPT