谁能给我解释一下为什么这种文法[上下文无关文法和上下文相关文法]接受字符串？
我知道的是
上下文无关文法是一种形式文法，其中每个生产(重写)规则都是 V→w 的一种形式 其中 V 是单个非终结符，w 是一串终结符和/或非终结符。 w可以为空
上下文相关文法 是一种形式文法，其中任何产生式(重写)规则的左侧和右侧都可能被终结符和非终结符符号的上下文包围。
但是我该如何解释为什么这些语法接受字符串呢？
最佳答案
这里的一个重要细节是语法不接受字符串；它们生成 字符串。语法是对语言的描述，它提供了一种生成语言中包含的所有可能字符串的方法。为了判断语言中是否包含特定字符串，您可以使用识别器，这是一种处理给定字符串并说"is"或“否”的自动机。
A context-free grammar (CFG) 是一种文法，其中(如您所述)每个产生式都具有 A → w 的形式，其中 A 是非终结符，w 是终结符和非终结符的字符串。非正式地，CFG 是一种文法，其中任何非终结符都可以在任何时候扩展到它的任何产生式。文法的语言是可以从起始符号导出的终结符串的集合。
A context-sensitive grammar (CSG) 是一种文法，其中每个产生式都具有 wAx → wyx 的形式，其中 w 和 x 是终结符和非终结符的字符串，y 也是终结符的字符串。换句话说，产生式给出的规则是“如果你在给定的上下文中看到 A ，你可以用字符串 y 替换 A。”不幸的是，这些语法被称为“上下文相关语法”，因为这意味着“上下文无关”和“上下文相关”并不是对立的，并且这意味着某些类别的语法可以说需要大量的上下文信息，但未被正式视为上下文相关。
要判断一个字符串是否包含在CFG或CSG中，有很多方法。首先，您可以为给定的语法构建一个识别器。对于 CFG， pushdown automaton (PDA) 是一种可以准确接受上下文无关语言的自动机，并且有一个简单的结构可以将任何 CFG 转换为 PDA。对于上下文相关的语法，您将使用的自动机称为 linear bounded automaton (LBA)。
但是，如果天真地对待上述这些方法，则效率不高。要确定一个字符串是否包含在 CFG 的语言中，有更有效的算法。例如，许多语法可以有 LL(k)或 LR(k)为它们构建的解析器，它允许你(在线性时间内)决定一个字符串是否包含在语法中。所有语法都可以使用 Earley parser 进行解析，在O(n3)中可以判断一个长度为n的字符串是否包含在语法中(有趣的是，它可以在O(n2)中解析任何明确的CFG ，并且使用 lookaheads 可以在 O(n) 时间内解析任何 LR(k) 文法!)。如果您纯粹对“字符串 x 是否包含在语法 G 生成的语言中？”这个问题感兴趣，那么这些方法中的一种会非常好。如果您想知道字符串 x 是如何生成的(通过查找 parse tree )，您可以采用这些方法来提供此信息。然而，解析 CSG 通常是 PSPACE 完备的，因此没有已知的在最坏情况多项式时间内运行的解析算法。不过，有些算法在实践中往往运行得很快。 解析技术:实用指南(见下文)的作者整理了a fantastic page containing all sorts of parsing algorithms ，包括解析上下文相关语言的语言。
如果您有兴趣了解更多关于解析的知识，请考虑查看 Grune 和 Jacobs 的优秀书籍“Parsing Techniques: A Practical Guide, Second Edition”，其中讨论了各种解析算法，用于确定字符串是否包含在语法中，如果那么，它是如何通过解析算法生成的。
关于algorithm - 上下文无关文法与上下文相关文法？，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/8236422/