Skip to content

2 上下文无关语言

CFG

courses.grainger.illinois.edu/cs373/fa2010/lectures/notes21.pdf

上下文无关文法 Context-Free Grammar (CFG) 一些递归地生成字符串的规则

Example

\(L=\set{a^nb^n}\):
- \(e\in L\)
- 递归 \(w\in L\to awb\in L\)

\(L=\set{w\in \set{a,b}^*,ab个数相等}\):
- \(e\in L\),
- 如果\(w\in L,awb,bwa\in L\)
- 如果\(w,v\in L\) 则\(wv\in L\)

CFG的定义

形式化定义 \(G=(V,\Sigma,S,R)\)

  • \(V\)是字母表(除了a,b等字符(一般用小写), 还有表示抽象的串的字符(一般用大写))
  • \(\Sigma\subseteq V\) 终结符号(terminal)
    • \(V-\Sigma\) 非终结符号(nonterminal)
  • \(S\subseteq (V-\Sigma)\) 起始符号
  • \(R\subseteq (V-\Sigma)\times V^*\) 规则(有限个) \(V^*\)相当于用抽象的串和字符组合得到的新串。

推导(Derivation): \(xAy\Rightarrow_G xuy\) 当\((A,u)\in R\) (derive in one step)。 注意和自动机的格局不同, 是从S出发,推到具体的字符串w

\(G\) 生成 \(w \in \Sigma^*\) if \(S \Rightarrow_G^* w\) (注意w是由终结符号构成的串)

\(L(G)\) 是所有G可以生成的字符串的集合

Example

\(L=\set{w\in \set{a,b}^*,ab个数相等}\) 对应CFG: \(V=\set{a,b,S}\), \(\Sigma=\set{a,b},S=S, R=\set{S\to e|aSb|bSa|SS}\)

Parse Tree

Example

合法括号序列对应的CFG
\(S\to SS| (S) | e\)

定义一棵parse tree

  • 内部节点是非终结符号
  • 叶子节点是终结符号或者e

所有叶子节点连接成的串称为yield of the parse tree

ambiguity:

inheriently ambiguous

CNF

A CFG is in ChomskyNormal Form \(S\)是开始符号, \(A\in V-\Sigma,B,C\in V-\Sigma-\{S\}\) 1. \(S\to e\) 2. \(A \to BC\)
3. \(A\to a\)

G是CNF, G生成长度为\(n\geq 1\)的字符串,那么推导次数(length of derivation)\(=2n-1\)

证明: 生成长度为n的字符串的n个字符,需要用n次规则3, 需要n个非终结符号。而1不增加非终结符号, 2会增加1个,从1个起始符号S开始，需要用n-1次规则2。所以总共用了2n-1次

每个CFG都可以转化成等价CNF形式

  1. \(?\to S\). 新建起始符号\(S_0\), 规则\(S_0\to S\)
  2. \(A\to e,A\neq S\). 对于右边有A的规则, 加入去掉一个A的新规则
  3. \(A\to B,B\in V-\Sigma\) 删除这条规则,且所有B在左边的规则, 都要将B改成A
  4. \(A\to u_1u_2u_3\) 新建非终结符号 \(A\to u_1V,V\to u_2u_3\)
  5. \(A\to u_1u_2,u_2\in\Sigma\) 新建非终结符号\(V,A\to u_1V,V\to u_2\)

CFL的性质&常见的CFL

Warning

CFL在并 , 连接和Kleene star下封闭。在交、补下不封闭

证明:

  • 并: 增加起始符号S, \(S\to S_1,S\to S_2\)
  • 连接: 同理增加起始符号\(S,S\to S_1S_2\)
  • Kleene star: \(S\to e,S\to SS_1\)

Warning

正则语言和CFL的交是CFL 推论 \(R\)是正则语言, \(L\)是CFL 那么\(L-R=L\cap \bar{R}\) 是CFL. 但是\(R-L\)不一定。 因为\(\bar{R}\)一定是RL 但\(\bar{L}\)不一定是CFL

证明: 构造自动机

Warning

(a) 的话,不妨考虑nm两种情况。然后n<m可以看成\(a^nb^n\)和\(b^{n-m}\)连接 (b) 构造正则，其中\(\Sigma=\set{a,b}\)

(2) 问 假设pumping length是p 那么vy肯定不能有a跟c(不然a,c不相等) 只能在b里面 \(vy=b^k(k\leq p)\) \(v^iy^i=b^{ki}\) 取一个合适的i,一定能凑出数量相等？

Pushdown Automata(PDA)

思路: 给NFA加一个栈 类比用栈判断合法括号序列?

PDA的定义

\(P=(K,\Sigma,\Gamma,\Delta,s,F)\)

  • \(\Gamma\) 栈里面出现的符号集合
    • \(\Delta\) 转移关系 \((K\times(\Sigma \cup \set{e})\times \Gamma^*) \to (K\times \Gamma^*)\)

\((p,x,\alpha)\vdash (q,y,\beta)\) \(((p,a,\gamma),(q,\eta))\in \Delta\) \(x=ay,\alpha=\gamma\tau,\beta=\eta\tau\) 意思是,读取字符串字符\(a\), pop了字符串\(\gamma\), push了字符串\(\eta\) \((p,a,e),(q,\beta)\) 表示无条件往栈push \(\beta\)

格局\((q,w,s)\) w是还没读取的字符串 s是当前栈的状态

Example

构造PDA \(C_0(w)=C_1(w),w\in \set{0,1}^*\)

\(K=(s,q,f),\Sigma=\set{0,1},\Gamma=\set{0,1,S}\) S或 $ 符号表示栈底

\[ \begin{aligned} &((s,e,e),(q,S)) 先放栈底标记\\ &((q,0,0),(q,00)) 如果当前是0,栈顶也是0,那就先pop1个0,push 2个0\\ &((q,0,S),(q,0S)) 如果是空栈,就push一个0 \\ &((q,0,1),(q,e)) 0,1抵消 \\ &a=1的情况同理 \\ &((q,e,S),(f,e)) 只有栈底标记,说明完美匹配\\ \end{aligned} \]

能否不用栈底的标记字符？ 利用NFA可以"猜测"转移的特性

\(K=\set{s},\Sigma=\set{0,1},\Gamma=\set{0,1}\) \((s,0,1),(s,e)\) 对应抵消 \((s,0,e),(s,0)\) 对应只放0 \((s,1,0),(s,e)\) \((s,1,e),(s,1)\)

CFG转PDA

Each CFL is accepted by some PDA

\(G=(V,\Sigma,S,R),P=(K,\Sigma,\Gamma,\Delta,s,F)\)

\(K=(p,q),s=p,F=\set{q},\Gamma=V\) \(((p,e,e),(q,S)\): 起始时有S \(((q,a,a),(q,e)),\forall a \in \Sigma\) 如果栈顶终结符号,就无条件pop出来 \(((q,e,A),(q,x)),\forall (A,x) \in R\) 所有CFG的规则

PDA转CFG

a simple PDA:

\(((q,a,\beta),(p,\gamma))\in \Delta\)

\(P=(K,\Sigma,\Gamma,\Delta,s,F),G=(V,\Sigma,S,R)\)

Not CFL

泵定理

Pumping Theorem

如果G是CFG, 存在整数n, 对任意字符串\(w \in L(G)\) \(|w|\geq n\), 可以写成\(w=uvxyz\) 满足以下条件 - \(|vy| \geq 1\) - \(|vxy|\leq n\) - \(uv^nxy^nz\in L(G)\)

常见的非CFL

Example

\(L=\set{www|w\in \set{a,b}^*}\) 不是CFL

formal languages - Use the pumping lemma to prove that {www} is not context-free - Computer Science Stack Exchange

pumping length p 考虑\(a^pba^pba^pba^p\) \(|vxy|\leq p\), 滑动过去。 \(v,y\)不能包含b,那么只能\(x=b,vy=a^l(l\leq n)\) 然后条件3的时候必然导致a的数量不平衡

Example

同理，涉及>2个的计数、比较的，因为栈做不到 - \(a^nb^nc^n\) 不是CFL - 但是它的补集是CFL - \(a^ib^jc^k(i>j>k)\) 不是CFL - \(w\)中\(a,b,c\)个数相等 - 但是它的补集 是CFL 因为写成3个情况的并

无法线性比较的 - \(a^{n^2}\) - \(a^p\) \(p\)是质数

需要用到非栈顶信息的 - \(ww\) - \(a^mb^nc^md^n\)

构造问题总结

第一种: 明显分成2段的

这种先构造CFG,再构造PDA比较好做

\(a^nb^m,n\geq m\)

CFG: \(S\to aSb|aS|e\)

Example

答案: (b)题 第一个状态添加1个a或2个a 第二个状态用一个b去消掉a 分两个状态, 是为了确保前面都是a, 后面都是b, 不存在先输入了b,又输入a的情况 。 和a,b个数2倍做法不同。

第二种: 字符个数关系

这种尽量直接构造PDA

a的个数和b个数相同

PDA: \(K=\{q\},\Gamma=\set{a,b}\) \(\delta:\) \((q,a,e),(q,a)\) \((q,b,e),(q,b)\) (前两步是push) \((q,a,b),(q,e)\) \((q,b,a),(q,e)\) (对应相消)

CFG: \(S\to e| SS | aSb | bSa\)

b的个数是a的两倍

PDA: 因为栈只能比较相等，我们把1个a转化成2个A. b转化成B. 然后让A和B相互抵消。

\((q,a,e),(q,AA)\) \((q,b,e),(q,B)\)

\((q,a,BB),(q,e)\) 1个a和2个B抵消 \((q,b,A),(q,e)\) 1个b和1个A抵消 \((q,a,B),(q,A)\) 如果B不够2个, 1个a相当于2个A, 消掉一个B(出栈)后,还剩1个A(入栈)

Comments