计算理论 第2章 上下文无关文法

主要内容 2.1 上下文无关文法概述 2.2 下推自动机 2.3 非上下文无关语言 2.1.1 上下文无关文法的形式化定义 2.1 上下文无关文法概述 2.1.1 上下文无关文法的形式化定义 2.1.2 上下文无关文法举例 2.1.3 设计上下文无关文法 2.1.4 歧义性 2.1.5 乔姆斯基范式 2.2 下推自动机 2.2.1 下推自动机的形式化定义 2.2.2 下推自动机举例 2.2.1 与上下文无关文法的等价性 2.3 非上下文无关语言

描述语言的方法： 有穷自动机 正则表达式 上下文无关文法 (CFG) 概述 A  0A1 A  B B  # 替换规则又称为产生式 变量 (Variables) A, B 终止符 (Terminals) 0,1,# 起始变元 (Start Variable) A 箭头的左侧只有一个变量

如何利用 CFG 产生字符串 (1) 写下起始变元——第一条规则左边的变元。 A  0A1 (2) 取一个已写下的变元，并找到以该变元开始的规则，把这个变元替换成规则右边的字符串。 (3) 重复步骤2，直到写下的字符串没有变元。 A  0A1 A  B A  # 获取一个字符串的替换过程叫派生。 例如字符串 000#111 的过程如下： A  0A1  00A11  000A111  000B111  000#111

如何利用 CFG 产生字符串 可以用语法生成树形象地表示派生过程。 A  0A1 A  B A  # A A A A 1 B 1 1 B 1 1 #

文法的语言 文法 G1 可以产生的字符串包括： A  0A1 #, 0#1, 00#11, 000#111, … A  B 用文法 生成的所有字符串的集合称为文法的语言。 L(G1) 表示文法 G1 产生的语言。 L(G1) = { 0n#1n | n  0 } 用上下文无关文法产生的语言叫上下文无关语言。 文法 G1 的简写： A  0A1 | B B  # A  0A1 A  B A  #

上下文无关文法的形式化定义 上下文无关文法是一个 4 元组 ( V,  , R, S )，且 定义 (4) SV 是起始变元。 定义 2.1

CFG的术语 假设 u 与 v 由变元及终结符构成的字符串，Aw 是文法的一条规则，称 uAv 生成 uwv，记作 uAv  uwv 。 如果 u = v ，或者存在 u1, u2, …, uk, k  0 使得 u u1 u2… uk  v，则称 u 派生 v，记作 u * v。 文法 G = (V,T,R,S)的语言为 L(G) = { wT*| S  w }

上下文无关文法举例 例2.1 考虑文法 G = ( {S}, {a,b}, R, S )，其中规则集 R 为： S  aSb | SS |  。 该文法生成 abab，aaabbb，aababb，… 如果将 a 看作 (，将 b 看作 )， L(G)是所有正常嵌套的括号字符串构成的语言。

设计上下文无关文法 化繁为简，利用正则，考察子串，利用递归。 设计如下语言的上下文无关文法 {0n1n | n  0}∪{1n0n | n  0} {0n1n | n  0} {1n0n | n  0} 设计技巧 化繁为简，利用正则，考察子串，利用递归。

设计上下文无关文法 CFG for L1 = {0n1n | n  0} S  0S1 |  CFG for L1∪L2 S  S1 | S2 S1  0S11 |  S2  1S20 |  CFG for L3 = {02n13n | n  0}? S  00S111 | 

上下文无关文法与正则语言 任何正则语言可以由 CFG 描述。 如果 (qi, a) = qj，则增加规则 Vi  aVj 如果 qi 是接受状态，则增加规则 Vi   如果 q0 是起始状态，则 V0 是起始变元。 q0 q1 1 start DFA G = ( {V0, V1}, {0,1}, R, V0 ) V0  0V0 | 1V1 |  V1  1V1 | 0V0 CFG

最左派生 对于文法 G 中的一个字符串 w 的派生，如果在每一步都是替换左边剩下的变元，则称这个派生是最左派生。 例如G=( {S}, {(,)}, R, S ) ，其中规则为 S  ( S ) | SS |  S  SS  (S)S  ( )S  ( ) ( S ) ( ) ( ) S  SS  S(S)  (S)(S)  ( ) ( S )  ( ) ( )

歧义性 一个串可能有两个甚至更多的最左派生。 例如 CFG G=( {S}, {+,*,a}, R, S) ，其中规则为 S  S + S | S * S | a 产生串 a + a * a S  S + S  a + S  a +S *S  a + a * S  a + a * a S  S *S  S + S * S  a +S * S  a + a * S

歧义性 S S S + S S x S a S x S S + S a a a a a

歧义性 如果字符串 w 在上下文无关文法 G 中有两个或两个以上不同的最左派生，则称 G 歧义地(ambiguously) 产生字符串 w，如果文法 G 歧义地产生某个字符串，则称 G 是歧义的。 某些上下文无关语言只能用歧义文法产生，这样的语言是固有二义的。 定义 2.4

REVIEW(2011-03-14) 广义非确定型有穷自动机(GNFA) GNFA与NFA等价 非正则语言B={ 0n1n | n≥0 } 证明非正则性的技术——泵引理，所有的正则语言都有一种特殊的性质，如果一个语言没有这个性质，则其不是正则的。 若 A 是一个正则语言，则存在一个数 p (泵长度) 使得，如果 s 是 A 中任一长度不小于 p 的字符串，那么 s 可以被分成 3 段，s = xyz，满足下述条件： 对于每一个 i  0, xyiz∈A (2) | y |  0 (3) | xy | ≤ p

REVIEW(2011-03-14) 广义非确定型有穷自动机(GNFA) GNFA与NFA等价 非正则语言B={ 0n1n | n≥0 } 证明非正则性的技术——泵引理，所有的正则语言都有一种特殊的性质，如果一个语言没有这个性质，则其不是正则的。 若 A 是一个正则语言，则存在一个数 p (泵长度) 使得，如果 s 是 A 中任一长度不小于 p 的字符串，那么 s 可以被分成 3 段，s = xyz，满足下述条件： 对于每一个 i  0, xyiz∈A (2) | y |  0 (3) | xy | ≤ p

REVIEW(2011-03-14) 泵引理的证明 泵引理的应用 例：非正则语言B={ 0n1n | n≥0 } 描述语言的方法：自动机——正则表达式——非正则性——上下文无关文法 上下文无关文法 变元、转换规则、终止符、起始变元 上下文无关文法的形式化定义 uAv 生成 uwv，记作 uAv  uwv 。 u 派生 v，记作 u * v。 文法 G = (V,T,R,S)的语言为 L(G) = { wT*| S  w }

REVIEW(2011-03-14) 设计上下文无关文法 任何正则语言可以由 CFG 描述。 如果 (qi, a) = qj，则增加规则 Vi  aVj 如果 qi 是接受状态，则增加规则 Vi   如果 q0 是起始状态，则 V0 是起始变元。 q0 q1 1 start DFA G = ( {V0, V1}, {0,1}, R, V0 ) V0  0V0 | 1V1 |  V1  1V1 | 0V0 CFG

REVIEW(2011-03-14) 最左派生 文法 G 中的一个字符串 w 的派生，如果在每一步都是替换左边剩下的变元。 歧义性 如果字符串 w 在上下文无关文法 G 中有两个或两个以上不同的最左派生，则称 G 歧义地(ambiguously) 产生字符串 w，如果文法 G 歧义地产生某个字符串，则称 G 是歧义的。 乔姆斯基范式

乔姆斯基范式 称一个上下文无关文法是为乔姆斯基范式(Chomsky normal form)，如果它的每一个规则具有如下形式： 定义 2.5 A  BC A  a 其中 a 是任意的终结符，A、B 和 C 是任意的变元，且 B 和 C 不能同时是起始变元。此外，允许规则 S   ，其中 S 是起始变元。 定义 2.5

乔姆斯基范式 任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。 定理 2.6 Step 1: 增加起始变元 S0 和规则 S0  S, 其中S是原来的起始变元。 Step 2: 考虑所有的  规则。 对于 A  , 删去每个A都会产生一个新规则。 例如 R  uAvAw R  uAvw, R  uvAw, R  uvw

乔姆斯基范式 例如： A  B, B  aC, B  CC, 则增加 任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。 定理 2.6 Step 3: 考虑单一产生式A  B。 例如： A  B, B  aC, B  CC, 则增加 A  aC, A  CC 。 Step 4: 考虑A  u1 u2 …uk, 其中 k > 2且ui 是变量或终结符。替换该规则 A  u1A1, A1  u2A2, A2  u3A3, …, Ak-2  uk-1uk

例题 S  ASA | aB A  B | S B  b |  S0  S S  ASA | aB A  B | S

例题 S0  S S0  S S  ASA | aB | a S  ASA | aB A  B | S |  A  B | S After that, we remove B   S0  S S  ASA | aB | a A  B | S |  B  b S0  S S  ASA | aB A  B | S B  b |  Before removing B   After removing B  

例题 S0  S S  ASA | aB | a A  B | S |  B  b S0  S After that, we remove A   S0  S S  ASA | aB | a A  B | S |  B  b S0  S S  ASA | aB | a | SA | AS | S A  B | S B  b Before removing A   After removing A  

例题 S0  ASA | aB | a | S0  S SA | AS S  ASA | aB | a | Then, we remove S  S and S0  S S0  ASA | aB | a | SA | AS S  ASA | aB | a | A  B | S B  b S0  S S  ASA | aB | a | SA | AS A  B | S B  b After removing S  S After removing S0  S

例题 S0  ASA | aB | a | SA | AS S  ASA | aB | a | A  B | S B  b Then, we remove A  B S0  ASA | aB | a | SA | AS S  ASA | aB | a | A  B | S B  b S0  ASA | aB | a | SA | AS S  ASA | aB | a | A  b | S B  b Before removing A  B After removing A  B

例题 S0  ASA | aB | a | S0  ASA | aB | a | SA | AS SA | AS Then, we remove A  S S0  ASA | aB | a | SA | AS S  ASA | aB | a | A  b | ASA | aB | a | SA | AS B  b S0  ASA | aB | a | SA | AS S  ASA | aB | a | A  b | S B  b Before removing A  S After removing A  S

After Step 4 Grammar is in CNF 例题 Then, we apply Step 4 S0  AA1 | UB | a | SA | AS S  AA1 | UB | a | SA | AS A  b | AA1 | UB | a | SA | B  b A1  SA U  a S0  ASA | aB | a | SA | AS S  ASA | aB | a | A  b | ASA | aB | a | SA | AS B  b After Step 4 Grammar is in CNF Before Step 4

主要内容 2.1 上下文无关文法概述 2.2 下推自动机 2.3 非上下文无关语言 2.1.1 上下文无关文法的形式化定义 2.1 上下文无关文法概述 2.1.1 上下文无关文法的形式化定义 2.1.2 上下文无关文法举例 2.1.3 设计上下文无关文法 2.1.4 歧义性 2.1.5 乔姆斯基范式 2.2 下推自动机 2.2.1 下推自动机的形式化定义 2.2.2 下推自动机举例 2.2.1 与上下文无关文法的等价性 2.3 非上下文无关语言

§2.2 下推自动机 下推自动机Pushdown Automata (PDA) 计算模型 §2.2 下推自动机 下推自动机Pushdown Automata (PDA) 计算模型 PDA = NFA + 栈（无限）——在控制器的有限存储量之外提供了附加的存储，使得PDA能够识别某些非正则语言。 能力上与上下文无关文法等价——在证明一个语言是上下文无关的时候有两种选择：可以给出生成他的上下文无关文法，或者给出识别他的PDA。

§2.2 下推自动机 PDA可以把符号写到栈上并在随后读取他 下面介绍识别CFL的自动机——下推自动机。 1．PDA的结构 输入带： §2.2 下推自动机 下面介绍识别CFL的自动机——下推自动机。 1．PDA的结构 有限控制器 a1 a2 a3 ………….. am Z0 Z1 Zn-1 Zn ……. 输入带： 下推栈 图2.1 PDA的结构 输入带： 带上存放被识别的符号串。 有限控制器： 存放PDA的状态转移函数。 下推栈： 后进先出的下推栈。 两个只读头： 分别用来读取带上符号和栈内符号。 PDA可以把符号写到栈上并在随后读取他

§2.2 下推自动机 栈的作用：-体现在可以保存无限的信息量。 例．{0n1n|n≥0} PDA工作过程： §2.2 下推自动机 栈的作用：-体现在可以保存无限的信息量。 例．{0n1n|n≥0} 有限控制器 0 0 0 1 1 ……. 输入带： 下推栈 图2.2 PDA工作过程 PDA工作过程： 读取输入串的符号，每读一个0，把它推入栈，一旦看见1之后，每读一个1，把一个0弹出栈，当栈中的0被清空时恰好读完输入串，则接受这个输入。如果在还有1的时候栈已经变空；或者在栈中还有0的时候1已经读完了；或者0出现在1的后面，则拒绝这个输入。

§2.2.1 下推自动机的形式化定义 1．PDA 与 NFA 相似 区别——栈（栈字母表Γ ） 自动机的核心——转移函数——描述自动机的动作 §2.2.1 下推自动机的形式化定义 1．PDA 与 NFA 相似 区别——栈（栈字母表Γ ） 自动机的核心——转移函数——描述自动机的动作 Σε=Σ ∪ {ε}，Γε = Γ ∪ {ε} ， 转移函数的定义域： Q×Σε ×Γε ——当前状态下，下一个读到的输入符号和栈顶的符号决定了PDA的下一个动作。 转移函数的值域： 需要考虑在特定情形下允许自动机做什么。即，可能进入某个新的状态，并可能在栈顶写入一个符号。 因此为：Q×Γε，考虑非确定性——返回子集，P（ Q×Γε ）

§2.2.1 下推自动机的形式化定义 2．PDA的形式化定义 PDA是一个6元组M=(Q,Σ,Γ,δ, q0, F)，其中 §2.2.1 下推自动机的形式化定义 2．PDA的形式化定义 PDA是一个6元组M=(Q,Σ,Γ,δ, q0, F)，其中 Q——状态的有限集合。 Σ——输入字母表。 Γ——栈字母表。 q0——q0∈Q，开始状态。 F——FQ，终止状态集合。 δ：状态转移函数，Q×Σε ×Γε  P（ Q×Γε ） 。

§2.2.1 下推自动机的形式化定义 有两种状态转移函数： （1）扫描输入带上符号a， §2.2.1 下推自动机的形式化定义 有两种状态转移函数： （1）扫描输入带上符号a， δ(q,a,Z)={(p1,γ1),(p2,γ2),…,(pm,γm)}， 其中 q∈Q，a∈Σ，Z∈Γ，p1,p2,…,pm∈Q, γ1,γ2,…,γm∈Γ*。 此动作表示：在q状态下，当前栈顶符号为Z，读取带上符 号a后，状态改成pi,，并且用γi代替栈顶符号Z(1≤i≤m)， 然后读头右移一个单元，准备读带上下一个符号。 （2）ε-动作，一般用于读带上符号串的开头或者是末尾。 δ(q,ε,Z)={(p1,γ1),( p2,γ2),…,( pm,γm)} 此动作表示：在q状态下，当前栈顶符号为Z ，读取带上符 号ε(实际上没有读符号，或者带上无符号可读)后，状态 改成pi,，并且用γi (1≤i≤m)代替栈顶符号Z，但是 读头不动。

§2.2.1 下推自动机的形式化定义 3．通常使用符号的约定： 注意：假设栈内符号串γ从底到顶依次是ABCD，则γ §2.2.1 下推自动机的形式化定义 注意：假设栈内符号串γ从底到顶依次是ABCD，则γ 要写成 DCBA, 即栈顶符号写在左边，栈底符号写在右边。 3．通常使用符号的约定： 1）用小写英文字母a、b、c…表示输入带上的符号，即 a,b,c,…∈Σ。 2）用小写英文字母x、y、z…表示输入带上带符号串，即 x,y,z,…∈∑*。 3）用大写英文字母A、B、C…表示栈内符号，即 A,B,C,…∈Γ。 4）用希腊字母α、β、γ…表示栈内符号串， 即α,β, γ,…∈Γ*。

§2.2.1 下推自动机的形式化定义 4．PDA计算过程： §2.2.1 下推自动机的形式化定义 4．PDA计算过程： 一个 PDA M = (Q, , , , q0, F) 接受输入串 w，如果 w 可以写成w=w1 w2…wm ，wi ∈, 并且 存在状态序列 r0, r1, …, rm ∈ Q, 和 字符串序列 s0, s1, …, sm ∈ * 满足下述三个条件，字符串 si是M在计算的接受分支中的栈内容序列。 Condition 1: r0 = q0, s0 =  M从起始状态和空栈开始 Condition 2: 对于 i = 0, 1, …, m-1, 有 (ri+1, b)  (ri, wi+1, a), 其中 si = at, si+1 = bt ， a, b ∈ Γε ；t∈ * Condition 3: rm  F M在每一步都完全按照当时的状态，栈顶符号和下一个输入符号进行

§2.2.2 下推自动机举例 例子2.9 0,   0 ,   $ 1, 0   , $   §2.2.2 下推自动机举例 例子2.9 回想一下{0n1n | n  0} ， NFA无法识别，但是PDA可以。 状态图描述 , $   1, 0   0,   0 ,   $ a, b  c 表示机器从输入中读取a时可以用c替换栈顶的符号b。a、b、c中任何一个都可以是  ，如果a是，机器转移而不读取输入中任何符号；若b为，不读栈中任何符号；c为，不在栈中写任何符号。pop b，push c

§2.2.2 下推自动机举例 PDA M的 例子2.9 识别语言{0n1n | n  0}的PDA的形式化定义： §2.2.2 下推自动机举例 例子2.9 识别语言{0n1n | n  0}的PDA的形式化定义： M = ({q1,q2,q3,q4}, {0,1}, {0,$}, , q1, {q1,q4}), PDA M的

§2.2.2 下推自动机举例 例2.10 给出识别下面语言的PDA M2： §2.2.2 下推自动机举例 例2.10 给出识别下面语言的PDA M2： { aibjck | i,j,k  0 and i=j or i=k } How to construct it? 首先,PDA先读 ‘a’ ,并且将其推入栈 push a； 读完a时，机器把它们全部放到栈中，以便能与b或c匹配。由于不知道a是与b匹配还是与c匹配——非确定性

§2.2.2 下推自动机举例 例2.10 给出识别下面语言的PDA M2： §2.2.2 下推自动机举例 例2.10 给出识别下面语言的PDA M2： { aibjck | i,j,k  0 and i=j or i=k } b, a   c,    q1 q3 q4 , $   ,    ,   $ ,    ,    , $   q2 q5 q6 q7 a,   a b,    c, a  

§2.2.2 下推自动机举例 例2.11 给出识别下面语言的PDA M3： { wcwR | w ∈ {0,1}* } wR表示倒写的w。

§2.2.2 下推自动机举例 解：设计的思想是：PDA M 有两个状态，即Q={q1,q2}， §2.2.2 下推自动机举例 解：设计的思想是：PDA M 有两个状态，即Q={q1,q2}， 有三个栈内符号，即Γ＝{R,B,G}。它的动作设想： 1).开始时，PDA M的状态为q1，栈内符号为R。 2).当读c左边的符号时，M是在q1状态，此时 如果读0，则向栈内压入符号B； 如果读1，则向栈内压入符号G。 例如，输入符号串是0101c1010， 读完c左边的0101后，栈内符号串为：GBGB。 3).当读符号c时，状态变成q2。 4).在此状态下之后读c右边的符号： 如果读0，此时栈顶应该是B，则B退栈； 如果读1，此时栈顶应该是G，则G退栈。 0 1 0 1 c 1 0 1 0 入 栈 q1 出 栈 q2

当带上符号串都读完后，栈内为空，就说明带上符号 串正是L中的句子。 M的形式定义如下： 这样，当带上符号都读完时，栈内应该是符号R。再将R清除，使得 栈内为空，进而接收输入带上的符号串。具体动作如下表所示： 栈顶 当前 输 入 符 号 符号 状态 0 1 c  B q1 B入栈，状态为q1 G入栈，状态为q1 状态改成q2 q2 G q1 B入栈，状态为q1 G入栈，状态为q1 状态改成q2 R q1 B入栈，状态为q1 G入栈，状态为q1 状态改成q2 退栈顶，状态为q2 － － － 退栈顶，状态为q2 － 如果带上无符号可读，则退栈顶R，否则，无动作。 表中符号“－”表示无动作。 当带上符号串都读完后，栈内为空，就说明带上符号 串正是L中的句子。 M的形式定义如下：

§2.2.2 下推自动机举例 M的形式定义：M＝({q1,q2},{0,1,c},{R,B,G},δ,q1,R,Φ) §2.2.2 下推自动机举例 M的形式定义：M＝({q1,q2},{0,1,c},{R,B,G},δ,q1,R,Φ) δ：δ(q1,0,R)={(q1,BR)} δ(q1,1,R)={(q1,GR)} δ(q1,0,B)={(q1,BB)} δ(q1,1,B)={(q1,GB)} δ(q1,0,G)={(q1,BG)} δ(q1,1,G)={(q1,GG)} δ(q1,c,R)={(q2,R)} δ(q1,c,B)={(q2,B)} δ(q1,c,G)={(q2,G)} δ(q2,0,B)={(q2,ε)} δ(q2,1,G)={(q2,ε)} δ(q2,ε,R)={(q2,ε)} δ(q2,0,R)=δ(q2,1,R) =δ(q2,c,R)=Φ δ(q2,1,B)=δ(q2,c,B)=Φ δ(q2,0,G)=δ(q2,c,G)=Φ 这里δ(q2,ε,R)={(q2,ε)}的作用是：当读完带上所有 符号时，清除下推栈，使之为空，接收带上符号串。

§2.2.2 下推自动机举例 5．PDA的瞬间描述ID (Instantaneous Description ) §2.2.2 下推自动机举例 5．PDA的瞬间描述ID (Instantaneous Description ) PDA M的当前格局，称之为M的瞬间描述ID。用有序 三元组(q,x,γ)表示瞬间描述ID，其中 q---- q∈Q, M的当前状态， x----x∈∑*, 输入带上还没有被读到的符号串， γ---- γ∈Γ*, 当前栈内符号串。 例如上例中，当带上符号串为0011c1100时， 开始的ID0：（q1,0011c1100,R）， 当读完第一个0后，变成ID1：（q1,011c1100,BR）。 ├ ：表示由一个ID，经过一个动作变成另一个ID时，ID 之间的转变关系。 例如上例中有 ID0├ID1，即 （q1,0011c1100,R）├ （q1, 011c1100,BR）。 ├*：表示经过多个动作后,ID之间的转变关系。

§2.2.2 下推自动机举例 如上例中（q1,0011c1100,R）├（q1, 011c1100,BR）├ §2.2.2 下推自动机举例 如上例中（q1,0011c1100,R）├（q1, 011c1100,BR）├ （q1,11c1100,BBR）├（q1,1c1100,GBBR）├ （q1,c1100,GGBBR）├（q2,1100,GGBBR） 可以写成 (q1,0011c1100,R)├*(q1,1100,GGBBR)。 6．PDA M所接收的语言 PDA M接收语言有两种方式： 1).空栈接收的语言,记作N(M)：令 M=(K,Σ,Γ,δ,q0,Z0, Φ), N(M)={w|w∈∑*,(q0,w,Z0)├* (q,ε,ε), q∈K} 即当M读完带上符号串w后，栈内为空，则接收w 。 上例中M识别0011c1100时，ID的变化过程： (q1,0011c1100,R)├ (q1,011c1100,BR)├ (q1,11c1100,BBR)├ (q1,1c1100,GBBR)├ (q1,c1100,GGBBR)├ (q2,1100,GGBBR)├ (q2,100,GBBR)├ (q2,00,BBR)├ (q2,0,BR)├ (q2,ε,R)├ (q2,ε,ε) 接收0011c1100。

§2.2.2 下推自动机举例 2)．用终止状态接收的语言，记作T(M)：令M=(Q,Σ,Γ,δ,q0, F), §2.2.2 下推自动机举例 2)．用终止状态接收的语言，记作T(M)：令M=(Q,Σ,Γ,δ,q0, F), T(M)={w|w∈∑*,(q0,w,Z0)├* (q,ε,γ), q∈F,γ∈Γ*} 即当M读完带上符号串w后，进入终止状态q，而栈内不 一定为空，则接收输入符号串w 。

§2.2.2 下推自动机举例 例2.12 给出识别下面语言的PDA M： { wwR | w ∈ {0,1}* } §2.2.2 下推自动机举例 例2.12 给出识别下面语言的PDA M： { wwR | w ∈ {0,1}* } wR表示倒写的w。此例与前例不同，前例w与wR之间有一个标志c，而此例的w与wR之间无标志，识别起来就麻烦一些。

§2.2.2 下推自动机举例 解：设计的思想是：PDA M 有两个状态Q={q1,q2}，有三 个栈内符号，即Γ＝{R,B,G}。 §2.2.2 下推自动机举例 解：设计的思想是：PDA M 有两个状态Q={q1,q2}，有三 个栈内符号，即Γ＝{R,B,G}。 它的动作设想： 1．开始时，PDA M的状态为q1 ，栈顶符号为R。 2．⑴ 当读左半边的符号串w时，M是在q1状态，这时 如果读0，则向栈内压入符号B； 如果读1，则向栈内压入符号G。 ⑵ 当读完左半部分符号串w后，状态变成q2, 之后，要 读右半边的符号串wR，这时 如果读0，此时栈顶应该是B，则B退栈； 如果读1，此时栈顶应该是G，则G退栈； 当带上符号都读完时，栈内应该是符号R。

§2.2.2 下推自动机举例 ⑶ 问题是：如何判断w与wR的分界线。我们注意到w的 末尾符号与wR开始符号相同。因此当连续读的两个符号 §2.2.2 下推自动机举例 ⑶ 问题是：如何判断w与wR的分界线。我们注意到w的 末尾符号与wR开始符号相同。因此当连续读的两个符号 相同时，就有两种可能：一种情况是这两个符号都是w中 的符号，此时状态不变；另一种情况是前一个符号是w末 尾的符号，而后一个符号是wR的第一个符号，此时就要 改变状态。 构造PDA M＝({q1,q2},{0,1},{R,B,G},δ,q1,R,Φ) M的动作δ如下： ⑴δ(q1,0,R)={(q1,BR)} ⑵δ(q1,1,R)={(q1,GR)} ⑶δ(q1,0,B)={(q1,BB),(q2,ε)} ⑷δ(q1,1,B)={(q1,GB)} ⑸δ(q1,0,G)={(q1,BG)} ⑹δ(q1,1,G)={(q1,GG),(q2,ε)} ⑺δ(q2,0,B)={(q2,ε)} ⑻δ(q2,1,G)={(q2,ε)} ⑼δ(q2,ε,R)={(q2,ε)} ⑽δ(q1,ε,R)={(q2,ε)} δ(q2,0,R)=δ(q2,1,R)=δ(q2,1,B)=δ(q2,0,G)=Φ

下面看看M识别110011的ID变换过程： 注：符号“┣⑽”表示执行动作⑽得到后面的ID； 符号“┳ ⑵”表示执行动作⑵得到下面的ID。 (q1,110011,R) ┣ ⑽ (q2,110011,ε) ┳ ⑵ (q1,10011,GR) ┣ ⑹ (q2, 0011,R) ┣ ⑼ (q2, 0011,ε) (q1,0011,GGR) ┳ ⑸ (q1,011,BGGR)┣ ⑶ (q2,11,GGR)┣ ⑻ (q2,1,GR) ┳ ⑶ ┳ ⑻ (q1,11,BBGGR) (q2,ε,R) ┳ ⑷ ┳ ⑼ (q1,1,GBBGGR) ┣ ⑹ (q2,ε,BBGGR) (q2,ε,ε) ┳ ⑹ (q1,ε,GGBBGGR)

§2.2.3 PDA与CFG之间的等价性 本节证明PDA与CFG在能力上是等价的，都能够描述上下文无关语言类。下面说明如何把任意一个上下文无关文法转换成能识别相同语言的下推自动机，以及相反。 定理 2.12 一个语言是上下文无关的，当且仅当存在一台下推自动机识别它。 左右: 如果一个语言是上下文无关的，则存在一台下推自动机识别它。 右左: 如果一个语言被一台下推自动机识别，则它是上下文无关的。

§2.2.3 PDA与CFG之间的等价性 Proof: We shall prove by construction. 引理 2.13 如果一个语言是上下文无关的，则存在一台下推自动机识别它。 Proof: We shall prove by construction. PDA的非形式化描述： 将标记符号$及G的开始变元放入栈中 重复下述步骤： 如果栈顶是变元A，则非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串。 如果栈顶是终结符a，则读输入中的下一个符号，并且将其与a比较。如果它们匹配，则重复，如果不匹配，则这个非确定性分支拒绝。 如果栈顶是符号$，则进入接受状态，如果此刻输入已全部读完，则接受这个输入串。 假设L为CFG G产生的语言，我们要说明如何将G转换为一台等价的PDA。

An Example Run Input: 1100 CFG: S  SS | 1S0 | 10 1100 1100 100 S $ 1 $ S $ 1100 1100 100 Next char Next char Next char At the beginning PDA uses the rule S  1S0 Input char is matched

An Example Run (cont.) 100 00 Input: 1100 CFG: S  SS | 1S0 | 10 1 $ $ $ $ $ 100 00 Next char Next char Next char PDA uses the rule S  10 Input char is matched Input char is matched

Whole input string is processed An Example Run (cont.) Input: 1100 CFG: S  SS | 1S0 | 10 $ Next char Next char Whole input string is processed The $ in the top of stack tells PDA the stack is empty. PDA accepts the string

Another Example Run 1100 1100 100 Input: 1100 CFG: S  SS | 1S0 | 10 S $ 1 $ $ 1100 1100 100 Next char Next char Next char At the beginning PDA uses the rule S  10 Input char is matched

Another Example Run (cont.) Input: 1100 CFG: S  SS | 1S0 | 10 $ 100 输入字符与栈顶终结符不匹配，怎么办? It stops exploring this branch of computation Next char

§2.2.3 PDA与CFG之间的等价性 如果一个语言是上下文无关的，则存在一台下推自动机识别它。 引理 2.13 证明：转移函数的缩写记号 机器能够一步把一个字符串写入栈内。同时引入附加的状态，实现每次写入这个字符串的一个符号，从而模拟出一次写入字符串的动作。 证明：转移函数的缩写记号 设q和r是P的状态，a ∈∑ε，s∈ Γε。我们要求P，当读a并且弹出s时，从q到r，并且同时把整个字符串u=u1…ul推入栈。可以如下完成这个动作：引入新的状态q1,…,ql-1, 并且令转移函数 δ（q,a,s）包含(q1,ul) δ（q1, ε, ε）={(q2,ul-1)} … … δ（ql-1, ε, ε）={(r,u1)} 使用记号(r, u) ∈ δ(q, a, s)表示当q是P的状态，a是下一个输入符号以及s是栈顶符号时，PDA P能够读a和弹出s，然后把字符串u推入栈和转移到状态r。

§2.2.3 PDA与CFG之间的等价性 证明： P的状态集Q={qstart，qloop，qaccept} ∪E，E实现上面描述的缩写所需要的状态集合。 δ(q, a, s)= (r, u)表示当q是P的状态，a是下一个输入符号以及s是栈顶符号时，PDA P能够读a和弹出s，然后把字符串u推入栈和转移到状态r 转移函数定义如下：从初始化栈开始，把符号$和S推入栈，实现步骤1的非形式描述： δ（qstart, ε, ε）={(qloop，S$)},然后进行步骤2循环 首先 ，处理情况1,此时，栈顶为一变元。令 δ（qloop, ε, A）={(qloop, w) |A→w是R中的一条规则} 其次，处理情况2，这时栈顶是一个终结符。令 δ（qloop, a, a）={(qloop, ε)} 最后，处理情况3，这时栈顶是空栈标记符。令 δ（qloop, ε, $）={(qaccept, ε)}

Using two dummy states to replace s by xyz at the top of the stack a, b  c 表示机器从输入中读取a时可以用c替换栈顶的符号b。a、b、c中任何一个都可以是  ，如果a是，机器转移而不读取输入中任何符号；若b为，不读栈中任何符号；c为，不在栈中写任何符号。pop b，push c q q a, s  z q1 ,   y a, s  xyz q2 r r ,   x Using two dummy states to replace s by xyz at the top of the stack A shorthand notation

PDA for Proof of (1) start ,   S$ , A  xyz for rule A  xyz qstart shorthand notation used here start ,   S$ , A  xyz for rule A  xyz qloop a, a   for terminal a , $  qaccept

REVIEW(2011-03-16) 乔姆斯基范式 任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。 例子 称一个上下文无关文法是为乔姆斯基范式(Chomsky normal form)，如果它的每一个规则具有如下形式： A  BC A  a 任一上下文无关语言都可以用一个乔姆斯基范式的上下文无关文法产生。 Step 1: 增加起始变元 S0 和规则 S0  S, 其中S是原来的起始变元。 Step 2: 考虑所有的  规则。 对于 A  , 删去每个A都会产生一个新规则。 Step 3: 考虑单一产生式A  B。 Step 4: 考虑A  u1 u2 …uk, 其中 k > 2且ui 是变量或终结符。替换该规则A  u1A1, A1  u2A2, A2  u3A3, …, Ak-2  uk-1uk 例子

REVIEW(2011-03-16) 下推自动机Pushdown Automata (PDA) 计算模型、PDA = NFA + 栈（无限）、能力上与上下文无关文法等价 PDA的结构：输入带、有限控制器、下推栈、两个只读头 PDA的形式化定义： M=(Q,Σ,Γ,δ, q0, F)， Q×Σε ×Γε  P（ Q×Γε ） 两种状态转移函数： δ(q,a,Z)={(p1,γ1),(p2,γ2),…,(pm,γm)}-读头右移一个单元 δ(q,ε,Z)={(p1,γ1),( p2,γ2),…,( pm,γm)}-读头不动

REVIEW(2011-03-16) PDA与CFG之间的等价性 一个语言是上下文无关的，当且仅当存在一台下推自动机识别它。 左右: 如果一个语言是上下文无关的，则存在一台下推自动机识别它。CFG——PDA 右左: 如果一个语言被一台下推自动机识别，则它是上下文无关的。 CFG——PDA ： 将标记符号$及G的开始变元放入栈中 重复下述步骤： 如果栈顶是变元A，则非确定地选择一个关于A的规则，并且把A替换成这条规则右边的字符串。 如果栈顶是终结符a，则读输入中的下一个符号，并且将其与a比较。如果它们匹配，则重复，如果不匹配，则这个非确定性分支拒绝。 如果栈顶是符号$，则进入接受状态，如果此刻输入已全部读完，则接受这个输入串。

REVIEW(2011-03-16) CFG——PDA 转移函数的缩写记号 (r, u) ∈ δ(q, a, s)表示当q是P的状态，a是下一个输入符号以及s是栈顶符号时，PDA P能够读a和弹出s，然后把字符串u推入栈和转移到状态r。 目的：实现CFG规则（如：A→01B10）到PDA 的一步转换，省略了中间状态

start ,   S$ , A  xyz for rule A  xyz a, a   for terminal a qstart shorthand notation used here start ,   S$ , A  xyz for rule A  xyz qloop a, a   for terminal a , $  qaccept

§2.2.3 PDA与CFG之间的等价性 中间状态 例 把下述CFG G转换成一台PDAP1。 2.14 S  aTb | b T  Ta |  中间状态

§2.2.3 PDA与CFG之间的等价性 如果一个语言被一台下推自动机识别，则它是上下文无关的。 引理 2.15 证明思路： 有一台PDA P，要构造一个CFG G，产生P接受的所有字符串。即，如果一个字符串能使P从起始状态转移到接受状态，则G应该产生这个字符串。 设计： 对于P的每一对状态pq，文法有一个变元Apq。产生所有能够把P从p和空栈一块带到q和空栈的字符串。所以不管当前状态时栈内内容是什么，这样的字符串能够保持栈内内容不变，且把P从p状态带到q。

§2.2.3 PDA与CFG之间的等价性 如果一个语言被一台下推自动机识别，则它是上下文无关的。 引理 2.15 为简化工作，对P轻微修改: first and second changes are easy 为简化工作，对P轻微修改: 有唯一的接受状态, qaccept 在接受之前清空栈 每一个转移把一个符号推入栈，或者把一个符号弹出栈，但不同时做这两个动作 使P具有第三个特点，需要： (i) 把同时push和pop的转移替换成两个转移，中间要经过一个新的状态； (ii) 把每一个既不push也不pop的转移，替换成两个转移，先推入任意一个栈符号，再把它弹出

Creating Apq §2.2.3 PDA与CFG之间的等价性 下一步，对P中的每一对状态p, q,建立一个 CFG变量Apq 目标是使Apq 能准确地产生把P从p带到q并且以空栈开始和结束的所有字符串。 How to do so? Creating Apq PDA有两种方法可以从 p (with an empty stack)到q (with an empty stack): (1) 在到达q之前栈变空 这意味着我们从p到某一个r (with empty stack) 然后到达q (2) 在到达q之前栈从不变空 表明在p时，我们push一些字符t进栈，在q时，我们弹出相同的字符t

Creating Apq (cont.) 对每一个p, q, r, 增加规则 Apq  AprArq 对每一个 p, q, r, s ，当(r, t)  (p, a, ) 且 (q, )  (s, b, t), 增加规则 Apq  aArsb 即, 如果我们可以从p到r，并且从r到q，那么我们可以从p到q（这里，所有开始与结束时栈都为空的 即, 如果我们可以从状态p到r，通过读一个字符a并且将t压入栈中，我们可以从状态s到达q，通过读字符b并且从栈中弹出t，那么如果我们开始状态p，栈为空，可以到达q，栈为空，通过读a，从r到s，然后读b获得

Creating Apq (cont.) 对每一个 p, 增加规则 App   如果 Apq 果真可以准确地产生那些串，由P从p到q（栈为空），那么Aqstart, qaccept代表什么? where qstart denotes the start state of PDA

§2.2.3 PDA与CFG之间的等价性 所以, 在我们的文法中，将以所有的规则 Apq 与 Aqstart, qaccept 集合作为变元 剩下的就是证明 Apq 能通过P中准确地产生那些串，从p到q（with empty stacks) 也就是说, 我们需要证明 如果 Apq 产生x, 则x能够把P 从p和空栈带到q 和空栈； 如果 x能够把 P 从p带到到q (with empty stacks), 则Apq 产生 x Exercise: Prove the above two statements (Hint: by induction)

主要内容 2.1 上下文无关文法概述 2.2 下推自动机 2.3 非上下文无关语言 2.1.1 上下文无关文法的形式化定义 2.1 上下文无关文法概述 2.1.1 上下文无关文法的形式化定义 2.1.2 上下文无关文法举例 2.1.3 设计上下文无关文法 2.1.4 歧义性 2.1.5 乔姆斯基范式 2.2 下推自动机 2.2.1 下推自动机的形式化定义 2.2.2 下推自动机举例 2.2.1 与上下文无关文法的等价性 2.3 非上下文无关语言

§2.3 非上下文无关语言 本节提出一项技术，用来证明某些语言不是上下文无关的。在1.4节中介绍了泵引理用来证明某些语言不是正则的，本节提出类似的泵引理，指出每一个上下文无关语言都有一个特殊的值，称为泵长度，使得这个语言中的所有长度等于或大于这个值的字符串都能被“抽取”，这一次抽取的意思要复杂一点，它是指字符串能被划分成5段，其中第2段和第4段可以同时重复任意多次，并且得到的字符串仍然在这个语言中。

§2.3 非上下文无关语言 关于上下文无关的泵引理 如果A是上下文无关语言，则存在数p（泵长度），使得A中任何一个长度不小于p的字符串s都能被划分为5段s = uvxyz且满足下述条件： 1. 对于每一个i  0, uvixyiz ∈A； 2. |vy|  0； 3. |vxy|  p。 定理 2.19

§2.3 非上下文无关语言 s = 证明思路： S R u z x v y 设A是CFL，G是产生A的CFG。要证明A中任何足够长的字符串s都能够被抽取，并且抽取后的字符串仍在A中。 设s是A中一个很长的字符串。由于s在A中，它可以用G派生出来，从而有一棵语法树。由于s很长，s的语法树一定很高，即，这棵语法分析树一定有一条很长的从树根的起始变元到树叶上的终结符的路径。根据鸽巢原理，在这条长路径上一定有某个变元R重复出现。 S R u z x v y s =

§2.3 非上下文无关语言 s = 证明思路： S R u z x v y 这种重复使得我们可以用第一次出现的R下面的子树代替第二次出现的R下面的子树，并且仍得到一颗合法的语法树。由此，可以象图中表示的那样，把s切成5段uvxyz，重复第2段和第4段，得到的字符串仍在A中。即，对任意i≥0， uvixyiz ∈A S R u z x v y s =

uvixyiz is in A for any i  0 Facts: R derives x, R derives vxy Since S derives uRz, and R derives x, S can derive uxz S R u z x S R u z v y x Since S derives uvRyz and R derives vxy, S can derive uvvxyyz

§2.3 非上下文无关语言 证明： 设G是关于CFLA的一个CFG，令b是规则右边符号数的最大值。在G的任意一棵语法树中，一个节点做多有b个儿子，即，离起始变元1步最多有b片树叶；离起始变元不超过2步最多有b2片树叶；离起始变元不超过h步最多有bh片树叶。因此，如果语法树高度不超过h，则它产生的字符串的长度不超过bh。反之，如果一个产生的字符串长度不小于bh+1，则生成它的每个语法树高度至少为h+1. 设G中变元的数目为|V|。令泵长p=b|v|+1>b|v|+1,则A中任一长度不小于p的字符串s的语法树的高度不小于|V|+1. 为说明如何抽取s，设T是s的一颗语法树，如果s有若干语法树，取T是结点数最少的，由于T的高度不小于|V|+1 ，从而至少存在一条路径且其长度不小于|V|+1并包含|V|+2个节点，其中一个节点为终止符，其它为变元。因此该路径上至少有|V|+1个变元，而G只有|V|个变元，故某个变元R在这条路径上不只出现1次，选取R为这条路径上在最下面的|V|+1个变元中重复出现的变元。

§2.3 非上下文无关语言 下面证明 |vy|  0 与 |vxy|  p 为了证明这两个条件，进一步进行限制: (1) 假设这棵生成树是可以产生字符串s中最小的 (2) R 为最长的从根到叶子的路径，并且最靠近 |V|+1的变元

|vy|  0 |vxy|  p 假设 |vy| = 0  Both v 与 y 为空串 则在生成树中， “产生 vxy 的子树R ” 由 “产生的x子树R替换” 结果生成树将产生s, 但是具有更少的节点  矛盾 |vxy|  p R 在最长路径中，最靠近 |V| + 1 的变元 产生vxy的子树R，其高度最多为 |V|+1  即最多有 b|V|+1 个叶子  因此, vxy 最多有 p 个字符 (as p = b|V|+1)

§2.3 非上下文无关语言 判定某个语言L不是CFL 【例2-20】 证明L={aibici|i≥1}不是CFL。 证明：假设L是CFL。设n是L满足CFL泵作用引理的常数。取 z=anbncn,|z|=3n＞n,于是根据泵作用引理，可将z写成 z=uvwxy形式，其中|vx|≥1,|vwx|≤n,且对任何i≥0,有 uviwxiy∈L。下面分五种情况讨论，看看如何选取v和x。

(1) vx中不可能包含符号a和c，因z中最右边的a与最左 边的c中间有n个b，受|vwx|≤n限制，故不能出现此情况。 (2) 如果v和x中只有符号a，取i=0，uviwxiy＝uwy, 因为 |vx|≥1,所以uwy中a的个数要少于b的个数，所以uwyL， 这与i≥0,有uviwxiy∈L矛盾。 (3) 如果v和x中只有符号b或者只有符号c，类似可以推 出矛盾。 (4) 如果vx中含有符号a和b，取i=0，uviwxiy＝uwy, 因 为|vx|≥1,所以uwy中a和b的个数要少于C的个数，所以 uwyL，这与i≥0,有uviwxiy∈L矛盾。 (5) 如果vx中含有符号b和c，取i=0，uviwxiy＝uwy, 因 为|vx|≥1,所以uwy中b和c的个数要少于a的个数，所以 可见，不论v和x取什么样的符号串，都产生矛盾。 所以L不是CFL。

§2.3 非上下文无关语言 例2.21: The language B = {aibjck | 0  i  j  k} is not a context-free language. 例2.22: The language C = {ww | w in {0,1}*} is not a context-free language.

RL与CFL关系 {ww} Set of Languages (= set of “set of strings”) {0n1n2n} {w with even |w|} {w | w = wR} {0x1y} {0n1n} Set of Regular Language Set of Context-Free Language

作业 2.3、2.6、2.7、2.10、2.23、2.35