当前位置: 代码迷 >> 数据结构与算法 >> 关于"上下文有关文法"的一个有关问题,请对形式语言了解的朋友近来指教一下
  详细解决方案

关于"上下文有关文法"的一个有关问题,请对形式语言了解的朋友近来指教一下

热度:638   发布时间:2016-05-23 09:14:01.0
关于"上下文有关文法"的一个问题,请对形式语言了解的朋友近来指教一下.
下面这段内容是我从翁富良编著的《计算语言学导论》第41页中摘录下来的概念“上下文有关文法”的定义。

        如果P中的规则,满足如下的形式:αAβ→aγβ,其中A是非终结符,α,β,γ是文法符号串(也就是由终结符和非终结符组成的字符串),且γ至少包含一个字符。则G称之为上下文有关文法(简称为CSG)。
       
        然后接下来的第42页有一道例题如下:
       
        例3.3假设G=(N,V,P,S),N={S,B,C},V={0,1,2},P={S→0SBC,
S→0BC,CB→BC,0B→01,1B→11,1C→12,2C→22}。此文法为上下文有关文法。

        我的不明白之处是,上面这个文法怎么会是上下文有关文法呢,明明是个无限制重写系统。上面这个文法共有7个产生式,其中的六个都满足上面提到的定义。而第3个产生式,也就是CB→BC是不满足形式αAβ→aγβ的。
      我不知道是这本书上给出的定义错了,还是我的理解上有问题,请知情者指点迷静。多谢了,多谢了。

------解决方案--------------------
There are two different definitions for "context-sensitive grammar, " yielding grammars whose productions look quite different. However, the grammars are equivalent, in that they describe (almost) the same languages.

(Original definition) A context-sensitive grammar is one whose productions are all of the form

αAβ→αγβ

where A belongs to V and α,γ,β belong to (V | T)*.

The name "context-sensitive " comes from the fact that the actual string modification is given by A→γ , while the α and β provide the context in which the rule may be applied.

(Extra crispy definition) A context-sensitive grammar is one whose productions are all of the form

α-> β

where α,β belong to (V | T)+, and |α| <= |β|.
  相关解决方案
本站暂不开放注册!
内测阶段只得通过邀请码进行注册!
 
  • 最近登录:Thu Nov 23 11:41:51 CST 2017
  • 最近登录:Thu Nov 23 11:41:51 CST 2017
  • 最近登录:Thu Nov 23 11:41:51 CST 2017
  • 最近登录:Thu Nov 23 11:41:51 CST 2017
  • 最近登录:Thu Nov 23 11:41:51 CST 2017