上下文無關(guān)文法能夠描述某些具有遞歸結(jié)構(gòu)的特征嗤栓。
上下文無關(guān)文法的應(yīng)用：
研究人類語言禀晓。在名詞原环、動詞、介詞以及他們的短語之間的關(guān)系中存在自然的遞歸贿条。
程序設(shè)計語言的規(guī)范說明和編譯雹仿。
3.1 上下文無關(guān)文法
例子,:
一個文法由一組替換規(guī)則產(chǎn)生，替換規(guī)則又叫做產(chǎn)生式整以。
格式：符號 箭頭 字符串
符號：變元
字符串：變元+終結(jié)符組成
起始變元：通常第一條規(guī)則的左邊
3.1.1 上下文無關(guān)文法的形式定義
定義3.1 上下文無關(guān)文法是一個4元組, 這里
1）v是一個有窮集合胧辽，稱作變元集。
是一個與V不相交的有窮集合公黑，稱作終結(jié)符集邑商。
R是一個有窮的規(guī)則集摄咆，每一條規(guī)則是一個變元和一個有變元和終結(jié)符組成的字符串。
是起始變元人断。
3.1.2上下文無關(guān)文法舉例
考慮文法豆同，其中規(guī)則集R為：
如果把a看作左括弧"("、b看作右括弧")"含鳞，可以看出是所有正常嵌套的括弧字符串構(gòu)成的語言。
考慮文法芹务，其中
蝉绷，
，規(guī)則為：
$<FACTOR> \rightarrow (<EXPR>) | a$$
3.1.3 設(shè)計上下文無關(guān)文法
1 許多CFG是由幾個比較簡單的CFG合并成的枣抱。分成幾部分熔吗，并且分別構(gòu)造每一部分的文法。
部分：
加入新規(guī)則：
2 如果這個語言碰巧是正則的佳晶，可以先構(gòu)造它的DFA桅狠，然后在構(gòu)造它的CFG。轉(zhuǎn)化方法：
對于DFA的每一個狀態(tài)轿秧，設(shè)一個變元
中跌，如果
是DFA中的一個轉(zhuǎn)移函數(shù)，則把規(guī)則
加入CFG菇篡；
如果是DFA的接受狀態(tài)漩符，則把規(guī)則
加入CFG；
設(shè)是DFA的起始狀態(tài)驱还，則取
作為CFG的起始變元嗜暴。
3.1.4 歧義性
最左派生
當(dāng)已知一個歧義文法，有時能找到一個產(chǎn)生相同語言的非歧義文法议蟆，但某些上下文無關(guān)語言只能用歧義文法產(chǎn)生闷沥，這樣的語言稱為固有歧義的。
3.1.5 喬姆斯基范式
定義3.5 一個上下文無關(guān)文法為喬姆斯基范式咐容，如果他的每一個規(guī)則具有如下形式：
定理3.6 任何一個上下文無關(guān)語言都能用喬姆斯基范式的上下文無關(guān)文法產(chǎn)生舆逃。
3.2 下推自動機
3.2.1 下推自動機的形式定義
定義3.8 下推自動機是一個6元組，這里
和F都是有窮集合疟丙，并且
Q是狀態(tài)集颖侄。
是棧字母表享郊。
(Q \times \Gamma_{\epsilon})$是轉(zhuǎn)移函數(shù)览祖。
是起始狀態(tài)。
是接受狀態(tài)集炊琉。
下推自動機在能力上與上下文無關(guān)文法等價.
非形式地描述這個語言的PDA如何工作：
讀輸入中的符號展蒂。每讀一個0把0輸入棧又活。一旦看見1之后，就每讀一個1就把一個0彈出棧锰悼。如果棧中0被排空的時候恰好讀完輸入串柳骄，則接受這個輸入。如果還有1沒有讀的時候棧變成空的箕般；或者棧中還有0的時候1已經(jīng)讀完了耐薯；或者0出現(xiàn)在1的后面，則拒絕這個輸入丝里。
3.2.2 下推自動機機舉例
3.2.3 與上下文無語言的等價性
定理3.12* 一個語言是上下文無關(guān)的曲初，當(dāng)且僅當(dāng)存在一臺下推自動機識別他。
正向：證明主要關(guān)注PDA的非確定性
反向：數(shù)學(xué)歸納法
3.3 非上下文無關(guān)語言
關(guān)于上下文無關(guān)語言的泵引理*
定理3.19 如果A是上下文無關(guān)語言，則存在數(shù)p（泵長度），使得A中任何一個長度不小于p的字符串s能夠分成5段宜咒，s=uvxyz，滿足下述條件
對于每一個i颁褂，
