資料結構
網路
關係資料庫管理系統 (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+ 次瀏覽
廣告