一、正則語(yǔ)言

預(yù)備知識(shí)

字母表：任意非空有窮集合
字符串：用字母表中的字母組成的序列，比如 Σ = { 0 , 1 } , x = 01001 \Sigma=\{0,1\},x=01001 Σ={0,1},x=01001
連接：首尾連接，如$x=01001,w=abcde,xw=01001abcde$
（特別地，$x...x=x^n$，表示n個(gè)x首尾連接）
串長(zhǎng)度：$x=01001,|x|=5$
空串：$\epsilon ,|\epsilon |=0,x^0=\epsilon$。
（空串$\ne$空格！）
子串&子序列：略
串的標(biāo)準(zhǔn)序：并非字典序！而是先比較長(zhǎng)度，再逐位比較大小！
語(yǔ)言：由字符串組成的集合,令字母表為$\Sigma$（里面的串要根據(jù)標(biāo)準(zhǔn)序排列）
${\Sigma }^{?}$：$\Sigma$上有窮長(zhǎng)度的串（包括$\epsilon$）
${\Sigma }^{+}$：$\Sigma$上正有窮長(zhǎng)度的串（不包括$\epsilon$）
${\Sigma }^{’}$：$\Sigma$上無(wú)窮長(zhǎng)度的串
$\Phi$:空語(yǔ)言
（與空串語(yǔ)言 { ε } \{\varepsilon\} {ε}不同！空串語(yǔ)言 { ε } \{\varepsilon\} {ε}也與空串$\epsilon$不同！）
語(yǔ)言連接：類似于笛卡爾積，兩兩搭配。 A B = { x y ∣ x ∈ a , y ∈ b } AB=\{xy|x\in a,y\in b\} AB={xy∣x∈a,y∈b}
（特殊地， { ε } A = A { ε } = A \{\varepsilon\}A=A\{\varepsilon\}=A {ε}A=A{ε}=A,$\Phi A=A\Phi =\Phi$）

確定性有窮自動(dòng)機(jī)（DFA）

$M=(Q,\Sigma ,\delta ,q_0,F)$
$Q$：有窮狀態(tài)集
$\Sigma$：輸入字母表
$\delta :Q\times \Sigma \to Q$（轉(zhuǎn)移函數(shù)，也就是映射關(guān)系）
（特殊地，$Q\times {\Sigma }^{?}\to Q$（多了個(gè)空串）為擴(kuò)展轉(zhuǎn)移函數(shù)）
$q_0$：初始狀態(tài)
$F$：接受狀態(tài)/終止?fàn)顟B(tài)
語(yǔ)言：能夠被自動(dòng)機(jī)接受的串集合， L ( M ) = { w ∈ Σ ? ∣ δ ( q 0 , w ) ∈ F } L(M)=\{w\in \Sigma^*|\delta(q_0,w)\in F\} L(M)={w∈Σ?∣δ(q0?,w)∈F}
正則語(yǔ)言：可以被有窮自動(dòng)機(jī)接受的語(yǔ)言/可以用正則表達(dá)式描述的語(yǔ)言

設(shè)計(jì)DFA

1. 確定狀態(tài)集
2. 確定轉(zhuǎn)移函數(shù)
3. 標(biāo)注初始狀態(tài)&終結(jié)狀態(tài)

正則運(yùn)算

正則語(yǔ)言對(duì)正則計(jì)算封閉！
正則語(yǔ)言的**交并補(bǔ)、差、對(duì)稱差、連接、*（星號(hào)）**封閉！
A ∪ B = { x ∣ x ∈ A 或 x ∈ B } A\cup B=\{x|x\in A或x\in B\} A∪B={x∣x∈A或x∈B}
A B = { x y ∣ x ∈ A 且 y ∈ B } AB=\{xy|x\in A且y\in B\} AB={xy∣x∈A且y∈B}
$A^{?}=A^0\cup A^1\cup A^2\cup ...$（見(jiàn)前，包括$\epsilon$）

非確定性有窮自動(dòng)機(jī)（NFA，含有$\epsilon$，下一個(gè)狀態(tài)可以有若干種選擇（包括0種））

籌碼集：字符集中只有$\epsilon$與一種字符的語(yǔ)言
$M=(Q,{\Sigma }_{\epsilon },\delta ,q_0,F)$
$Q$：有窮狀態(tài)集
$\Sigma$：輸入字母表（ Σ ε = Σ ∪ { ε } \Sigma_{\varepsilon}=\Sigma\cup\{\varepsilon\} Σε?=Σ∪{ε}）
$\delta :Q\times {\Sigma }_{\epsilon }\to P(Q)$（轉(zhuǎn)移函數(shù)）
$q_0$：初始狀態(tài)
$F$：接受狀態(tài)/終止?fàn)顟B(tài)

任何一個(gè)NFA都有等價(jià)的DFA！
一個(gè)語(yǔ)言是正則語(yǔ)言，當(dāng)且僅當(dāng)只有一個(gè)NFA可以識(shí)別！
（具體轉(zhuǎn)換見(jiàn)其他）

正則表達(dá)式

定義

對(duì)于$R$，有

1. $a$表示語(yǔ)言 { a } \{a\} {a}，其中$a\in \Sigma$（包括$\epsilon$）
2. $\Phi$表示空語(yǔ)言
3. $R=(R_1\cup R_2)$是正則表達(dá)式
4. $R=(R_1°R_2)$是正則表達(dá)式
5. $R=(R_1^{?})$是正則表達(dá)式

則$R$是正則表達(dá)式

eg:數(shù)值常量：
{ + , ? , ε } ( D D ? ∪ D D ? . D ? ∪ D ? . D D ? ) , D = { 0 , 1 , 2 , . . . , 9 } \{+,-,\varepsilon\}(DD^*\cup DD^*.D^*\cup D^*.DD^*),D=\{0,1,2,...,9\} {+,?,ε}(DD?∪DD?.D?∪D?.DD?),D={0,1,2,...,9}
eg:72、3.14159、+7.、-.01

計(jì)算優(yōu)先級(jí)

星號(hào)$?>$連接$>$并$\cup$

定理

Φ ? = { ε } \varPhi^*=\{\varepsilon\} Φ?={ε}
$R\cup \Phi =R$
$R\epsilon =R$
R ∪ ε = R ∪ { ε } ≠ R R\cup \varepsilon=R\cup \{\varepsilon\}\neq R R∪ε=R∪{ε}=R
$R\Phi =\Phi \ne R$

正則表達(dá)式與一個(gè)確定自動(dòng)機(jī)等價(jià)！

GNFA（廣義非確定自動(dòng)機(jī),NFA的推廣）

（與NFA不同的是，轉(zhuǎn)移用的并非是單個(gè)字符，而是一個(gè)正則表達(dá)式！）
$G=(Q,\Sigma ,\delta ,q_{start},q_{accept})$
$Q$：有窮狀態(tài)集
$\Sigma$：輸入字母表（ Σ ε = Σ ∪ { ε } \Sigma_{\varepsilon}=\Sigma\cup\{\varepsilon\} Σε?=Σ∪{ε}）
δ : ( Q ? { q a c c e p t } ) × ( Q ? { q s t a r t } ) → R \delta:(Q-\{q_{accept}\}) \times (Q-\{q_{start}\}) \rightarrow R δ:(Q?{qaccept?})×(Q?{qstart?})→R
（與NFA不同的是，轉(zhuǎn)移狀態(tài)用的并非是單個(gè)字符，而是一個(gè)正則表達(dá)式！）
$q_{start}$：初始狀態(tài)
$q_{accept}$：接受狀態(tài)/終止?fàn)顟B(tài)

CONVERT(G)（過(guò)程函數(shù)）

對(duì)于任意GNFA G，$CONVERT(G)$與$G$等價(jià)！
對(duì)于$G$的狀態(tài)數(shù)$k$，$k=2$時(shí)，$CONVERT(G)=\delta (q_{start},q_{accept})$。
當(dāng)$k>2$時(shí)，令 q r i p ∈ Q ? { q s t a r t } ? { q a c c e p t } , Q ′ = Q ? q r i p q_{rip}\in Q-\{q_{start}\}-\{q_{accept}\},Q'=Q-{q_{rip}} qrip?∈Q?{qstart?}?{qaccept?},Q′=Q?qrip?。
構(gòu)造$G^{\prime }=(Q^{\prime },{\Sigma }_{\epsilon },{\delta }^{\prime },q_{start},q_{accept})$，如此循環(huán)直到$k=2$。
其中，對(duì)于每個(gè)非起始態(tài)$q_i$與每個(gè)非終結(jié)態(tài)$q_j$，${\delta }^{\prime }(q_i,q_j)=(R_1)(R_2)?(R_3)\cup (R_4)$
其中$R_1=\delta (q_i,q_{rip}),R_2=\delta (q_{rip},q_{rip}),R_3=\delta (q_{rip},q_j),R_4=\delta (q_i,q_j)$
（選擇$i\to j$和$i\to (rip{)}^{?}\to j$的并集來(lái)轉(zhuǎn)移狀態(tài)不斷遞歸）

轉(zhuǎn)化方法

1. 增加新的起始點(diǎn)與終結(jié)點(diǎn)，并將其與原來(lái)的起始點(diǎn)/終結(jié)點(diǎn)用$\epsilon$連接
   （類似最大流的源點(diǎn)與匯點(diǎn)，使得起始點(diǎn)沒(méi)有入度，終結(jié)點(diǎn)沒(méi)有出度）
2. 合并平行邊
   
3. 去除中心點(diǎn)（使得點(diǎn)減少更精簡(jiǎn)）
   
   以下圖為例。
   1.添加新起始點(diǎn)s與新終結(jié)點(diǎn)a，用$\epsilon$連接。
   2.將狀態(tài)2去消除中心點(diǎn)，變?yōu)?span id="vxwlu0yf4" class="katex--inline">$b(a\cup b{)}^{?}$后刪除狀態(tài)2
   3.將狀態(tài)1去消除中心點(diǎn)，變?yōu)?span id="vxwlu0yf4" class="katex--inline">$a^{?}b(a\cup b{)}^{?}$，結(jié)束。
   （合并的時(shí)候，如果有不含$\epsilon$的部分，則消去所有$\epsilon$，否則不消去！）
   
   以下圖為例。
   1.添加新起始點(diǎn)s與新終結(jié)點(diǎn)a，用$\epsilon$連接。
   2.將狀態(tài)1去消除中心點(diǎn)。
   （消除路徑經(jīng)過(guò)1的、且不是回路的）
   （1）把$2\stackrel{a}{\to }1\stackrel{b}{\to }3$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$2\stackrel{ab}{\to }3$
   （2）把$3\stackrel{b}{\to }1\stackrel{a}{\to }2$與$3\stackrel{a}{\to }2$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$3\stackrel{ba\cup a}{\to }2$
   （消除新起始點(diǎn)/新終結(jié)點(diǎn)相關(guān)的）
   （3）把$s\stackrel{\epsilon }{\to }1\stackrel{a}{\to }2$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$s\stackrel{a}{\to }2$
   （4）把$s\stackrel{\epsilon }{\to }1\stackrel{b}{\to }3$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$s\stackrel{b}{\to }3$
   （消除路徑經(jīng)過(guò)1的、且是回路的）
   （5）把$2\stackrel{a}{\to }1\stackrel{a}{\to }2$與$2\stackrel{b}{\to }2$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$2\stackrel{aa\cup b}{\to }2$
   （6）把$3\stackrel{b}{\to }1\stackrel{b}{\to }3$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$3\stackrel{bb}{\to }3$
   3.將狀態(tài)2去消除中心點(diǎn)。
   （1）將$s\stackrel{a}{\to }2\stackrel{\epsilon }{\to }a$與$2\stackrel{aa\cup b}{\to }2$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$s\stackrel{a(aa\cup b{)}^{?}}{\to }a$
   （2）將$s\stackrel{b}{\to }3$與$s\stackrel{a}{\to }2\stackrel{aa\cup b}{\to }2\stackrel{ab}{\to }3$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$s\stackrel{a(aa\cup b{)}^{?}ab\cup b}{\to }3$
   （因?yàn)?span id="vxwlu0yf4" class="katex--inline">$3\stackrel{\epsilon }{\to }a$，所以狀態(tài)3也是終結(jié)狀態(tài)）
   （3）將$3\stackrel{bb}{\to }3$與$3\stackrel{ba\cup a}{\to }2\stackrel{aa\cup b}{\to }2\stackrel{ab}{\to }3$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$3\stackrel{(ba\cup a)(aa\cup b{)}^{?}ab\cup bb}{\to }3$
   （4）將$3\stackrel{\epsilon }{\to }a$與$3\stackrel{ba\cup a}{\to }2\stackrel{aa\cup b}{\to }2\stackrel{\epsilon }{\to }a$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$3\stackrel{ba\cup a(aa\cup b{)}^{?}\cup \epsilon }{\to }a$
   4.將狀態(tài)3去消除中心點(diǎn)。
   將$s\stackrel{a(aa\cup b{)}^{?}ab\cup b}{\to }3$、$3\stackrel{(ba\cup a)(aa\cup b{)}^{?}ab\cup bb}{\to }3$、$3\stackrel{ba\cup a(aa\cup b{)}^{?}\cup \epsilon }{\to }a$，
   與$s\stackrel{a(aa\cup b{)}^{?}}{\to }a$變?yōu)?br /> $s\stackrel{(a(aa\cup b{)}^{?}ab\cup b)((ba\cup a)(aa\cup b{)}^{?}ab\cup bb{)}^{?}(ba\cup a(aa\cup b{)}^{?}\cup \epsilon )\cup (a(aa\cup b{)}^{?})}{\to }a$
   

泵引理（一個(gè)正則語(yǔ)言一定存在泵長(zhǎng)度）

若$A$是正則語(yǔ)言，則存在常數(shù)$p$（$p$為泵長(zhǎng)度，類似最大循環(huán)節(jié)長(zhǎng)度），若$s\in A$，$|s|\ge p$，
則$s=xyz$，并且滿足：
（1）$?i\ge 0，x{y}^{i}z\in A$。
（2）$|y|>0$
（3）$|xy|\le p$

如果要證明一個(gè)語(yǔ)言不是正則的，則用反證法 。找一個(gè)反例即可。

二、上下文無(wú)關(guān)文法（CFG）

$G=(V,\Sigma ,R,S)$
$V$：有窮變?cè)?br /> $\Sigma$：有窮終結(jié)符集
$R$：有窮規(guī)則集（形如$A\to w,w\in (V\cup \Sigma {)}^{?}$）
$S\in V$：初始變?cè)?br /> 一個(gè)上下文無(wú)關(guān)語(yǔ)言(CFL)與上下文無(wú)關(guān)文法等價(jià)！

CFG生成

合并

對(duì)于原本的初始變?cè)?span id="vxwlu0yf4" class="katex--inline">$S_1,S_2,...S_k$，新增規(guī)則$S\to S_1|S_2|...S_k$

正則語(yǔ)言生成

用DFA轉(zhuǎn)化為等價(jià)的CFG（正則語(yǔ)言都是上下文無(wú)關(guān)語(yǔ)言！）
對(duì)于原DFA中$\delta (q_i,a)=q_j$（即$q_i\stackrel{a}{\to }{q}_j$），則令$R_i\to a{R}_j$
對(duì)于原DFA中$q_i\in F$（即$q_i$為終止?fàn)顟B(tài)），則令$R_i\to \epsilon$

語(yǔ)法分析樹

文法歧義性

最左派生：每一步都優(yōu)先替換最左邊的變?cè)?/strong>
eg1:$<EXPR>$
$?<EXPR>+<EXPR>$
$?a+<EXPR>$
$?a+<EXPR>\times <EXPR>$
$?a+a\times <EXPR>$
$?a+a\times a$
eg2:$<EXPR>$
$?<EXPR>\times <EXPR>$
$?<EXPR>+<EXPR>\times <EXPR>$
$?a+<EXPR>\times <EXPR>$
$?a+a\times <EXPR>$
$?a+a\times a$
注意到最左派生產(chǎn)生歧義性，因此這是歧義文法。

喬姆斯基范式(CNF)

初始變?cè)荒茉谑阶佑曳匠霈F(xiàn)
只允許如下形式規(guī)則：
$S\to \epsilon$
$A\to BC$
$A\to a$（任意終結(jié)符）

生成CNF

任何的CFG都有等價(jià)的CNF！

1. 添加新初始變?cè)?/strong>$S_0$與新規(guī)則$S_0\to S$（舊初始變?cè)?#xff09;
2. 處理所有的$\epsilon$規(guī)則：
   若有非初始變?cè)?span id="vxwlu0yf4" class="katex--inline">$A\to \epsilon$，則刪除之，并修改所有等式右邊與$A$相關(guān)的內(nèi)容。
   $B\to uAv$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$B\to uv$。
   $B\to uAvAw$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$B\to uvAw|uAvw|uvw$（三種不同的可能情況）
   $B\to A$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$B\to \epsilon$。
   重復(fù)以上，知道刪除所有$\epsilon$相關(guān)規(guī)則為止（$S_0\to \epsilon$除外）
3. 處理所有的單一規(guī)則：（左邊單個(gè)對(duì)應(yīng)右邊單個(gè)）
   刪除$A\to B$，并修改所有相關(guān)的內(nèi)容。
   若有$B\to u$，則添加$A\to u$。
   重復(fù)以上，直到刪除所有單一規(guī)則為止。
4. 處理$A\to u_1{u}_2...u_k$長(zhǎng)規(guī)則：
   將其換成$A\to u_1{A}_1,A_1\to u_2{A}_2,......,A_k=u_{k?1}{u}_k$。
5. 處理終結(jié)符：
   引入新變?cè)?span id="vxwlu0yf4" class="katex--inline">$U_i$與新規(guī)則$U_i\to a_i$。
   $A\to a_i{a}_j$換成$A\to U_i{U}_j$
   $A\to a_{i}B$換成$A\to U_{i}B$
   $A\to B{a}_i$換成$A\to B{u}_i$

$G:S\to ASA|aB$
$A\to B|S$
$B\to b|\epsilon$
求等價(jià)CNF。

（1）添加新初始變?cè)?span id="vxwlu0yf4" class="katex--inline">$S_0$
$S_0\to S$
$S\to ASA|aB$
$A\to B|S$
$B\to b|\epsilon$
（2）處理B的$\epsilon$規(guī)則
$S_0\to S$
$S\to ASA|aB|a$
$A\to B|S|\epsilon$
$B\to b$
（3）處理A的$\epsilon$規(guī)則
$S_0\to S$
$S\to ASA|aB|a|SA|AS$（$S\to S$沒(méi)有用，可以刪去）
$A\to B|S$
$B\to b$
（4）處理單一規(guī)則$S_0\to S$
$S_0\to ASA|aB|a|SA|AS$
$S\to ASA|aB|a|SA|AS$
$A\to B|S$
$B\to b$
（5）處理單一規(guī)則$A\to B$
$S_0\to ASA|aB|a|SA|AS$
$S\to ASA|aB|a|SA|AS$
$A\to S|b$
$B\to b$
（6）處理單一規(guī)則$A\to S$
$S_0\to ASA|aB|a|SA|AS$
$S\to ASA|aB|a|SA|AS$
$A\to ASA|aB|SA|AS|a|b$
$B\to b$
（7）處理長(zhǎng)規(guī)則$ASA$
$S_0\to A{A}_1|aB|a|SA|AS$
$S\to A{A}_1|aB|a|SA|AS$
$A\to A{A}_1|aB|SA|AS|a|b$
$B\to b$
$A_1\to SA$
（8）處理終結(jié)符$a$
$S_0\to A{A}_1|UB|U|SA|AS$
$S\to A{A}_1|UB|U|SA|AS$
$A\to A{A}_1|UB|SA|AS|U|B$
$A_1\to SA$
$B\to b$
$U\to a$
于是得到$G$對(duì)應(yīng)的喬姆斯基范式。

下推自動(dòng)機(jī)（PDA，通常指的是非確定性下推自動(dòng)機(jī)）

由棧組成，每次讀入字符后選擇與棧頂字符匹配或壓入棧。
$M=(Q,\Sigma ,\Gamma ,\delta ,q_0,F)$
$Q$：有窮狀態(tài)集
$\Sigma$：輸入字母表（ Σ ε = Σ ∪ { ε } \Sigma_\varepsilon=\Sigma\cup\{\varepsilon\} Σε?=Σ∪{ε}）
$\Gamma$：棧字母表（ Γ ε = Γ ∪ { ε } \Gamma_\varepsilon=\Gamma\cup\{\varepsilon\} Γε?=Γ∪{ε}）
$\delta :Q\times {\Sigma }_{\epsilon }\times {\Gamma }_{\epsilon }\to P(Q\times {\Gamma }_{\epsilon })$（轉(zhuǎn)移函數(shù)）
$q_0$：初始狀態(tài)（$q_0\in Q$）
$F$：終結(jié)狀態(tài)集（$F?Q$）

以此圖為例，可以繪制出此自動(dòng)機(jī)。
在棧的初始插入一個(gè) $符號(hào)，用于判斷是否為空棧。

上下文無(wú)關(guān)語(yǔ)言CFL

如果一個(gè)語(yǔ)言是上下文無(wú)關(guān)語(yǔ)言（CFL）$?$有下推自動(dòng)機(jī)（PDA）識(shí)別這個(gè)語(yǔ)言。
CFL對(duì)正則運(yùn)算封閉！
CFL對(duì)交$\cap$不封閉！（語(yǔ)言$A,B$是CFL，$A\cap B$不一定是CFL）
CFL對(duì)補(bǔ)運(yùn)算不封閉！（語(yǔ)言$A$是CFL，$A^c$不一定是CFL）

CFL的泵引理（一個(gè)CFL必定有泵）

假設(shè)$A$為上下文無(wú)關(guān)語(yǔ)言，則存在常數(shù)$p$（泵長(zhǎng)度，類似循環(huán)節(jié)最大長(zhǎng)度），若$s\in A$，且$|s|\ge p$，
則$s=uvxyz$，其中
（1）$?i\ge 0,u{v}^{i}x{y}^{i}z\in A$
（2）$|vy|>0$
（3）$|vxy|\le p$

同正則文法一樣，找出一個(gè)反例證明不是CFL即可！

eg1：證明 C = { a i b j c k ∣ 0 ≤ i ≤ j ≤ k } C=\{a^ib^jc^k|0\leq i\leq j\leq k\} C={aibjck∣0≤i≤j≤k}不是CFL。
prove：假設(shè)$C$為上下文無(wú)關(guān)語(yǔ)言，設(shè)$p$為泵長(zhǎng)度，不妨令$s=a^p{b}^p{c}^p$。
則$s=uvxyz$，其中
（1）$?i\ge 0,u{v}^{i}x{y}^{i}z\in C$
（2）$|vy|>0$（即$v$與$y$至少含一種符號(hào)）
（3）$|vxy|\le p$（即$v$與$y$至多含兩種符號(hào)，理由同上）

（1）：$v$與$y$僅含一種符號(hào)
①：$a$不在$v$與$y$之中，此時(shí)只可能是$\underset{p個(gè)}{\underbrace{a...a}}|?|\underset{p個(gè)}{\underbrace{b...b}}|?|\underset{p個(gè)}{\underbrace{c...c}}$，違背了$|vy|>0$，矛盾。
②：$b$不在$v$與$y$之中，此時(shí)只可能是$\underset{p?i個(gè)}{\underbrace{a...a}}|\underset{i個(gè)}{\underbrace{a...a}}|\underset{p個(gè)}{\underbrace{b...b}}|\underset{i個(gè)}{\underbrace{c...c}}|\underset{p?i個(gè)}{\underbrace{c...c}}$，違背了$|vxy|\le q$，矛盾。
③：$c$不在$v$與$y$之中，同①，矛盾。
（2）：$v$與$y$含兩種符號(hào)
此時(shí)易知當(dāng)$i>1$時(shí)，就不具有$a^p{b}^p{c}^p$的形式，即$i=0$或$i=1$，矛盾。（$?i\ge 0$才算成立）
綜上，$C$不是CFL，證畢。

eg2：證明 D = { w w ∣ w ∈ { 0 , 1 } ? } D=\{ww|w\in\{0,1\}^*\} D={ww∣w∈{0,1}?}不是CFL。
prove：假設(shè)$C$為上下文無(wú)關(guān)語(yǔ)言，設(shè)$p$為泵長(zhǎng)度，不妨令$s=0^p{1}^p{0}^p{1}^p$。
則$s=uvxyz$，其中
（1）$?i\ge 0,u{v}^{i}x{y}^{i}z\in C$
（2）$|vy|>0$（即$v$與$y$至少含一種符號(hào)）
（3）$|vxy|\le p$（即$v$與$y$至多含兩種符號(hào)）
（注意這里一定要挑一個(gè)合適的反例，例如$0^{p}10^{p}1$可以拆分為$\underset{p?1個(gè)}{\underbrace{\mathrm{0...0}}}|0|1|0|\underset{p?1個(gè)}{\underbrace{\mathrm{0...0}}}1$，是合法的。）

（1）$vxy$在前半部分里，即$vxy$在第一個(gè)$0^p{1}^p$內(nèi)。此時(shí)隨著$i$的變化，后半個(gè)$0^p{1}^p$的數(shù)量會(huì)與前半個(gè)不同，不匹配，矛盾。
（2）$vxy$在后半部分里，同上，矛盾。
（3）$vxy$橫跨中間，則$v$與$y$不可以含兩種符號(hào)，故$v$為$1^i$，$y$為$1^i$，同理$i$的變化會(huì)讓頭尾的兩個(gè)$0^p$與$1^p$數(shù)量與內(nèi)部的兩個(gè)不同，不匹配，矛盾。
綜上，$D$不是CFL，證畢。

三、圖靈機(jī)

單帶圖靈機(jī)（TM）

有一個(gè)紙帶序列與一個(gè)可以左右雙向移動(dòng)的讀寫頭
$M=(Q,\Sigma ,\Gamma ,\delta ,q_0,q_{acc},q_{rej})$
$Q$：有窮狀態(tài)集
$\Sigma$：輸入字母表（注意空格符$B\notin \Sigma$）
$\Gamma$：帶字母表， Σ ∪ { B } ? Γ \Sigma\cup\{B\}\subseteq\Gamma Σ∪{B}?Γ
$\delta$： Q × Γ → Q × Γ × { L , R } Q\times\Gamma\rightarrow Q\times\Gamma\times\{L,R\} Q×Γ→Q×Γ×{L,R}（轉(zhuǎn)移函數(shù)，L/R表示左移/右移）
$q_0\in Q$：初始狀態(tài)
$q_{acc}\in Q$：停機(jī)接受狀態(tài)
$q_{req}\in Q$：停機(jī)拒絕狀態(tài)，$q_{acc}\ne q_{rej}$
單帶圖靈機(jī)的格局（序列的當(dāng)前狀態(tài)）：$uqav$
$q$：當(dāng)前狀態(tài)
$uav$：當(dāng)前帶上的內(nèi)容
$a$：當(dāng)前的掃描符號(hào)
（即之前的序列$u$|當(dāng)前的狀態(tài)$q$|當(dāng)前的掃描符號(hào)$a$|后面的序列$v$）
eg:對(duì)于帶$101101111$,狀態(tài)$q_7$正在掃描第五個(gè)字符$0$，其格局為$1011q_{7}01111$
初始格局：$q_{0}w$（w為輸入串）
接受格局：$u{q}_{acc}av$
拒絕格局：$u{q}_{rej}av$
停機(jī)格局：$u{q}_{acc}av/u{q}_{rej}av$
（圖靈機(jī)的計(jì)算結(jié)果只能是停機(jī)接受、停機(jī)拒絕、不停機(jī)）
若$\delta (q_i,b)=(q_j,c,L)$（L表示左移），則
$ua{q}_{i}bv$產(chǎn)生$u{q}_{j}acv$（將$b$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$c$，$q_i$變?yōu)?span id="vxwlu0yf4" class="katex--inline">$q_j$后左移）
$q_{i}bv$產(chǎn)生$q_{j}cv$（已經(jīng)在帶最左端，不可再左移）
若$\delta (q_i,b)=(q_j,c,R)$（R表示右移），則
$ua{q}_{i}bv$產(chǎn)生$uac{q}_{j}v$（因?yàn)?strong>帶一定可以繼續(xù)右移，所以不需要分情況）
如何判斷當(dāng)前狀態(tài)已經(jīng)在帶最左端：在當(dāng)前位置寫下某個(gè)特殊符號(hào)，讓帶頭向左移動(dòng)，若仍然檢測(cè)到該符號(hào)則說(shuō)明在最左端，否則恢復(fù)原來(lái)的符號(hào)。

圖靈可識(shí)別=遞歸可枚舉=計(jì)算可枚舉=半可判定=半可計(jì)算
圖靈可判定=遞歸=可解=能行=可判定=可計(jì)算

圖靈可識(shí)別$\ne$圖靈可判定！

圖靈機(jī)的等價(jià)變形

多帶圖靈機(jī)（同時(shí)多個(gè)紙帶）

δ : Q × Γ k → Q × Γ k × { L , R } k \delta:Q\times\Gamma^k\rightarrow Q\times\Gamma^k\times\{L,R\}^k δ:Q×Γk→Q×Γk×{L,R}k
$\delta :(q_i,a_1,...,a_k)=(q_j,b_1,...,b_k,\underset{k個(gè)}{\underbrace{L/R,L/R,...,L/R}})$
多帶圖靈機(jī)可轉(zhuǎn)換為等價(jià)的單帶圖靈機(jī)！
圖靈可識(shí)別$?$可用多帶圖靈機(jī)識(shí)別！

非確定性圖靈機(jī)（NTM）

在左移/右移的基礎(chǔ)上增加了“停止”狀態(tài)$S$
d e l t a : Q × Γ → P ( Q × Γ × { L , R , S } ) delta:Q\times\Gamma\rightarrow P(Q\times\Gamma\times\{L,R,S\}) delta:Q×Γ→P(Q×Γ×{L,R,S})
因此計(jì)算NTM格局的方式變?yōu)榱?strong>計(jì)算樹（擁有多個(gè)非確定性分支）

每個(gè)非確定性圖靈機(jī)（NTM）都有等價(jià)的確定性圖靈機(jī)（DTM）！
圖靈可識(shí)別$?$可用非確定性圖靈機(jī)識(shí)別！
圖靈可判定$?$可用非確定性圖靈機(jī)判定！

識(shí)別器：輸入$x$，輸出$0/1/?$（停機(jī)拒絕/停機(jī)接受/不停機(jī)）
判定器：輸入$x$，輸出$0/1$（停機(jī)拒絕/停機(jī)接受，沒(méi)有不停機(jī)）
轉(zhuǎn)換器：輸入$x$，輸出$y$（輸出一個(gè)串而非一位，通常用于計(jì)算函數(shù)）
產(chǎn)生器：輸入$0^n$，輸出$x_n$（生成序列）
枚舉器：輸入$\epsilon$，輸出$x_1,x_2,x_3,...$（無(wú)輸入，無(wú)遺漏，無(wú)多余，無(wú)順序，可重復(fù)）

圖靈可識(shí)別$?$圖靈可枚舉！

圖靈機(jī)算法

對(duì)象編碼寫作<$O_1,O_2,...,O_k$>，表示對(duì)串$O_1{O}_2...O_k$進(jìn)行一種編碼轉(zhuǎn)換。
eg:設(shè)定一種對(duì)$01$串編碼的方式，將所有的字符重復(fù)出現(xiàn)1次，多個(gè)串拼接時(shí)用兩個(gè)不同的字符作為間隔符拼接。
$x=010,y=11,$<$x,y$>$=001100101111$（$001100|10|1111$）

遞歸定理

存在可計(jì)算函數(shù)$q:{\Sigma }^{?}\to {\Sigma }^{?}$，$?w$，$q(w)$是圖靈機(jī)$P_w$的描述，單帶圖靈機(jī)$P_w$打印出$w$，然后停機(jī)。（一個(gè)函數(shù)如果可計(jì)算，則和圖靈機(jī)等價(jià)！）

自我復(fù)制機(jī)：自己打印自己的圖靈機(jī)。 $?x,SELF(x)=<SELF>$（不斷地進(jìn)行自我復(fù)制）
遞歸定理：假設(shè)單帶圖靈機(jī)$T$有計(jì)算函數(shù)$t:{\Sigma }^{?}\times {\Sigma }^{?}\to {\Sigma }^{?}$，則存在單帶自動(dòng)機(jī)$R$，其計(jì)算函數(shù)$r:{\Sigma }^{?}\times {\Sigma }^{?}\to {\Sigma }^{?}$，$?w,r(w)=t($<$R$>$,w)$
（$T$可以用$R$來(lái)代替，從而實(shí)現(xiàn)遞歸運(yùn)算，將問(wèn)題轉(zhuǎn)化）

圖靈機(jī)接受性問(wèn)題

定義 A T M = { < M , w > ∣ 圖靈機(jī) M 能接受串 w } A_{TM}=\{<M,w>|圖靈機(jī)M能接受串w\} ATM?={<M,w>∣圖靈機(jī)M能接受串w}
一個(gè)圖靈機(jī)能接受某些給定的串構(gòu)成的語(yǔ)言， 是圖靈可識(shí)別的！是不可判定的！

通用機(jī)：存在一個(gè)固定的圖靈機(jī)$U$，對(duì)于任意圖靈機(jī)$M$與輸入$w$，$U(<M,w>)=M(w)$

圖靈機(jī)極小性問(wèn)題

極小圖靈機(jī)：對(duì)于圖靈機(jī)$M$，其描述的字符<$M$>是最短的。
（因?yàn)閳D靈機(jī)有無(wú)窮多種，每種都有等價(jià)的極小圖靈機(jī)，因此$MI{N}_{TM}$是無(wú)窮語(yǔ)言。）
$MI{N}_{TM}$不是圖靈可識(shí)別！

不動(dòng)點(diǎn)(x=f(x))

遞歸定理的不動(dòng)點(diǎn)形式：對(duì)于$?$可計(jì)算函數(shù)$t:{\Sigma }^{?}\to {\Sigma }^{?}$，存在一個(gè)圖靈機(jī)$F$，使得$t(<F>)$描述一個(gè)與$F$等價(jià)的圖靈機(jī)。

四、可計(jì)算問(wèn)題/不可計(jì)算問(wèn)題

算法可解：存在處處停機(jī)的等價(jià)圖靈機(jī)。

對(duì)于正則語(yǔ)言的可判定問(wèn)題

A D F A = { < B , w > ∣ D F A B 接受串 w } A_{DFA}=\{<B,w>|DFA\ B接受串w\} ADFA?={<B,w>∣DFA?B接受串w}是可判定語(yǔ)言。
同理$A_{NFA}$是可判定語(yǔ)言。
A R E X = { < R , w > ∣ 正則表達(dá)式? R 派生串 w } A_{REX}=\{<R,w>|正則表達(dá)式\ R派生串w\} AREX?={<R,w>∣正則表達(dá)式?R派生串w}是可判定語(yǔ)言。
（因?yàn)镈FA、NFA、REX提供給圖靈機(jī)的都是等價(jià)的，圖靈機(jī)能在這三種之間進(jìn)行轉(zhuǎn)換）
（DFA空性） E D F A = { < A > ∣ A 是 D F A 且 L ( A ) = ? } E_{DFA}=\{<A>|A是DFA且L(A)=\empty\} EDFA?={<A>∣A是DFA且L(A)=?}是可判定語(yǔ)言
（DFA等價(jià)性） E Q D F A = { < A , B > ∣ A 與 B 都是 D F A 且 L ( A ) = L ( B ) } EQ_{DFA}=\{<A,B>|A與B都是DFA且L(A)=L(B)\} EQDFA?={<A,B>∣A與B都是DFA且L(A)=L(B)}是可判定語(yǔ)言。

關(guān)于上下文無(wú)關(guān)語(yǔ)言（CFL）的可判定問(wèn)題

每一個(gè)CFL是可判定的！
A C F G = { < G , w > ∣ C F G G 派生串 w } A_{CFG}=\{<G,w>|CFG\ G派生串w\} ACFG?={<G,w>∣CFG?G派生串w}是可判定語(yǔ)言。
（CFG空性） E C F G = { < G > ∣ C F G G ， L ( G ) = ? } E_{CFG}=\{<G>|CFG\ G，L(G)=\emptyset\} ECFG?={<G>∣CFG?G，L(G)=?}是可判定語(yǔ)言。
（CFG等價(jià)性） E Q C F G = { < G , H > ∣ C F G G , H ， L ( G ) = L ( H ) } EQ_{CFG}=\{<G,H>|CFG\ G,H，L(G)=L(H)\} EQCFG?={<G,H>∣CFG?G,H，L(G)=L(H)}是不可判定語(yǔ)言！

不可計(jì)算問(wèn)題

有理數(shù)集可數(shù)，實(shí)數(shù)集不可數(shù)！

用對(duì)角化方法證明不可計(jì)算問(wèn)題

對(duì)角化方法：在判定結(jié)果圖上構(gòu)造一個(gè)非圖靈機(jī)后觀察對(duì)角線上的判定結(jié)果。
eg：定義 A T M = { < M , w > ∣ 圖靈機(jī) M 能接受串 w } A_{TM}=\{<M,w>|圖靈機(jī)M能接受串w\} ATM?={<M,w>∣圖靈機(jī)M能接受串w}，
證明：$A_{TM}$不可判定。

證：
那只需用對(duì)角化法證明$D_{TM}$不可判定。
假設(shè)存在圖靈機(jī)$H$可判定$A_{TM}$，即：
$H(<M>,w)=\{\begin{array}{ll}接受& M接受w\\ 拒絕& M不接受w\end{array}$
構(gòu)造$D$=“對(duì)于輸入<$M$>，$M$是圖靈機(jī)”
在輸入"$M,<M>$"上運(yùn)行$H$，如果$H$接受則拒絕$D$，反之接受，即：
$D(<M>)=\{\begin{array}{ll}接受& M不接受<M>\\ 拒絕& M接受<M>\end{array}$
（M串是圖靈機(jī)自己的編碼，即所有w中的一部分，即$D_{TM}$是$A_{TM}$的特例。）
不妨令$M=D$，即：
$D(<D>)=\{\begin{array}{ll}接受& D不接受<D>\\ 拒絕& D接受<D>\end{array}$
顯然矛盾，故原命題得證。
如圖所示，對(duì)于$H(<M,<M>>)$，$D$的結(jié)果是反過(guò)來(lái)的，而$D<D>$上的結(jié)果卻并不是全部接受。

非圖靈可識(shí)別語(yǔ)言

對(duì)于$A$和$A$的補(bǔ)集$A^c/\overline{A}={\Sigma }^{?}?A$，A可判定$?$A與$A^c$圖靈可識(shí)別。（可判定語(yǔ)言對(duì)布爾運(yùn)算封閉）

歸約法

（圖靈機(jī)的停機(jī)問(wèn)題） H A L T T M = { < M , w > ∣ 圖靈機(jī) M 在輸入 w 上停機(jī) } HALT_{TM}=\{<M,w>|圖靈機(jī)M在輸入w上停機(jī)\} HALTTM?={<M,w>∣圖靈機(jī)M在輸入w上停機(jī)}是不可判定的。
（圖靈機(jī)空性問(wèn)題） E T M = { < M > ∣ M 是圖靈機(jī)且 L ( M ) = ? } E_{TM}=\{<M>|M是圖靈機(jī)且L(M)=\emptyset \} ETM?={<M>∣M是圖靈機(jī)且L(M)=?}是不可判定的。
（圖靈機(jī)正則性問(wèn)題） R E G U L A R T M = { < M > ∣ M 為圖靈機(jī)且 L ( M ) 正則 } REGULAR_{TM}=\{<M>|M為圖靈機(jī)且L(M)正則\} REGULARTM?={<M>∣M為圖靈機(jī)且L(M)正則}是不可判定的。
（圖靈機(jī)等價(jià)性問(wèn)題） E Q T M = { < M 1 , M 2 > ∣ M 1 和 M 2 是圖靈機(jī)且 L ( M 1 ) = L ( M 2 ) } EQ_{TM}=\{<M_1,M_2>|M_1和M_2是圖靈機(jī)且L(M_1)=L(M_2)\} EQTM?={<M1?,M2?>∣M1?和M2?是圖靈機(jī)且L(M1?)=L(M2?)}是不可判定的。