admin管理员组文章数量:1596263
(Begin from p37)
Parsing推导一个content free language怎么获得的input太复杂了,需要尝试每一个derivation,就像下图:
为了解决如果input不属于这个languge,那么推导永远也不会停止的problem:
(这里提出一个概念叫:nullable-- 1.如果一个varialbe可以推导出ε,那么他就是nullable的 2. 如果B -> CD,但CD都可以推导出ε,那么B也是nullable的)
1. Remove all ε-productions,方法如下
例:
最后的结果:
2. Removal of unit productions
例:
例:
3. 及时停止如果满足:|derived string| > |input|
例:
Cocke-Younger-Kasami algorithm (CYK) : a faster way to parse
To use CYK algorithm, we should convert CFG to Chomsky Normal Form :
Step 1. Eliminate ε productions
Step 2. Eliminate unit productions
Step 3. Add rules for terminals and split longer sequences of non-terminals
>> Chomsky Normal Form
这个form只允许出现 A → BC / A → a 这两种形式,()转化需要两步:
例:From tutorial 7
Answer:
>> CYK algorithm
Pushdown automata(PDA)
引入了stack,其中右边是notation of PDA,最终stack里是不能留有x的,所以这里每读一个0要push一个x,而每read一个1要pop一个x,为了不能留有x所以控制了read1和0的数量一样的条件:L = { : n ≥ 1}
右边的图:记住左边是pop 右边是push 先push 再pop
这是PDA的定义,其中transition function很重要
例:有点复杂..
CFG ↔ PDA conversions
(End with p92)
本文标签: 笔记
版权声明:本文标题:【COMP218 笔记6】 内容由热心网友自发贡献,该文观点仅代表作者本人, 转载请联系作者并注明出处:https://www.elefans.com/dianzi/1728256921a1151129.html, 本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容,一经查实,本站将立刻删除。
发表评论