计算理论导引第二章
第二章
·上下文无关法
··替换规则
A->0A1
\(G_1\){A->B
B->#
用局部变化规律和初始条件描述一个过程
派生:获取一个字符串的替换序列成为派生
由CFG生成的语言是CFL
上下文无关法是一个四元组(V,Σ,R,S)
变元集,终结符集,规则集,起始变元
··设计上下文无关文法
···四步
···歧义性
定义一种以固定次序替换变元的派生类型。如果在每一步
都是替换剩下的最左边的变元,则称这个派生是最左派生。
如果字符串 𝑤 在上下文无关文法 G 中有两个或两个以上
不同的最左派生,则称在 G 中歧义地产生字符串 𝑤 。如 果文法 G
歧义地产生某个字符串,则称 G 是歧义的。
··乔姆斯基范式
规则如下:
A->BC
A->a
*BC不能是起始变元,允许S->𝜀(S是起始变元)
~~任一 CFL 都可以用乔姆斯基范式的 CFG 产生。
~~=>(ppt_24)
加头(添加新的起始变元\(S_0\)保证起始变元不出现在右端) ...
!站长推荐!BASS!地狱系列の教程
b8e8037bdf9e341b3d470259692eeb5c1859211900a669d4c003b7723c641b0c1d0c44f5ffabab0eb4527a8d3126c14fc375ce32e845689ac75ccdf1bc688886a9de3df92baa8ed4d554ddba433bd3786807d27b9e65a6e5e24867e65d02d017585d39d84259005a22675153398d295f531a3a3b6d923dbef93ba60861b18ee5919462ce2be313f7500c212a0b7a48dbbff0bb0fed9180ff4de247f7fa0a0b9ba0eeb1ec06186770f16eccb13df858a0ef64042d79340bdcd90b85e3d844d4525d8b06e6e77aa65ca50e21e37157c7ab0228438af50ff324f5695fd26f5860d2cceae95bd6d398d4b6d2004e0a2ca527173cc284e5a657b55 ...
Hello World
Welcome to Hexo! This is your very
first post. Check documentation for
more info. If you get any problems when using Hexo, you can find the
answer in troubleshooting or
you can ask me on GitHub.
Quick Start
Create a new post
1$ hexo new "My New Post"
More info: Writing
Run server
1$ hexo server
More info: Server
Generate static files
1$ hexo generate
More info: Generating
Deploy to remote sites
1$ hexo deploy
More info: Deployment