首页 文章

上下文敏感的语法可以有空字符串吗？

提问于
浏览 次
1

在我的一个cs类中，他们提到无上下文语法和上下文敏感语法之间的区别在于CSG，然后 生产环境 规则的左侧必须小于或等于右侧 .

因此，他们给出的一个例子是，上下文敏感的语法不能有空字符串，因为这样就不会满足第一个规则 .

但是，我已经理解常规语法包含在无上下文中，无上下文包含在上下文敏感中，并且上下文相关包含在递归可枚举语法中 .

因此，例如，如果语法是递归可枚举的，那么也是类型上下文敏感，无上下文和常规的类型 .

问题是，如果发生这种情况，那么如果我有一个包含空字符串的无上下文语法，那么它就不能满足规则被视为上下文敏感，但是会发生矛盾，因为每个上下文敏感没有上下文 .

grammar context-free-grammar computation-theory context-sensitive-grammar

1 回答

  • 1

    空制作（"lambda productions"，所谓的因为λ通常用于指代空字符串）可以从任何无上下文语法中机械地消除，除了可能的顶级制作 S → λ . 这样做的算法很好地呈现在形式语言理论的每一个文本中 .

    因此对于任何具有lambda产品的CFG，都有一个等效的CFG，没有lambda产生，它生成相同的语言，并且也是一个上下文敏感的语法 . 因此，禁止在CSG中签订 Contract 规则不会影响语言的层次结构：任何无上下文的语言都是一种上下文敏感的语言 .

    乔姆斯基对上下文敏感语法的原始定义没有指定非 Contract 属性，而是更具限制性的属性：每个 生产环境 必须是 αAβ→αγβ 形式，其中 A 是单个符号而 γ 不是空的 . 这组语法生成与非签约语法相同的语言集（Chomsky也证明了这一点），但它不是同一组 . 此外，他的无上下文语法确实是上下文敏感语法的一个子集，因为根据他对CFG的原始定义，lambda产品被禁止 . （1959年的论文可在线获取;有关参考链接，请参阅Wikipedia article on the Chomsky hierarchy . ）

    正是存在一个非空的上下文 - α 和 β - 这导致名称"context-sensitive"和"context-free";对于诸如 AB→BA 之类的任意非约束规则而言"context-sensitive"可能意味着什么并不太明确 . （注1）

    简而言之，鉴于您的问题中引用的CFG和CSG的常见现代用法，"every CFG is a CSG"在技术上并不正确 . 但这只是一个技术性问题：带有lambda产品的CFG可以进行机械转换，就像非 Contract 语法可以机械地转换成符合Chomsky对上下文敏感的定义的语法（参见Wikipedia article on non-contracting grammars） .

    （通过向规则 S→λ 添加CFG和CSG定义的例外，允许上下文敏感语言和无上下文语言都包含空字符串也很常见 . ）

    注意事项

    • 在乔姆斯基的无上下文和敏感语法的表述中，即使对于CSG，解析树的含义也是明确的;由于乔姆斯基是语言学家并且正在寻求解释自然语言结构的框架，因此解析树的概念至关重要 . 如何将 AB → BA 的结果描述为解析树并不是很明显，尽管在例如 a A b → B 的情况下非常清楚 .
    回复于

相关问题