1

我正在解决一个问题，我迫切需要一个提示来解决一个问题：

在 union 下使用闭包来表明以下语言是上下文无关的：

{a m b n c p d q : n=q 或 m <= p 或 m+n=p+q }

4

1 回答 1

4

由于您没有指定您的问题是什么，我将只介绍您需要知道的内容。

在工会下关闭- 这是什么意思？
如果我们有一种语言L和一种语言S并且两者都是上下文无关的，我们知道语言的联合也是上下文无关的。

L ∪ S = 上下文无关语言

有关 CFL 的更多闭包属性，请参阅this，如果您有兴趣，可以在网上找到这方面的证明（或者您可以尝试制作自己的证明）。

你怎么能用它来解决你的问题？
你有这个语言规范（我们称之为L）：

L = {a m b n c p d q : n=q 或 m <= p 或 m+n=p+q }

您可以将此语言拆分为其他 3 种语言：

A = {a m b n c p d q : n = q }
B = {a m b n c p d q : m <= p }
C = {a m b n c p d q : m+n = p +q }

很容易看出这一点A ∪ B ∪ C = L。

如果您可以证明 A、B 和 C 是上下文无关的，那么您可以得出结论 L 也是上下文无关的。

解决方案
要确定一种语言是否与上下文无关，请参阅此答案。引用答案：

首先，你应该尝试构建一个上下文无关的语法来形成主题中的语言。如果所有产生式的左侧恰好包含一个非终结符，则文法是上下文无关的。根据定义，如果存在，则该语言是上下文无关的。

等效构造是下推自动机。它与 DFA 相同，但有可用的堆栈。它可能比语法更容易构建。

因此，如果您可以为每种语言 A、B 和 C 构建一个 CFG（或 PDA），那么您就解决了您的问题。

让我们以语言为例A：我们需要一个语法来生成一个形式的字符串，a..b..c..d..其中我们必须有相等数量的bs 和ds。

S -> AE
A -> Aa  | ε
E -> bEd | C
C -> Cc  | ε

S是开始变量（或非终端），ε是空字符串（有些人使用空符号^，但我一直被告知使用ε）。该语法应该能够生成语言A，因此A是上下文无关的。（如果有人检测到错误，请告诉我。我有一段时间没有创建 CFG）。

由于这是一个练习，我会让你解决剩下的部分，但你应该知道如何去做。

于 2013-04-29T16:52:54.200 回答