数据结构
网络
关系数据库管理系统 (RDBMS)
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C语言编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装学
法学什么是下推自动机 (PDA) 的瞬时描述？
瞬时描述被称为非正式表示法，它解释了下推自动机 (PDA) 如何计算给定的输入字符串并做出关于该字符串是否被接受的决定。
PDA 包括状态和堆栈的内容。
堆栈通常是 PDA 在任何时候的重要组成部分之一。
因此，我们采用一种方便的表示法来描述 PDA 用于字符串处理的连续配置。
PDA 表示法的因素由三元组 (q, w, γ) 表示：
- q 是当前状态。
- w 是剩余的输入字母表。
- γ 是 PDA 堆栈的当前内容。
通常，最左边的符号表示堆栈 γ 的顶部，最右边的符号表示底部。这种三元组表示法称为下推自动机的瞬时描述或 ID。
从一个瞬时描述移动到另一个瞬时描述用符号“⊢”表示。
因此，
(q0, aw, z0) ⊢ (q1, w, yz0)
当且仅当
δ(q0, a, z0) ϵ (q1, yz0).
示例
考虑以下示例：
显示 PDA 输入字符串 w = “aabb” 的 ID 或移动，其中：
M = ({q0, q1, q2}, {a, b}, {a, b, Z0}, δ, q0, Z0, {q2}),
其中 δ 定义如下：
δ(q0, a, Z0) = {(q0, aZ0)} Rule (1)
δ(q0, a, a) = {(q0, aa)} Rule (2)
δ(q0, b, a) = {(q1, λ)} Rule (3)
δ(q1, b, a) = {(q1, λ)} Rule (4)
δ(q1, λ, Z0) = {(q2, λ)} Rule (5)
δ(q0, λ, Z0) = {(q2, λ)} Rule (6)我们需要找出字符串 w 是否被 PDA 接受。
解答
字符串 w = “aabb” 的瞬时描述如下所示：
(q0, aabb, Z0) |- (q0, abb, aZ0) based on Rule (1) |- (q0, bb, aaZ0) based on Rule (2) |- (q1, b, aZ0 based on Rule (3) |- (q1, λ, Z0) based on Rule (3) |- (q2, λ, λ) based on Rule (5)
因此，PDA 达到 (q2, λ, λ) 的配置，即 PDA 堆栈为空，并且它已达到最终状态。因此，字符串 'w' 被接受。
更新于：2021年6月12日
12K+ 次浏览
广告