資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究什麼是理論計算機科學（TOC）中的下推自動機？
一個下推自動機 (PDA) 是一種以類似於為正則語法設計確定性有限自動機 (DFA) 的方式實現上下文無關文法 (CFG) 的方法。
DFA 可以記住有限量的資訊，但 PDA 可以記住無限量的資訊。
基本上，PDA 如下所示：
"有限狀態機 + 堆疊"
PDA 有三個組成部分，如下所示：
- 輸入帶。
- 控制單元。
- 大小無限的堆疊。
PDA 可能會也可能不會讀取輸入符號，但它必須在每次事務中讀取堆疊的頂部。
PDA 可以正式描述為 7 元組
(Q, ∑,S, δ,q0,I,F)
- Q 是有限數量的狀態。
- ∑ 是輸入字母表。
- S 是堆疊符號。
- δ 是轉換函式：QX(∑U{e})XSXQ
- q0 是初始狀態 (q0 屬於 Q)。
- I 是初始狀態頂部符號。
- F 是一個接受狀態集 (F 屬於 Q)。
該圖顯示了 PDA 從狀態 q1 到狀態 q2 的轉換，標記為 a,b->c
在狀態 q1，如果遇到輸入字串 'a' 並且堆疊的頂部符號為 'b'，那麼我們將彈出 'b'，將 'c' 推入堆疊頂部，並移動到狀態 q2。
更新於： 2023-10-07
30K+ 次瀏覽
廣告