计算理论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 | n0}
Algol, Pascal ,C ,…,都是CFL, 人类语言太丰富,是CSL,辩论中断章取义是诡辩,当作CFL处理
General idea: CFLs are languages that canbe recognized by automata that have onesingle stack:
{ 0n1n | n0} is a CFL
{ 0n1n0n | n0} is not a CFL
2017/7/23
4
Context-Free Languages (Ch. 2)前后文无关语言
Context-free languages allow us to describe nonregular languages like { 0n1n | n0}
Algol, Pascal ,C ,…,都是CFL, 人类语言太丰富,是CSL,辩论中断章取义是诡辩,当作CFL处理
General idea: CFLs are languages that canbe recognized by automata that have onesingle stack:
自动机加堆栈(或允许栈结构的C程序可识别)
{ 0n1n | n0} is a CFL
{ 0n1n0n | n0} 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 toS 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转载请标明出处.