課程名：形式語言與自動機

作者：Lupinus_Linn

許可證：CC-BY-NC-SA 3.0 創作共用-署名-非商業性-相同方式共享

• 署名（英語：Attribution，BY）：您（用戶）可以復制、發行、展覽、表演、放映、廣播或通過信息網絡傳播本作品；您必須按照作者或者許可人指定的方式對作品進行署名。
• 非商業性使用（英語：Noncommercial，NC）：您可以自由復制、散布、展示及演出本作品；您不得為商業目的而使用本作品。
• 相同方式共享（英語：Sharealike，SA）：您可以自由復制、散布、展示及演出本作品；若您改變、轉變或更改本作品，僅在遵守與本作品相同的許可條款下，您才能散布由本作品產生的派生作品。（參見copyleft。）

引用：

• 本文中部分文字與圖片引用自北京郵電大學計算機學院王柏教授的《形式語言與自動機》課程課件。
• 緒論中的證明方法部分引自清華大學王生原老師課件。
• 部分題目插圖引用自北京郵電大學出版社《形式語言與自動機 第二版》教材。

在此一并表示感謝，并不做商業用途。

本筆記所有內容的傳送門

Part.1緒論, Part.2 語言與文法
Part 3.有限自動機
Part.4 正則語言，2DFA，Mealy&Moore機
Part.5 上下文無關語言與下推自動機(PDA)
Part.6 圖靈機

文章目錄

• • Part 1. 緒論
  • • 1.1 課程核心內容
    • 1.2 形式語言
    • 1.3 自動機
    • 1.4 文法
    • 1.5 證明技術
  • Part 2.語言和文法
  • • 2.1 基本概念
    • 2.2 常用符號規定
    • 2.3 Chomsky文法體系

Part 1. 緒論

1.1 課程核心內容

(序號指課本章節)

語言，文法, 語言的運算(并、連接、閉包、…)， 推導， 句型， 句子

有限自動機、三種類型（DFA/NFA/?-NFA），極小化，相互關系
右線性文法，正則式，文法與自動機、正則式的關系
3型語言的性質（泵浦引理等）
有輸出的自動機

推導樹，二義性
上下文無關文法的變換
CNF/GＮF (GNF 本屆考試不要求)
下推自動機
文法與自動機的關系 （本屆PDA 轉 CFG 考試不要求）
文法特性（２型語言的泵浦引理等）

圖靈機 （本屆僅5.1 基本圖靈機）

1.2 形式語言

形式化描述的字母表上的字符串的集合

形式語言是某個字母表上的字符串的集合， 有一定的描述范圍。

1.3 自動機

自動機是具有離散輸入輸出的數學模型。自動機接受一定的輸入，執行一定的動作， 產生一定的結果。使用狀態遷移描述整個工作過程。

自動機的本質：根據狀態、輸入和規則決定 下一個狀態

狀態： 一個標識，能區分自動機在不同時刻的狀況。有限狀態系統具有任意有限數目的內部“狀態”。

有限自動機可以認為是由一個帶有讀頭的有限控制器和一條寫有字符的輸入帶組成。

自動機和語言的關系

形式語言用于接受的自動機

非限定性語言	圖靈機
上下文有關語言	線性有界自動機
上下文無關語言	下推自動機
正則語言	有限自動機

1.4 文法

文法是定義語言的一個數學模型，而自動機可 看作是語言的識別系統。

1.5 證明技術

“If – Then”命題

把 If部分作為已知的命題，把 Then 部分作為結論.

“If - And - Only - If ”命題

可分別證明如下兩個命題：
1 if A then B，
2 if B then A.

欲證R ? S

可證明如下命題： if x∈R then x∈S

欲證R = S

可分別證明如下兩個命題：
1 if x∈R then x∈S
2 if x∈S then x∈R

逆否命題的證明

有時，證明原命題的逆否(contrapositive)命題更加方便。
欲證 if A then B ， 可證明如下命題： if not B then not A

反證法

欲證 if H then C ，可以把 H 和 not C 都作為已知的命題，把任何一個矛盾( contradiction ) 命題作為新的結論.

舉例證明存在性&舉反例否定任意性

集合的歸納定義

由 3 部分構成：
1 基礎（basis） // 直接定義集合中的元素（至少1個）
2 歸納（induction）// 從已知元素生成新元素的規則
3 極小性限制 // 申明集合中的元素只能由1、2 生成

結構歸納法

對于歸納定義的集合S，欲證對于任意x∈S，滿足性質P(x).
1 基礎（basis） // 若有直接定義a∈S，則證明P(a)
2 歸納（induction） // 若歸納定義中有規則
$a_1,a_2,\dots ,a_n\in S,thenf(a_1,a_2,\dots ,a_n)inS$
則證明$ifP(a_1),P(a_2),\dots ,P(a_n)inSthenP(f(a_1,a_2,\dots ,a_n))成立$

Part 2.語言和文法

2.1 基本概念

• 字母表
• 字符串
• 閉包
• 語言
• 文法
• 推導和句型
• 句子

2.2 常用符號規定

• 字母表: Σ, Γ, . . .
• 字符: a, b, c, . . .
• 字符串: . . . , w, x, y, z
• 集合: A,B, C, . . .

2.3 Chomsky文法體系

Chomsky文法體系該體系對生成式（產生式）的形式做了一些規定， 分為四類，即0型、1型、2型、3型文法.

文法類別對應語言對應自動機生成式約束

0型文法	遞歸可枚舉語言	圖靈機	No
1型文法	上下文有關語言	若不考慮ε，與線性有界自動機LBA等價。	1. 左部的長度小于右部 2. 不含A->ε
2型文法	上下文無關語言	下推自動機PDA	左部是單個非終結符。
3型文法	正則語言	有限自動機	左/右線性文法。

• 注意，四種文法從上到下是包含關系，詢問類別時應該取盡量靠下的文法（范圍較小的文法）。

總結

以上是生活随笔為你收集整理的形式语言与自动机 Part.1绪论, Part.2 语言与文法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。