计算理论第2章去某范式版ppt课件

1、第一部分 自动机与言语第2章 上下文无关文法上下文无关文法的引入v对任何言语对任何言语L L，有一个字母表，有一个字母表，使得，使得L L* * 。 vL L的详细组成构造是什么样的？的详细组成构造是什么样的？v一个给定的字符串能否为一个给定言语的句子一个给定的字符串能否为一个给定言语的句子? ?假设假设不是，它在构造的什么地方出了错？进一步地，这个错不是，它在构造的什么地方出了错？进一步地，这个错误是什么样的错？如何更正？误是什么样的错？如何更正？。v这些问题对有穷言语来说，比较容易处理。这些问题对有穷言语来说，比较容易处理。v这些问题对无穷言语来说，不太容易处理。这些问题对无穷言语来说，不

2、太容易处理。v用文法作为相应言语的有穷描画不仅可以描画出言语用文法作为相应言语的有穷描画不仅可以描画出言语的构造特征，而且还可以产生这个言语的一切句子的构造特征，而且还可以产生这个言语的一切句子文法文法(grammar) (grammar) 文法的方式定义 文法的方式定义 文法例 1CDccd#，CDd#，CD#d，S)。商定商定 推导(derivation)定义定义文法的构造例1 文法的构造例2文法的构造例 3不能用不能用Aan表示表示A可以产生恣意多个可以产生恣意多个a。文法的乔姆斯基体系 文法的乔姆斯基体系 文法的乔姆斯基体系 文法的乔姆斯基体系 文法的乔姆斯基体系 文法的乔姆斯基体系

3、定理 2.1 上下文无关文法概述 上下文无关文法例如 上下文无关文法例如 2.1.1 上下文无关文法的方式化定义上下文无关文法的方式化定义定义定义2.1 2.1 上下文无关文法是一个上下文无关文法是一个4 4元组元组 G=(V, G=(V,R,S),R,S) V: V: 一个有穷集，称为变元集一个有穷集，称为变元集 : : 一个有穷集一个有穷集 (V (V= =) ) ，称为终结符集，称为终结符集 R: R: 有穷规那么集，有穷规那么集， V V (V (V) )* * 规那么是规那么是 左一右多，或一分为多左一右多，或一分为多 S SV : V : 起始变元起始变元文法文法 G G的言语可以

4、表示为的言语可以表示为 L(G): L(G):L(G) = wL(G) = w* * | S | S * * w w 上下文无关文法举例上下文无关文法举例2.1.2 上下文无关文法举例上下文无关文法举例2.1.3 设计上下文无关文法设计上下文无关文法2.1.3 设计上下文无关文法设计上下文无关文法2.1.4 岐义性岐义性假设文法以不同的方式产生同一个字符串，那么称文法假设文法以不同的方式产生同一个字符串，那么称文法歧义地产生这个字符串，假设一个文法歧义地产生某个歧义地产生这个字符串，假设一个文法歧义地产生某个字符串，那么称这个文法是歧义的字符串，那么称这个文法是歧义的2.1.4 岐义性岐义性定

5、义定义2.4 假设字符串假设字符串w在上下文无关文法在上下文无关文法G中有两个以中有两个以上不同的最左派生，那么称上不同的最左派生，那么称G歧义地产生字符串歧义地产生字符串w，假，假设文法设文法G歧义地产生某个字符串，那么称歧义地产生某个字符串，那么称G是歧义的；是歧义的；留意：有时对于一个歧义文法，可以找到一个产生一留意：有时对于一个歧义文法，可以找到一个产生一样言语的非歧义文法，但是，某些上下文无关言语只样言语的非歧义文法，但是，某些上下文无关言语只能用歧义文法产生，这样的言语称为固有歧义的。能用歧义文法产生，这样的言语称为固有歧义的。2.1.5 乔姆斯基范式乔姆斯基范式Chomsky N

6、ormal Form定义定义2.5 2.5 称一个上下文无关文法称一个上下文无关文法 G = (V, G = (V,R,S) ,R,S) 为乔为乔姆斯基范式，假设它的每一个规那么具有如下方式姆斯基范式，假设它的每一个规那么具有如下方式A A BC BC 一分为二一分为二或或A A a a 或终极化或终极化其中，其中， A AV and B,CV and B,CV S, and aV S, and a 2.1.5 乔姆斯基范式乔姆斯基范式Chomsky Normal Form定理定理2.6 2.6 任一上下文无关文法任一上下文无关文法 G = (V, G = (V,R,S) ,R,S) 为言语为

7、言语都可以用一个乔姆斯基范式的上下文无关文法产生都可以用一个乔姆斯基范式的上下文无关文法产生证明思绪：证明思绪：1添加一个新的起始变元添加一个新的起始变元S0； 和规那么和规那么S0S 2思索一切的诸如思索一切的诸如A 规那么；规那么；R uAv, 添加添加R uv；R uAvAw, 添加添加R uvAw; R uAvw; R uvwR A, 添加添加R 3处置一切的单一规那么；处置一切的单一规那么； 4添加新的变元和规那么，把留下的一切规那添加新的变元和规那么，把留下的一切规那么转换成适宜的变元；么转换成适宜的变元； 例例例习题2.2 下推自动机Pushdown Automata有穷自动机的

8、物理模型PDA的物理模型的物理模型例例输入 w = 00100100111100101internal state set Qxyyzxstack当读完W且进入终止态，那么接受w, 栈用来作简单记忆历史对比，只是栈顶元素可见，才干有限，且不灵敏例例非方式化地描画关于言语非方式化地描画关于言语0n1n | n=0的的PDA如何如何任务的：任务的：PDA 的方式化描画的方式化描画输入 w = 00100100111100101内部形状集合内部形状集合State set Qxyyzx栈栈PDA M 读带读带 w且且 作栈操作取决于作栈操作取决于 - 输入输入 wi ,输入字输入字母表母表 - 栈栈

9、sj ,栈字母表栈字母表 - 形状形状 qk Q 形状集合形状集合PDA M: - 调转到一个新的形状调转到一个新的形状, - 推入元素推入元素 (非确定性地非确定性地)PDA的根本构造 下推自动机下推自动机M被定义为被定义为6元组元组 (Q， ， ，q0，F)，这里，这里Q， ， 和和F都是有穷集合，并且：都是有穷集合，并且： Q 是形状集是形状集 是输入字母表是输入字母表 栈字符表栈字符表 q0 Q是起始形状是起始形状 F Q是接受形状集是接受形状集 是形状转移函数是形状转移函数 相当于相当于3种语句种语句goto, push ,pop : Q P (Q )= = 2.2.1 PDA 的方

10、式化定义的方式化定义PDA 的计算过程的计算过程一台下推自动机一台下推自动机M接受输入接受输入w，假设可以把，假设可以把w写成写成w=w1w2wm，这里每一个，这里每一个wi ，并且存在形状，并且存在形状序列序列r0, r1, , rm Q和字符串序列和字符串序列s0, s1, , sm T*满足下述满足下述3个条件，字符串个条件，字符串si是是M在计算的接受分支中的在计算的接受分支中的栈内容序列。栈内容序列。r0 q0 且且s0，对于对于i=0, , m-1，有，有ri+1 ，b (ri， wi+1 ，a)其中其中si=at, si+1=bt, a, b T 和和t T*；rm F例例2.9

11、 : L = 0n1n | n0 背景：背景： 检查左右括号检查左右括号(0,1)能否能否 配对配对 PDA 首先把首先把 “ $ 0n 推入栈推入栈. $ 栈底符号，压箱钱栈底符号，压箱钱 ，表示后来压入栈的，表示后来压入栈的存款用完了。存款用完了。然后，当读到然后，当读到“1n, 0被弹出被弹出. 栈顶对比，左右括号配对，那么同归于尽，栈顶对比，左右括号配对，那么同归于尽，最后最后, 假设假设“$留在栈顶，那么接受留在栈顶，那么接受q1q3q2q4, $, $1, 01, 00, 02.2.2 PDA 举例举例q1读读，栈顶，栈顶变箱底钱变箱底钱 q2遇左括号遇左括号0，压，压0栈入栈入栈

12、栈q1q3q2q4, $, $1, 01, 00, 0弹出压箱钱，栈空弹出压箱钱，栈空 q3 遇右括号遇右括号1，弹出，弹出0，10兑消兑消在在q2遇遇1，弹，弹出出0, 兑消兑消形状图描画形状图描画方式化定义方式化定义接受接受 w = 000111 形状；堆栈的变化过程：形状；堆栈的变化过程：(q1; ) (q2; $) (q2; 0$) (q2; 00$) (q2; 000$) (q3; 00$) (q3; 0$) (q3; $) (q4; ) 终态终态 q4 是个接受态是个接受态形状形状栈内值栈内值 q1q3q2q4, $, $1, 01, 00, 0w = 000111回绝回绝 w =

13、 0101 形状；堆栈的变化过程：形状；堆栈的变化过程：(q1; ) (q2; $) (q2; 0$) (q3; $) (q4; ) 虽然具有输入的部分子串虽然具有输入的部分子串 “01，但找不到整个字，但找不到整个字符串的接受途径符串的接受途径了解为用括号配对比较直观了解为用括号配对比较直观形状形状栈内值栈内值 q1q3q2q4, $, $1, 01, 00, 0w = 0101例：例：构造一台识别下述言语的构造一台识别下述言语的PDA M：aibjck i, j, k0 且且 i=j 或或 i=k例确定的(deterministic)PDA2.2.3与上下文无关文法的等价性与上下文无关文法

14、的等价性定理定理.12: 一个言语是上下文无关的，当且一个言语是上下文无关的，当且仅当存在一台仅当存在一台PDA识别它。识别它。L是是CFL L被被PDA接受接受两步两步: 1)引理引理. 假设一个言语是上下文无关的，那么假设一个言语是上下文无关的，那么存在一台存在一台PDA识别它识别它 部分部分2)引理引理.5 假设一个言语被一台假设一个言语被一台PDA识别，那么识别，那么它是上下文无关的它是上下文无关的 部分部分假设干教材都说假设干教材都说 此定理容易证明此定理容易证明 但又略去证明，此但又略去证明，此定理的证明定理的证明适宜静心自学，不适宜课堂讲解适宜静心自学，不适宜课堂讲解 。 可以先

15、成认结论，可以先成认结论，读第二遍时再深化了解读第二遍时再深化了解引理2.13 的证明P的非方式描画如下：的非方式描画如下：1) 把标志符把标志符$和起始变元放入栈中；和起始变元放入栈中；2反复下述步骤：反复下述步骤：假设栈顶是变元假设栈顶是变元A，那么非确定地选择一个关，那么非确定地选择一个关于于A的规那么，并且把的规那么，并且把A交换成这条规那么右交换成这条规那么右边的字符串；边的字符串；假设栈项是终结符假设栈项是终结符a，那么读输入中的下一个，那么读输入中的下一个符号，并且把它与符号，并且把它与a进展比较。假设它们匹配，进展比较。假设它们匹配，那么反复，假设它们不匹配，那么这个非确定那么

16、反复，假设它们不匹配，那么这个非确定性分支回绝；性分支回绝；假设栈顶是符号假设栈顶是符号$，那么进入接受形状，假设，那么进入接受形状，假设此刻输入已全部读完，那么接受这个输入。此刻输入已全部读完，那么接受这个输入。1初始化栈，把符号初始化栈，把符号$和和S推入栈；推入栈；2 a)栈顶是个变元；令栈顶是个变元；令(qloop, , A)(qloop, w) A w是是R中的一条规那么中的一条规那么 b)栈顶是个终结符。令栈顶是个终结符。令(qloop, a, a) (qloop, ) c)栈顶是空栈标志符栈顶是空栈标志符$。令。令(qloop, , $)(qaccept, ) CFG G 转换成

17、转换成PDA P例：把下述例：把下述CFG G转换成一台转换成一台PDA： SaTb b TTa 引理2.15的证明自学引理2.15 的证明引理2.1 证明3正那么言语与上下文无关言语的关正那么言语与上下文无关言语的关系系Regularlanguagescontext-free languages? 0n1n 2.3 非上下文无关言语非上下文无关言语言语言语 L = anbncn | n0 不是不是CFL证明此事需求新的泵定理言多必反复证明此事需求新的泵定理言多必反复比喻：前后文无关的人格，我行我素，不受言论左比喻：前后文无关的人格，我行我素，不受言论左右，两岸猿声啼不住，轻舟已过万重山，那么

18、某些右，两岸猿声啼不住，轻舟已过万重山，那么某些喜好和行为就会反复喜好和行为就会反复如：如： A * vAy :If S * uAz * uvAyz * uvxyz L, then S * uAz * uvAyz * * uviAyiz * uvixyiz L as well, for all i=0,1,2, 关于上下文无关言语的泵引理的思想：关于上下文无关言语的泵引理的思想： 与与RL不同，不同，CFL 两处打圈，至少一处是两处打圈，至少一处是真圈，真圈，定理定理2.19：假设：假设A是上下文无关言语，那么存在数是上下文无关言语，那么存在数p泵泵长度，使得长度，使得A中任何一个长度不小于中任何一个长度不小于p的字符串的字符串s被划被划分成分成5段段 s=uvxyz 且满足下述条件：且满足下述条件：1) 对于每一个对于每一个I=0，uvixy