Loading AI tools
来自维基百科,自由的百科全书
在自動機理論中,確定下推自動機(英語:Deterministic pushdown automaton,縮寫:DPDA)是可以使用了持有數據的棧的確定有限狀態自動機。術語「下推」來自原型機械自動機物理上接觸穿孔卡片來閱讀其內容的下推動作。術語「確定下推自動機」當前指稱識別確定上下文無關語言的抽象計算設備。
確定下推自動機是減弱版本的下推自動機。
一個下推自動機(PDA) M 可以定義為一個 7-元組:
這裏的
M 是確定的,如果它滿足下列兩個條件:
有兩種可能的接受標準: 「空棧」接受和「最終狀態」接受。對於確定下推自動機這兩種接受是不等價的(儘管對於非確定下推自動機是等價的)。被空棧接受的語言是被最終狀態接受的語言,同時滿足沒有在語言中的串是在語言中的其他串的前綴。
傑霍·賽尼澤格證明了確定 PDA 的等價問題(即給定兩個確定 PDA A 和 B,L(A)=L(B) 嗎?)是可決定的。對非確定 PDA 這個問題是不可決定的。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.