返回信息流最近看了Chomsky对文法的定义。但我一直对一个概念不是很清楚。
上下文无关的定义：
A := w, A是一个非终结符，w是终结符和非终结符的闭包。
上下文相关的定义：
yAz := ywz, A是一个非终结符，y和z是终结符和非终结符的正闭包，w是终结符和非终结符的闭包。
原来我一直觉得上下文有关和上下文无关的差别在于：在上下文有关的文法中若A要推导出w，那一定是要在y和z中间。但是我才发现y和z都可以是空字符。
那这个上下文相关主要体现在什么地方呢？
还请大虾指教哈。
这是一条镜像帖。来源：北邮人论坛 / soft-design / #23191同步于 2007/12/18
该镜像源已超过 30 天没有更新，可能在源站已被删除。
SoftDesign机器人发帖
[求助]上下文无关和上下文相关的语法差别在哪呢？
hman
2007/12/18镜像同步8 回复
订阅后，新回复会通过你的通知中心匿名送达。
8 条回复
【 在 hman (Richard) 的大作中提到: 】
: 最近看了Chomsky对文法的定义。但我一直对一个概念不是很清楚。
: 上下文无关的定义：
: A := w, A是一个非终结符，w是终结符和非终结符的闭包。
: 上下文相关的定义：
: yAz := ywz, A是一个非终结符，y和z是终结符和非终结符的正闭包，w是终结符和非终结符的闭包。
: 原来我一直觉得上下文有关和上下文无关的差别在于：在上下文有关的文法中若A要推导出w，那一定是要在y和z中间。但是我才发现y和z都可以是空字符。
哪里说的？都可以是空字符？
: 那这个上下文相关主要体现在什么地方呢？
: 还请大虾指教哈。
我也不知道
我只是问下出处而已
自动机课本啊？
都忘记了，虽然自动机那课有90分
【 在 hman (Richard) 的大作中提到: 】
: 我从图书馆借的一本书上写的
: 叫 形式语言与自动机。
: 难道这书有问题？
: ...................
我早就忘光了。。。= =
【 在 NWN2 的大作中提到: 】
: 我也不知道
: 我只是问下出处而已
: 自动机课本啊？
: ...................
【 在 hman 的大作中提到: 】
: 没人 理哈？
很明显，从你说的定义可以看出来上下文相关文法包括了上下文无关文法。准确地来说应该是，除了空串以外的上下文无关文法是上下文相关文法的一个子集。书找不着了，记得好象是这样的.....
我觉得要理解这个东西，最好从它们所对应的机器模型来理解。Chomsky对文法的定义,3型文法正规文法的描述能力最差，对应的是有限状态机； 2型文法上下文无关文法包括了3型文法，对应了下推自动机; 而1型文法上下文相关文法对应的是线性有界自动机; 0型文法无限制文法,包括了前面所有的文法，描述能力最强，对应的是图灵机。下推自动机可以做的事情，线性有界自动机都可以做。如果要从具体的语言方面来理解，最好是和编译原理的那几个阶段结合起来理解
如果你是学CS的，请无视我吧，我是半路出家的......