確定的上下文無關語言（deterministic context-free language）是2018年公布的計算機科學技術名詞。
基本介紹
- 中文名：確定的上下文無關語言
- 外文名：deterministic context-free language
- 所屬學科：計算機科學技術
- 公布時間：2018年
定義,出處,
定義
由確定的下推自動機接受的語言。
出處
《計算機科學技術名詞 》第三版。
確定的上下文無關語言（deterministic context-free language）是2018年公布的計算機科學技術名詞。
確定的上下文無關語言 確定的上下文無關語言（deterministic context-free language）是2018年公布的計算機科學技術名詞。定義 由確定的下推自動機接受的語言。出處 《計算機科學技術名詞 》第三版。
在形式文法理論中，確定上下文無關文法(DCFG)是上下文無關文法的真子集。簡介 確定上下文無關文法是確定下推自動機可識別的文法。確定上下文無關語言是確定上下文無關文法所定義的形式語言。意義 它們在計算機科學領域中特別重要，因為這些文法可以有效的識別，而非確定上下文無關文法需要回溯或其他複雜的技術；非確定...
上下文無關解析就是對無關上下文的分析。簡介 程式語言大部分是上下文無關語言，查詢語言通常也是上下文無關語言。英語也可以看成是上下文無關語言。這些語言中的字元串需要用編譯器、查詢引擎和各種其他應用程式分析與解釋。因此我們需要一個算法，給定上下文無關文法G，完成下列工作：1．檢查一個字元串，確定其是否L(...
形式語言與自動機理論是計算機科學理論的重要基礎。本書主要介紹喬姆斯基文法體系的四類文法以及它們與有限自動機、下推自動機、線性界限自動機和圖靈機之間的關係。此外，對語言的各種運算和封閉性質、判定問題及不可判定性以及確定的上下文無關語言與LR-文法也進行了討論。書中還介紹了一些文法和自動機在文本編輯、編譯...
第一章為預備知識；第二、三章討論有窮自動機和正規集合；第四、五、六章討論上下文無關語言和下推自動機；第七章討論圖靈機；第八章討論不可判定性；第九章按Chomsky譜系對語言和自動機加以總結，同時介紹了上下文有關語言和線性有界自動機；第十章討論上下文無關語言的一種特殊情形——確定的上下文無關語言；第...
6.3 上下文無關文法的範式 6.4 上下文無關文法的套用 6.4.1 用上下文無關文法描述語言 6.4.2 語法分析器生成工具YACC ……第7章 下推自動機 第8章 上下文無關語言的性質 第9章 圖靈機導引 第10章 不可判定性 第11章 線性有界自動機和上下文有關文法 第12章 確定的上下文無關語言和LR（k）...
在計算機科學中，特別是在形式語言理論領域，術語抽象語言族是指抽象的數學概念泛化的特徵，常見的有正則語言（正規語言），上下文無關語言和遞歸可枚舉語言以及其他形式語言，簡稱AFL，抽象語言族是用代數方法研究形式語言理論的重要成果。定義 某些代數運算下具有封閉性的形式語言類,簡稱AFL。抽象語言族是用代數方法研究...
第7章下推自動機和上下文無關語言 第三部分可計算性 第8章圖靈機 第9章圖靈可計算函式 第10章喬姆斯基層次 第11章判定問題與丘奇圖靈機 第12章不可判定性 第13章Mu—遞歸函式 第四部分計算複雜性 第14章時間複雜性 第15章庫克定理 第16章NP—完全問題 第17章其他複雜性類 第五部分確定型語法分析 第18章...
由1型文法產生的語言稱為1型語言或上下文有關語言。1型語言恰是非確定型線性有界自動機所識別的語言類。③2型文法。又稱為上下文無關文法。這種文法要求生成式a→β中的a必須是變元。由2型文法產生的語言稱為2型語言或上下文無關語言。2型語言恰是由下推自動機所識別的語言類。④3型文法。又稱為正則文法。...
0型文法產生的語言稱為0型語言。1型文法產生的語言稱為1型語言，也稱作上下文有關語言。2型文法產生的語言稱為2型語言，也稱作上下文無關語言。3型文法產生的語言稱為3型語言，也稱作正規語言。計算性質 上下文有關語言的可計算性等價於線性有界非確定圖靈機。它是磁帶只有kn個單元的非確定圖靈機，這裡的n是輸入...
《形式語言與自動機理論（第3版）》是2013年清華大學出版社出版的圖書，作者是蔣宗禮、姜守旭。內容簡介 本書是作者結合其近30年來在大學講授該門課程的經驗和體會，選擇和組織有關內容撰寫而成。基於計算機問題求解的需要討論正則語言、上下文無關語言的文法、識別模型及其性質、圖靈機的基本知識。其內容特點是抽象和...
一個形式語言是上下文無關的,如果它是由上下文無關文法生成的。 上下文無關文法重要的原因在於它們擁有足夠強的表達力來表示大多數程式設計語言的語法;實際上,幾乎所有程式設計語言都是通過上下文無關文法來定義的。另一方面,上下文無關文法又足夠簡單,使得我們可以構造有效的分析算法來檢驗一個給定字串是否是由某個...
7.3 上下文無關語言的接收 7.4 上下文無關語言的泵引理 7.5 上下文無關語言的封閉性 7.6 練習 參考文獻注釋 第三部分 可計算性 第8章 圖靈機 8.1 標準圖靈機 8.2 作為語言接收器的圖靈機 8.3 可供選擇接收標準 8.4 多道圖靈機 8.5 雙向圖靈機 8.6 多帶圖靈機 8.7 非確定型圖靈機 8...
形式語言與自動機理論因其以體現計算學科中模型描述、模型研究和模型計算為問題求解的主要特徵而成為計算機科學與技術、軟體工程、網路空間安全等計算機類學科教育的最重要的內容之一。本書按照我國當前計算機類及相關學科研究生教育實際需求，結合作者30餘年的教學實踐編著而成，以正則語言與上下文無關語言的文法、識別模型...
本書是關於形式語言、自動機理論和計算複雜性方面的經典之作，是國際上得到廣泛認可的計算機理論和計算機工程專業的優秀教材。書中涵蓋了有窮自動機、正則表達式與語言、正則語言的性質、上下文無關文法及上下文無關語言、下推自動機、上下文無關語言的性質、圖靈機、不可判定性以及難解問題等內容。本書注重定義、定理...
因此，非確定型的計算能力一般說應比確定型的強。然而是否真強，則取決於所討論的自動機的類型。從自動機接受語言（見形式語言理論）的能力來說，對於有限自動機，確定型機器和非確定型機器接受的語言類完全一樣，都是正規集合。對於下推自動機，確定型機器接受的語言類（確定的上下文無關語言）是非確定型機器接受...
帕里克定理表明，有些上下文無關語言可能只有歧義語法Template:Explain。這樣的語言稱為固有歧義語言。從形式文法的角度看，這意味著某些有歧義的上下文無關文法無法轉換為明確的上下文無關文法。上下文無關文法 在計算機科學中，形式語言是：某個字母表上，一些有限長字串的集合，而形式文法是描述這個集合的一種方法。形式...
可以證明，線性語言，即由線性語法生成的語言，形成了上下文無關語言的一個子集。很顯然，每個正則語言都是線性的。線性語言類與確定性上下文無關語言不同。這些結果總結起來叫作喬姆斯基層次結構(Chomsky’s Hierarchy)。它規定：每一個正則語言都是線性的。每一個正則語言都是確定性上下文無關的。每一個線性語言都是...
可以證明，線性語言，即由線性語法生成的語言，形成了上下文無關語言的一個子集。很顯然，每個正則語言都是線性的。線性語言類與確定性上下文無關語言不同。這些結果總結起來叫作喬姆斯基層次結構(Chomsky’s Hierarchy)。它規定：每一個正則語言都是線性的。每一個正則語言都是確定性上下文無關的。每一個線性語言都是...
正規語言通常用來定義檢索模式或者程式設計語言中的詞法結構。正規語言類包含於上下文無關語言類，上下文無關語言類包含於上下文相關語言類，上下文相關語言類包含於遞歸可枚舉語言類。這裡的包含都是集合的真包含關係，也就是說：存在遞歸可枚舉語言不屬於上下文相關語言類，存在上下文相關語言不屬於上下文無關語言類，存在...
下推自動機是一個非確定的裝置，對於有限自動機，確定型和非確定型有限自動機在接受語言上是等價的。這一結論對於下推自動機是不成立的。非確定型下推自動機接受的語言集合是上下文無關語言；確定型下推自動機接受的語言集合是非確定型下推自動機接受的語言集合的真子集，稱為確定型上下文無關語言。圖靈機 圖靈機...
17字母表與語言(25)18語言的有窮表示(29)參考文獻(33)第2章有窮自動機(34)21確定型有窮自動機(34)22非確定型有窮自動機(39)23有窮自動機與正則表達式(47)24正則語言與非正則語言(54)25狀態最小化(58)26關於有窮自動機的算法(65)參考文獻(70)第3章上下文無關語言(72)31...
第6章上下文無關語言的結構 6.1引言 6.2疊加自動機 本節習題 6.3上下文無關語法與疊加自動機 本節習題 6.4泵作用引理 本節習題 6.5上下文無關語言的閉包性質 本節習題 6.6確定型疊加自動機 本節習題 6.7本章總結與附加思考題 附加思考題 第7章可計算枚舉語言 7.1引言 7.2非限制性語法 本節習題 7...
這種文法規定的語言可以被線性有界非確定圖靈機接受。2-型文法生成上下文無關語言。這種文法的產生式規則取如A-> γ 一樣的形式。這裡的A是非終結符號，γ 是包含非終結符號與終結符號的字串。這種文法規定的語言可以被非確定下推自動機接受。上下文無關語言為大多數程式設計語言的語法提供了理論基礎。3-型文法（...
兩個最重要例子是正則語言的泵引理和上下文無關語言的泵引理。鄂登引理是另一種更強的上下文無關語言的泵引理。這些引理可以用來確定特定語言不在給定語言類中。但是它們不能被用來確定一個語言在給定類中，因為滿足引理是類成員關係的必要條件，但不是充分條件。泵引理是1961年由Y. Bar-Hillel、M. Perles和E. ...
兩個最重要例子是正則語言的泵引理和上下文無關語言的泵引理。鄂登引理是另一種更強的上下文無關語言的泵引理。這些引理可以用來確定特定語言不在給定語言類中。但是它們不能被用來確定一個語言在給定類中，因為滿足引理是類成員關係的必要條件，但不是充分條件。泵引理是1961年由Y. Bar-Hillel、M. Perles和E. ...