跳到正文

CSCI3130

形式語言及自動機理論

有限自動機與正則語言、上下文無關文法與下推自動機、語法分析、上下文有關語言、圖靈機與不可判定性。

9 章 · 27 節EN · 繁 · 简
我的課程筆記

你的進度

0/ 27 節已標記完成

下一節: 可區分性與最小確定型自動機

完成記錄儲存在此瀏覽器中。

這門課在網上

CSCI3130 筆記裏的內容

定理卡
77
定義
61
反例
34
概念視角
13
思想史
0
證明透視
33

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 27 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

在網上定理卡 77 · 定義 61 · 反例 34 · 概念視角 13 · 證明透視 33

這門課的概念視角還沒有記錄到網上。

在知識圖譜中打開這門課

數字只算這門課 27 節公開筆記裏寫了甚麼,不是網上已記錄的關係。目前其中 0 節已細緻地記錄到網上。

第 1 章 · 5 節

正則語言

正則語言

定理 16 · 定義 14反例 8視角 1證明透視 6

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 1.1

    可區分性與最小確定型自動機

    由剩餘語言構造最小 DFA,並透過劃分細化來計算它。

  2. 1.2

    有限自動機、正則表達式與泵引理

    定義 DFA、NFA 與正則表達式,證明子集構造、Thompson 構造與狀態消去構造,並證明泵引理與基於可區分性的狀態數下界。

  3. 1.3

    確定有限自動機的判定問題

    利用有限圖搜尋判定空性、等價性與無窮性。

  4. 1.4

    正則語言的泵引理

    利用有限狀態的重複與正確的量詞次序證明語言非正則。

  5. 1.5

    同態與正則語言

    為同態的正像與逆像構造有限自動機。

第 2 章 · 9 節

上下文無關語言

上下文無關語言

定理 21 · 定義 13反例 11視角 3證明透視 10

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 2.1

    下推自動機:終結狀態接受與空堆疊接受

    在保持語言不變的前提下,在兩種非確定性下推自動機的接受約定之間互相轉換。

  2. 2.2

    範式與堆疊計算中隱藏的文法

    證明上下文無關範式定理,補全泵引理的二叉樹前提,並從任意非確定下推自動機構造文法。

  3. 2.3

    以動態規劃判定上下文無關文法的成員關係

    為喬姆斯基(Chomsky)範式文法推導 CYK 表。

  4. 2.4

    上下文無關文法、堆疊自動機與泵引理

    推導、語法分析樹與歧義;括號平衡與 aⁿbⁿ 的文法;用非確定型下推自動機模擬文法;上下文無關語言的泵引理及其局限。

  5. 2.5

    簡化上下文無關文法

    在保持語言不變的前提下消除空產生式與單位產生式。

  6. 2.6

    將文法轉換為喬姆斯基範式

    在保持上下文無關語言不變的前提下,分離終結符並將產生式二元化。

  7. 2.7

    上下文無關語言的泵引理

    從語法分析樹推導上下文無關泵引理,並正確運用其量詞。

  8. 2.8

    上下文無關語言與正則約束

    將下推自動機與有限自動機結合,並考察封閉性的局限。

  9. 2.9

    確定性下推自動機與接受方式

    追蹤一部確定性堆疊機,並證明空堆疊接受方式所帶來的前綴限制。

第 3 章 · 2 節

語法分析

語法分析

定理 6 · 定義 7反例 2視角 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 3.1

    LR(0) 項目、移進-歸約分析與前瞻

    增廣文法、LR(0) 項目、閉包與 goto、規範族、ACTION/GOTO 表與衝突,一張完整的分析表與一次完整分析,以及通過 S → a | ab 區分 LR(0) 與 LR(1)。

  2. 3.2

    預測分析與 LL(1) 分析表

    利用可空性、FIRST 與 FOLLOW 資訊構造預測分析表。

第 4 章 · 1 節

上下文有關語言

上下文有關語言

定理 5 · 定義 3反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 4.1

    非收縮文法與線性有界帶

    非收縮文法與長度引理,aⁿbⁿcⁿ 的完整文法及其不變式證明,線性有界自動機,有界帶上接受問題的可判定性,用逆向推導模擬文法,以及標記算法。

第 5 章 · 5 節

可計算性

可計算性

定理 15 · 定義 13反例 5視角 2證明透視 7

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 5.1

    圖靈機、可判定性與不可判定性

    圖靈機格局、通用模擬、識別器與判定器、用交錯執行證明補集定理、自接受的對角線證明、歸約的正確方向、萊斯定理,以及這些語言類在一條鏈中的位置。

  2. 5.2

    不可判定性:自我引用與停機歸約

    區分識別與判定,推導停機問題的矛盾,並以可計算映射把結果轉移到空輸入停機問題。

  3. 5.3

    萊斯(Rice)定理與語義性質

    將停機問題歸約至可識別語言的非平凡性質。

  4. 5.4

    為甚麼 Post 對應問題不可判定

    將接受計算編碼為對應序列,並去除強制首塊骨牌的條件。

  5. 5.5

    為何上下文無關文法的普遍性不可判定

    利用對應骨牌與確定性堆疊比較,歸約到文法普遍性問題。

第 6 章 · 2 節

自動機例題

自動機例題

定理 4 · 定義 4反例 3視角 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 6.1

    有限自動機:狀態作為不變式

    構造並證明一個追蹤奇偶性的確定有限自動機。

  2. 6.2

    非確定性、ε-閉包與子集構造

    追蹤 NFA 的全部可能狀態,處理不消耗輸入的轉移,並證明由子集組成的 DFA 識別相同語言。

第 7 章 · 1 節

正則限制

結合有限狀態條件與上下文無關推導。

定理 2 · 定義 2反例 1視角 1證明透視 1

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 7.1

    正則限制下的上下文無關語言

    構造上下文無關語言與正則語言交集的文法,並證明其正確性。

第 8 章 · 1 節

平衡括號與文法歧義

剖析樹、首次回零分解與歧義。

定理 6 · 定義 3反例 1視角 1證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 8.1

    上下文無關文法:分析樹、歧義與平衡括號

    證明文法恰好生成平衡括號語言,以首次回零分解消除歧義,並連結語法分析、有限狀態的限制與計數。

第 9 章 · 1 節

下推自動機

證明堆疊不變式與非確定性辨認。

定理 2 · 定義 2反例 2證明透視 2

本章骨架 →在網上看本章 →本章還沒有記錄到網上

  1. 9.1

    下推自動機:堆疊不變式與猜測中點

    追蹤識別等長區塊的堆疊機器,雙向證明它的語言,並謹慎運用非確定性識別偶數長度迴文。

Vercel 瀏覽統計與公開頁面效能量度均須分別取得同意,兩者均非使用網站的必要條件。

網站功能儲存(按需使用)

安全、登入及你選擇的偏好會按需使用儲存,與可選統計分開處理。

撤回會停止後續統計;需要卸載已載入的統計程式時,頁面會重新載入。已傳送的資料不會因此刪除。

查看 Cookie 與儲存詳情