下载此文档

计算理论03 CFL.ppt


文档分类:金融/股票/期货 | 页数:约38页 举报非法文档有奖
1/38
下载提示
  • 1.该资料是网友上传的,本站提供全文预览,预览什么样,下载就什么样。
  • 2.下载该文档所得收入归上传者、原创者。
  • 3.下载的文档,不会出现我们的网址水印。
1/38 下载此文档
文档列表 文档介绍
计算理论03_CFL第三讲课程
§
Context-Free Languages (CFL)
Context-Free Grammars (CFG)
Chomsky Normal Form of CFG
RL  CFL
2017/7/23
1
用前后文相关(CSL) 的来反衬托CFL直观概念
P=“Capital of china”如何翻译?
中国的首都或瓷都
有歧义
用前后文信息排歧
X China y  x中国y
U China v  u 瓷器 v ,
比较复杂,以后讨论,今天讨论CFL
2017/7/23
2
前后文无关的直观概念
括号配对 XML(扩展标识语言)中mark 配对
( ( ) ( (( ))) ( ) )

扫描,与左边括号压栈 push ,与右边括号弹栈,
空栈开始。扫描完,栈空, 则配对正确。与前后文无关
只管局部行为
(
(
(
(
2017/7/23
3
Context-Free Languages (Ch. 2) 前后文无关语言
Context-free languages allow us to describe nonregular languages like { 0n1n | n0}
Algol, Pascal ,C ,…,都是CFL, 人类语言太丰富,是CSL,辩论中断章取义是诡辩,当作CFL处理
General idea: CFLs are languages that can be recognized by automata that have one single stack:
{ 0n1n | n0} is a CFL
{ 0n1n0n | n0} is not a CFL
2017/7/23
4
Context-Free Languages (Ch. 2) 前后文无关语言
Context-free languages allow us to describe nonregular languages like { 0n1n | n0}
Algol, Pascal ,C ,…,都是CFL, 人类语言太丰富,是CSL,辩论中断章取义是诡辩,当作CFL处理
General idea: CFLs are languages that can be recognized by automata that have one single stack:
自动机加堆栈(或允许栈结构的C程序可识别)
{ 0n1n | n0} is a CFL
{ 0n1n0n | n0} is not a CFL(要更多的资源)
2017/7/23
5
Context-Free Grammars (Inf.) 前后文无关文法与ep92 例类似,但稍简单
Which simple machine produces the nonregular language { 0n1n | n  N }?
Start symbol S with rewrite rules:
1) S  0S1 //s从左右两边不断长出不对称的翅膀
2) S “stop”
S yields 0n1n according to S  0S1  00S11 … 0nS1n  0n1n
长翅膀的规则与前后文无关,只管自己长,
比较简单,当然描述能力也比较有限
2017/7/23
6
Context-Free Grammars () ep94
形式化定义,学****元组式定义的方法
A context free grammar G=(V,,R,S) is defined by
V: a finite set variables
: finite set terminals (with V=) //终极符, 字母
R: finite set of substitution rules V (V)*
规则是左一右多, 或一分为多
S: start symbol V //开始符号,句子sentence
The language of grammar G is denoted by L(G):
L(G) = { w* | S * w }
2017/7/23
7
Context-Free Grammars () ep94
思想:
用局部变化规律和初始条件描述一个过程
如微分方程+初始条件描述热传递,弦震动
等等非量子过程
利息 y’=ky , y(0)=2.
dy/y=k dx , 两边积分 ln(y)=kx +c1
y=cekx , 由初始条

计算理论03 CFL 来自淘豆网www.taodocs.com转载请标明出处.