確定性下推自動機（deterministic pushdown automaton）是2018年公布的計算機科學技術名詞。
基本介紹
- 中文名：確定性下推自動機
- 外文名：deterministic pushdown automaton
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
定義
下推自動機中的一種，這種下推自動機的動作函式是單值函式，它接受的語言類嚴格小於非確定性下推自動機接受的語言類。
出處
《計算機科學技術名詞 》第三版。
確定性下推自動機
相關詞條
- 確定性下推自動機
確定性下推自動機 確定性下推自動機（deterministic pushdown automaton）是2018年公布的計算機科學技術名詞。定義 下推自動機中的一種，這種下推自動機的動作函式是單值函式，它接受的語言類嚴格小於非確定性下推自動機接受的語言類。出處 《計算機科學技術名詞 》第三版。
- 下推自動機
下推自動機 M 是如下的一個七元組 ( Q, Σ, Γ, δ, q0, Z0, F ) ，其中：* Q 是一個有窮狀態集合；* Σ 是一個字母表，稱為輸入字母表。* Γ 是一個字母表，稱為棧字母表。* q0 屬於 Q ，是初始狀態。* Z0 屬於 Γ ，是一個特殊的棧符號，稱為棧起始符號。* F 包含於 Q ，是終結...
- 形式語言與自動機理論
《形式語言與自動機理論》是2007年由機械工業出版的書籍，作者是吳哲輝。內容簡介 形式語言與自動機理論是計算機科學理論的重要基礎。本書主要介紹喬姆斯基文法體系的四類文法以及它們與有限自動機、下推自動機、線性界限自動機和圖靈機之間的關係。此外，對語言的各種運算和封閉性質、判定問題及不可判定性以及確定的上下文...
- 非確定性
對於同一類型的自動機，確定型可以看作是非確定型的特殊情形。因此，非確定型的計算能力一般說應比確定型的強。然而是否真強，則取決於所討論的自動機的類型。從自動機接受語言（見形式語言理論）的能力來說，對於有限自動機，確定型機器和非確定型機器接受的語言類完全一樣，都是正規集合。對於下推自動機，確定型...
- 計算的本質:深入剖析程式和計算機
3.1.3 確定性 61 3.1.4 模擬 62 3.2 非確定性有限自動機 65 3.2.1 非確定性 65 3.2.2 自由移動（free move） 71 3.3 正則表達式 74 3.3.1 語法 75 3.3.2 語義 78 3.3.3 解析 86 3.4 等價性 88 第4章 增加計算能力 97 4.1 確定性下推自動機 100 4.1.1 存儲 100 4.1.2 ...
- 計算理論導引(原書第3版)
214歧義性 215喬姆斯基範式 22下推自動機 221下推自動機的形式化定義 222下推自動機舉例 223與上下文無關文法的等價性 23非上下文無關語言 24確定型上下文無關語言 241DCFL的性質 242確定型上下文無關文法 243DPDA和DCFG的關係 244語法分析和LR(...
- 計算理論基礎(第2版)
26關於有窮自動機的算法(65)參考文獻(70)第3章上下文無關語言(72)31上下文無關文法(72)32語法分析樹(79)33下推自動機(83)34下推自動機與上下文無關文法(87)35上下文無關語言與非上下文無關語言(92)36關於上下文無關文法的算法(97)37確定性與語法分析(102)參考文獻(115)第4章Turing...
- 喬姆斯基層次結構
不具有無歧義文法的語言稱為本質歧義性語言。例如，{S A，S a，A a}是歧義的文法。。接受CFL的自動機稱為下推自動機。確定型和不確定型下推自動機接受的語言分別稱為確定型CFL和不確定型CFL，前者是後者的真子集。正則文法 正則文法來源於20世紀50年代中期喬姆斯基對自然語言的研究，是喬姆斯基短語結構文法分層...
