下推自动机下推自动机|自动机教程

本文概述

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