一捏萍、Chomsky對文法和語言對分類
??Chomsky的分類依據(jù)是產(chǎn)生該語言的文法。
0型文法
??所有一般的PSG（短語結(jié)構(gòu)文法）及PSL（短語結(jié)構(gòu)語言）读整。似乎對文法和語言沒有特別的要求宾舅，這一類包含了以下介紹的1型在验、2型糊识、3型文法绩社。
1型文法
??文法的任意產(chǎn)生式 α -> β ，均有 | α | ≤ | β |赂苗。1型文法也叫上下文相關(guān)文法（CSG）愉耙，其產(chǎn)生的語言稱上下文相關(guān)語言（CSL）。簡單理解：產(chǎn)生式左邊的終結(jié)符和非終結(jié)符數(shù)目之和不大于產(chǎn)生式右邊拌滋。
2型文法
??文法的任意產(chǎn)生式 α -> β 朴沿，均有 | α | ≤ | β |，且α是非終結(jié)符败砂。2型文法也叫上下文無關(guān)文法（CFG）悯仙，其產(chǎn)生的語言稱上下文無關(guān)語言（CFL）。在1型文法基礎(chǔ)上吠卷，還要求產(chǎn)生式左邊只能有非終結(jié)符（大量作業(yè)證明，還只有一個非終結(jié)符）沦零。
3型文法
??文法的任意產(chǎn)生式 α -> β 祭隔，只有形如A -> w或A -> wB的形式（一個非終結(jié)符推導(dǎo)出終結(jié)符或終結(jié)符+一個非終結(jié)符）。3型文法也叫右線型文法（RLG）或正則文法（RG）路操。
??簡單理解：產(chǎn)生式左邊只有一個非終結(jié)符疾渴，產(chǎn)生式右邊最多一個非終結(jié)符，且在最右邊屯仗。
例題
二搞坝、語言間的基本運算
1. 聯(lián)合運算
??L = L1∪L2 = {w | w∈L1或w∈L2}
??兩個語言L1、L2聯(lián)合得到的語言L魁袜，其句子是原來兩個語言所有句子桩撮。
2. 連接運算
??L = L1L2 = {w | w=w1w2, w∈L1, w∈L2}
??兩個語言經(jīng)連接運算得到的語言L，其句子是兩個語言L1峰弹、L2句子前后相連店量。
3. 迭代運算
??語言之間不停推導(dǎo)，替換鞠呈。
定理：上下文相關(guān)語言融师，上下文無關(guān)語言和正則語言在3種運算內(nèi)是有效封閉的。有效指仍能合法產(chǎn)生一個語言蚁吝；封閉指經(jīng)運算后旱爆，語言類型不發(fā)生改變舀射。
三、正則集和正則表達式
正則集
對于字母表∑上的語言L
- 若L是有限的怀伦，則L是正則的（正則集）脆烟。
- 或L能由正則語言經(jīng)3種運算產(chǎn)生。
正則語言即正則集空镜。
正則表達式
- 若a∈∑浩淘，則a是正則表達式
- 或正則表達式經(jīng)3種運算得到的
正則集和正則語言都是一種有窮描述。
四吴攒、有限自動機
有限自動機分類如下：
- 有限狀態(tài)自動機（FA）张抄，包括確定的FA（DFA）和不確定的FA（NFA）
- 下推自動機（PDA），包括單態(tài)PDA和多態(tài)PDA
- 圖靈機（TM）
Ⅰ. FA
??有限狀態(tài)自動機是狀態(tài)轉(zhuǎn)換圖洼怔，根據(jù)當(dāng)前狀態(tài)和接收到的字符確定應(yīng)轉(zhuǎn)換到什么狀態(tài)署惯。DFA對于每一狀態(tài)和接收字符有確定的狀態(tài)轉(zhuǎn)換，而NFA可能會轉(zhuǎn)換到不同的狀態(tài)镣隶。
例1 構(gòu)造DFA
例2 構(gòu)造NFA
Ⅱ. PDA
??下推自動機用來表示無窮語言极谊，棧存儲方式。
- 單態(tài)PDA指令為<a, Z, AZ>安岂，表示棧頂元素為Z時轻猖，讀取到a字符，則將Z彈出棧域那，將AZ壓棧咙边。
- 多態(tài)PDA的五元式為<q, a, Z, q', AZ>，表示當(dāng)前狀態(tài)是q次员，棧頂元素是Z時败许，讀取到a字符，則狀態(tài)變?yōu)閝'淑蔚，并將Z彈出棧市殷，將AZ壓棧。
例1 構(gòu)造能接收如下語言的單態(tài)PDA
例2 構(gòu)造能接收如下語言的多態(tài)PDA
??當(dāng)字符串掃描結(jié)束刹衫，棧為空醋寝，稱這是該PDA能夠接收的語言。
Ⅲ.TM
??圖靈機（TM）的有限狀態(tài)控制器（FSC）處于某個狀態(tài)绪妹，讀寫頭將掃描帶上的一個單元甥桂。根據(jù)當(dāng)前狀態(tài)和掃描到的字符，TM發(fā)生如下動作：
- FSC狀態(tài)改變
- 擦除掃描到的帶上符號邮旷，并印刷上新的（可能與原來相同）
- 讀寫頭向左/右移動一個單元黄选，或不移
指令描述：<q, x, q', W, {R, L, N}>
其中，q和q'是前后狀態(tài)，x是讀到的字符办陷，W是印刷上的新字符貌夕，{R, L, N}是讀寫頭動作。
圖靈機的幾種技術(shù)
- 存儲技術(shù)民镜。如[q, a], [q, aa]兩個狀態(tài)可以存儲讀到的1個或2個a啡专，用特殊狀態(tài)實現(xiàn)。
- 移動技術(shù)制圈。如[q, a1], [q, a1, a2], [q, a2, a3]们童，結(jié)合存儲技術(shù)可實現(xiàn)如向右移動2個位置的功能。
- 多道技術(shù)鲸鹦。常用于實現(xiàn)圖靈機的計算功能慧库。
- 查訖技術(shù)。結(jié)合多道技術(shù)馋嗜，查詢到目標(biāo)后在另一道對應(yīng)位置標(biāo)記特殊字符齐板。
例 構(gòu)造3道圖靈機，實現(xiàn)二進制數(shù)的按位異或運算
