LearnLog

学习Automata PPT的记录. 相关笔记会另开博客记录. 也可能不会开.

  • 介绍了CFG以及CFL.
  • CFG有相关的下推语法以及parse树的概念, 同时它们是等价的;
  • CFG可以进行进一步地形式化, 从而成为CNF. 包括消除无用变量, 消除空字符, 消除unit production等

引入

  • 有的语言RE是无法表述的, 例如回文语言(可以通过泵引理来证明)
  • 我们引入CFG来描述这一类语言.
  • CFL更加powerful, 但是依然无法描述所有语言.

Formalism

可以由一个四元组来描述

CFG=<T,V,S,P>CFG = <T, V, S, P>

  • Terminals: 相当于符号表
  • Variables = nonterminals: 一个符号的有限集合, 每一个表示了一个语言
  • Start symbol: 第一个被定义的variable
  • productions: head -> body. 描述了变量之间的依赖关系.

Derivations

derive: 从起始符号开始, 不断替换某个变量, 直到只剩下终止符号.
符号: =>: 表示一次替换. =>*: 表示任意次替换

sentential form: 可以从起始符推导得到的符号 / 变量

CFL: The Language of a CFG, is {w∣S=>∗w}\{w | S =>^* w\}

某些语言是CFL, 但不是RL; 有些语言不是CFL(例如, 0n1n2n0^n1^n2^n)

Notation

BNF Notation:
Varialbes 写在 <...>中; Terminals用粗体或下划线标明.
用 ::=来指代 ->, 用 |来指代 or.
用 ...来表示"一个或多个" (翻译: A -> S|SA)
用 [...]来表示"可选" (翻译: A -> S|epsilon)

Leftmost / Rightmost Derivations

Derivation 有很多种进行的方法.
为了获得某种统一的过程, 我们定义lm / rm 的过程.
(lm要求: 进行替换时, 变量的左边全部为终止符)

因此相应地也可以递归定义: =>_lm和 =>*_lm.

当然, 就算限制了LM / RM, 从一个起始符S出发的生成方式也不止一种, 因为production的选取往往是不确定的

Parse Trees

Parse trees: tress labeled by symbos of a CFG. 加了标签的树
Leaves: 标签为终止符或空字符串.
Interior nodes: 标签为变量.
Root: 标签为起始符
树的父子关系符合 production 的限制
yield: 将叶子上的终止符汇合起来得到的终止符的串

等价性

我们证明Parse Trees和LM, RM Derivations 是等价的.
证明: 从双箭头的两个方向分别出发.

  • 从树的高度进行归纳证明: 假设树的高度为 h
  • 从LM Derivation 的长度进行归纳证明: 假设进行了 k步的 => lm. 于是从第一步A=>lm X1 X2 ... Xk开始, 从左到右分别考虑即可.

同时, 我们也可以证明, 对于某个给定的 LM Derivation 过程, 不一定要严格按照LM的方式来构建Parse 树

Ambiguous

一个CFG是 ambiguous的, 如果存在一个 string , 它是至少两颗Parse树的yield

等价性

两个不同的LM过程会到处两颗不同的树; 同时, 两颗不同的树也会导出两个不同的LM过程

RM是同理的

因此, 对于某个string, 下面三句话等价

  1. 它有不同的LM过程
  2. 它有不同的RM过程
  3. 它有不同的Parse Tree

Ambiguity是语法的性质, 而不是语言的性质: 同样的语言可以用两个不同的CFG来表示, 有点CFG会具有 ambiguity, 有的则没有

LL(1)

对于某些语法, 我们可以选出需要用的production, 只需要从左到右地扫描并且读入下一个symbol:

  1. 从给定的string和起始符S出发
  2. 不断地进行=>lm过程. 过程中选定的production通过扫描string的字符得到.
  3. 进行到底, 直到遇到终止符. 由于=>*lm过程确定, 因此对应的Parse Tree 也确定.
  4. Leftmost derivation, left-to-right scan, one symbol of lookahead.

Inherent Ambiguity 固有歧义

某些特定的CFL具备天然歧义性, 这意味这它的所有CFG都具有歧义.

Example: {0i1j2k∣i=j or j=k}\{0^i1^j2^k| i = j \text{ or } j = k\}
此时, 我们发现, 对于 0n1n2n0^n1^n2^n, 我们总有两种生成方式: 检查前两个, 或检查后两个.

Normal Forms for CFG’s - CNF

对于某些CFG, 它什么也推导不出来(对应的CFL为空. )

即, 不存在这样的 w, 使得 S =>* w.

Discovery Algorithms:

  1. basis: start from some facts that are obvious
  2. induction: discover more facts from what already have discovered
  3. Eventually, nothing more can be discovered, and we are done.

利用上面的思想, 我们可以推导出CFG对应的CFL.

  1. biasis: 对于变量A, A能够导出一个终止符串, 如果存在 A -> w
  2. induction: A能够导出一个终止符串, 如果有A -> Bw, 且B能够导出终止符串.
  3. 可以证明, 这个算法发现的所有可终止变量都是真的, 且能够发现所有可能的可终止变量
  4. 通过Parse Tree的高度证明.

类似的, 我们也可以设计一个算法, 用于找到所有的"Unreachable Symbols"
(从起始符出发, 做类似BFS的算法. )

可以将CFG看作一个有向图, 其中边由production 生成.

因此, 我们可以将所有的unreachable grammar 以及相应的productions移除.

Useless Symbols(总会包含在从起始符出发的某个Derive当中):

  1. 移除所有的Symbols that derive no terminal string; (只剩下可以导出strings的符号)
  2. 移除所有的 Unreachable Symbols (只剩下从起始符出发, 能够导出strings的符号)

TH: 对于CFL L, L−{ϵ}L - \{\epsilon \} 有一个不包含 ϵ\epsilon-production 的CFG

换言之, 如果一个CFG不包含 ϵ\epsilon-production, 那么它对应的语言集合中不可能有 ϵ\epsilon. (这一点是比较直观的. )

因此, 我们几乎可以移除所有的 A -> epsilon :

  1. 将所有最终能够导出空符号的symbols(nullable symbols)找到. (递归的算法)
  2. 对于那些包含 nullable symbols的production, 将它们化为一族 productions (例如对于空符号 X1 X2 以及过程 A -> X1 X2, 将它化为幂集的形式 A -> X1 X2 | X1 | X2). 然后, 删去所有类似 A -> epsilon的式子
  3. 对得到的结果, 移除那些Useless Symbols.
  4. 于是, 我们得到的production中就不包含 ϵ\epsilon了

Prove:
对于任意变量A

  1. 如果 w \enq \epsilon, 且 A=>old∗wA =>^*_{old} w, 则 A=>new∗wA =>^*_{new} w
  2. 如果 A=>new∗wA =>^*_{new} w, 则w \enq \epsilon, 且 A=>old∗wA =>^*_{old} w

然后, 令A作为起始符号, 即可证明 L(new)=L(old)−{ϵ}L(new) = L(old) - \{\epsilon\}

证明过程: 同样是对于derivation的步数作归纳证明.

unit production: body部分只包含一个变量的production
这些productions可以被消除.

步骤:

  1. 首先, 递归地找出所有"等价符号"
  2. 对于所有等价符号, 将他们的非 productions 进行共享. (这个共享的传递过程是有向的)
  3. 将所有的unit productions 丢弃.

Cleaning Up a Grammar

TH: if L is a CFL, then there is a CFG for L−{ϵ}L-\{\epsilon\} that has:

  1. No useless symbols (不包含"不可达"和"不可生成终结式"的符号)
  2. No ϵ\epsilon- productions
  3. No unit productions
    因此, 所有productions的body要么是终止符, 要么长度至少为2

Prove: 构造性地完成:
对于一个CFG的L

  1. Eliminate ϵ\epsilon- productions
  2. Eliminate unit productions
  3. Eliminate variables that derive no terminal string
  4. Eliminate variables not reached from the start symbol

注意次序. 消除epsilon的时候可能会产生unit, 所以必须先做; 后两步不会生成epsilon / unit 所以后做.

CNF (Chomsky Normal Form)

CNF:
特殊的CFG, 满足: 对于每个production, 要么 A -> BC, 要么 A -> a

只能为"两个"变量. 可以通过引入新变量的方法, 将一般的形式转化成CNF.

TH: if L is a CFL, then there is a CFG in CNF for L−{ϵ}L-\{\epsilon\} that has:
证明:

  1. clear up the CFG.
  2. 对于每个终止符, 创建一个变量用于"指代"它
  3. 对于所有production, 将其化为长度为2的形式. (长度为k的生成式化为k-1个长度为2的生成式)

对于CNF: 它的语法形式更加形式化, 同时推导过程更加形式化.

backtop