你的進度
0/ 27 節已標記完成
下一節: 可區分性與最小確定型自動機
完成記錄儲存在此瀏覽器中。
這門課在網上
CSCI3130 筆記裏的內容
數字只算這門課 27 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。
在網上定理卡 77 · 定義 61 · 反例 34 · 概念視角 13 · 證明透視 33
第 1 章 · 5 節
正則語言
正則語言
- 1.1
可區分性與最小確定型自動機
由剩餘語言構造最小 DFA,並透過劃分細化來計算它。
- 1.2
有限自動機、正則表達式與泵引理
定義 DFA、NFA 與正則表達式,證明子集構造、Thompson 構造與狀態消去構造,並證明泵引理與基於可區分性的狀態數下界。
- 1.3
確定有限自動機的判定問題
利用有限圖搜尋判定空性、等價性與無窮性。
- 1.4
正則語言的泵引理
利用有限狀態的重複與正確的量詞次序證明語言非正則。
- 1.5
同態與正則語言
為同態的正像與逆像構造有限自動機。
第 2 章 · 9 節
上下文無關語言
上下文無關語言
- 2.1
下推自動機:終結狀態接受與空堆疊接受
在保持語言不變的前提下,在兩種非確定性下推自動機的接受約定之間互相轉換。
- 2.2
範式與堆疊計算中隱藏的文法
證明上下文無關範式定理,補全泵引理的二叉樹前提,並從任意非確定下推自動機構造文法。
- 2.3
以動態規劃判定上下文無關文法的成員關係
為喬姆斯基(Chomsky)範式文法推導 CYK 表。
- 2.4
上下文無關文法、堆疊自動機與泵引理
推導、語法分析樹與歧義;括號平衡與 aⁿbⁿ 的文法;用非確定型下推自動機模擬文法;上下文無關語言的泵引理及其局限。
- 2.5
簡化上下文無關文法
在保持語言不變的前提下消除空產生式與單位產生式。
- 2.6
將文法轉換為喬姆斯基範式
在保持上下文無關語言不變的前提下,分離終結符並將產生式二元化。
- 2.7
上下文無關語言的泵引理
從語法分析樹推導上下文無關泵引理,並正確運用其量詞。
- 2.8
上下文無關語言與正則約束
將下推自動機與有限自動機結合,並考察封閉性的局限。
- 2.9
確定性下推自動機與接受方式
追蹤一部確定性堆疊機,並證明空堆疊接受方式所帶來的前綴限制。
第 3 章 · 2 節
語法分析
語法分析
- 3.1
LR(0) 項目、移進-歸約分析與前瞻
增廣文法、LR(0) 項目、閉包與 goto、規範族、ACTION/GOTO 表與衝突,一張完整的分析表與一次完整分析,以及通過 S → a | ab 區分 LR(0) 與 LR(1)。
- 3.2
預測分析與 LL(1) 分析表
利用可空性、FIRST 與 FOLLOW 資訊構造預測分析表。
第 4 章 · 1 節
上下文有關語言
上下文有關語言
- 4.1
非收縮文法與線性有界帶
非收縮文法與長度引理,aⁿbⁿcⁿ 的完整文法及其不變式證明,線性有界自動機,有界帶上接受問題的可判定性,用逆向推導模擬文法,以及標記算法。
第 5 章 · 5 節
可計算性
可計算性
- 5.1
圖靈機、可判定性與不可判定性
圖靈機格局、通用模擬、識別器與判定器、用交錯執行證明補集定理、自接受的對角線證明、歸約的正確方向、萊斯定理,以及這些語言類在一條鏈中的位置。
- 5.2
不可判定性:自我引用與停機歸約
區分識別與判定,推導停機問題的矛盾,並以可計算映射把結果轉移到空輸入停機問題。
- 5.3
萊斯(Rice)定理與語義性質
將停機問題歸約至可識別語言的非平凡性質。
- 5.4
為甚麼 Post 對應問題不可判定
將接受計算編碼為對應序列,並去除強制首塊骨牌的條件。
- 5.5
為何上下文無關文法的普遍性不可判定
利用對應骨牌與確定性堆疊比較,歸約到文法普遍性問題。
第 6 章 · 2 節
自動機例題
自動機例題
- 6.1
有限自動機:狀態作為不變式
構造並證明一個追蹤奇偶性的確定有限自動機。
- 6.2
非確定性、ε-閉包與子集構造
追蹤 NFA 的全部可能狀態,處理不消耗輸入的轉移,並證明由子集組成的 DFA 識別相同語言。
第 7 章 · 1 節
正則限制
結合有限狀態條件與上下文無關推導。
- 7.1
正則限制下的上下文無關語言
構造上下文無關語言與正則語言交集的文法,並證明其正確性。
第 8 章 · 1 節
平衡括號與文法歧義
剖析樹、首次回零分解與歧義。
- 8.1
上下文無關文法:分析樹、歧義與平衡括號
證明文法恰好生成平衡括號語言,以首次回零分解消除歧義,並連結語法分析、有限狀態的限制與計數。
第 9 章 · 1 節
下推自動機
證明堆疊不變式與非確定性辨認。
- 9.1
下推自動機:堆疊不變式與猜測中點
追蹤識別等長區塊的堆疊機器,雙向證明它的語言,並謹慎運用非確定性識別偶數長度迴文。