上下文无关语言的闭包性质

上下文无关语言（CFL）被 下推自动机 .上下文无关语言可以由上下文无关语法生成，其生成形式（替换规则）如下：

A->ρ（其中A∈ N和ρ∈ （T）∪ N） *N是非终端，T是终端） 上下文无关语言的性质 工会： 如果L1和L2是两种与上下文无关的语言，那么它们的联合就是L1∪ 第二语言也将是上下文无关的。例如 L1={a ^N B ^N C ^M |m>=0和n>=0}和L2={a ⁿ B ^M C ^M |n>=0和m>=0} L3=L1∪ L2={a ^N B ⁿ C ^M ∪ A. ^N B ^M C ^M |n>=0，m>=0}也是上下文无关的。 L1表示a的数量应该等于b的数量，L2表示b的数量应该等于c的数量。他们的联合表示两个条件中的任何一个为真。所以它也是上下文无关的语言。

注： 所以CFL在联合政府下关闭。

连接： 如果L1和L2是两种与上下文无关的语言，则它们的连接是L1。第二语言也将是上下文无关的。例如 L1={a ^N B ^N |n>=0}和L2={c ^M D ^M |m>=0} L3=L1。L2={a ^N B ^N C ^M D ^M |m>=0和n>=0}也是上下文无关的。 L1表示a的数量应等于b的数量，L2表示c的数量应等于d的数量。它们的连接表示a的第一个数量应等于b的数量，然后c的数量应等于d的数量。因此，我们可以创建一个PDA，它将首先推动a，弹出b，按c键，然后按d键。这样它就可以被下推自动机接受，因此上下文无关。

注： 所以CFL在串联下是闭合的。

Kleene闭包： 如果L1是上下文无关的，则其Kleene闭包L1*也将是上下文无关的。例如 L1={a ^N B ^N |n>=0} L1*={a ^N B ^N |n>=0}*也是上下文无关的。

注： 所以CFL在Kleen关闭下关闭。

交叉与互补： 如果L1和L2是两种上下文无关的语言，那么它们的交集是L1∩ 第二语言不需要上下文无关。例如 L1={a ^N B ^N C ^M |n>=0和m>=0}和L2=（a ^M B ^N C ^N |n>=0和m>=0} L3=L1∩ L2={a ^N b ^N C ^N |n>=0}不需要与上下文无关。 L1表示a的数量应等于b的数量，L2表示b的数量应等于c的数量。它们的交点表示两个条件都必须为真，但下推自动机只能比较两个。所以它不能被下推自动机接受，因此不是上下文无关的。 同样，上下文无关语言L1的互补∑* – L1，不需要上下文无关。

注： 因此，在交叉和互补条件下，CFL是不封闭的。

确定性上下文无关语言 确定性CFL是可被确定性PDA识别的CFL的子集。确定性PDA从给定状态和输入符号只有一次移动，即它没有选择。要使一门语言成为DCFL语言，就必须明确何时推送或弹出。

例如，L1={a ^N B ^N C ^M |m>=0和n>=0}是DCFL，因为对于a，我们可以在堆栈上推送，对于b，我们可以弹出。可由确定性PDA识别。另一方面，L3={a ^N B ^N C ^m ∪ A. ^N B ^M C ^M |n>=0，m>=0}无法被DPDA识别，因为a和b的数量可以相等，或者b和c的数量可以相等。因此，它只能由NPDA实施。因此，它是CFL，而不是DCFL。 注： DCFL仅在互补同态和逆同态下闭合。 问题: 考虑下面给出的语言L1、L2、L3。 L1={a ^M B ^N |m，n>=0} L2={a ⁿ B ^N |n>=0} L3={a ⁿ B ^N C ^N |n>=0} 以下哪项陈述是不正确的？ A.下推自动机（PDA）可用于识别L1和L2 L1是一种常规语言 C.这三种语言都与上下文无关 D.图灵机器可以用来识别这三种语言

解决方案： 选项（A）表示PDA可用于识别L1和L2。L1包含任意数量的a后跟任意数量的b的所有字符串。因此，它可以被PDA接受。L2包含n个a后面跟着n个b的字符串。PDA也可以接受它。因此，选项（A）是正确的。 选项（B）表示L1是规则的。这是真的，因为L1的正则表达式是a*b*。 选项（C）表示L1、L2和L3与上下文无关。L3语言包含所有字符串，其中n个a后跟n个b后跟n个c，但PDA不能接受。所以选项（C）是不正确的。 选项（D）是正确的，因为图灵机器可以用来识别所有三种语言。

问题: 语言L={0 ^我 12 ^我 |我≥ 字母表{0，1，2}上的0}是： 答：不是递归的 B.是递归的和确定性的CFL C.是正常的 D.CFL机器人是否不是确定性CFL。

解决方案： 上面的语言是确定性的CFL，对于0，我们可以在堆栈上推0，对于2，我们可以弹出相应的0。因为没有歧义，所以它是确定性的。所以，正确的选择是（B）。由于CFL是递归的子集，所以它也是递归的。 问题: 请考虑下列语言： L1={0 ^N 1. ^N |n≥0 } L2={wcwr|wɛ{a，b}*} L3={wwr|wɛ{a，b}*} 这些语言中哪些是确定性上下文无关语言？ 答：没有一种语言 B.只有L1 C.只有L1和L2 D.所有三种语言

解决方案： 语言L1包含n 0后跟n 1的所有字符串。确定性PDA可以构造为接受L1。对于0，我们可以将其推到堆栈上，对于1，我们可以从堆栈中弹出。因此，它是DCFL。 L2包含所有形式为wcwr的字符串，其中w是a和b的字符串，wr是w的反向。例如，aabbcbbaa。为了接受这种语言，我们可以构造PDA，它将把堆栈上的所有符号推到c之前。在c之后，如果输入字符串上的符号与堆栈上的符号匹配，它将被弹出。因此，L2也可以被确定性PDA接受，因此它也是DCFL。 L3包含形式为wwr的所有字符串，其中w是a和b的字符串，wr是w的反向。但我们不知道w在哪里结束，wr从哪里开始。例如。；aabbaa是对应于L3的字符串。首先，我们将把它推到堆栈上。接下来，a可以是w或wr的一部分，其中w=a。因此，输入符号上的一个状态可以有多个移动。因此，只有非确定性PDA可以用来接受这种类型的语言。因此，它是NCFL而不是DCFL。 所以，正确的选项是（C）。只有L1和L2是DCFL。 问题: 以下哪一种语法生成语言L={a ^我 b ^J |我≠ j} S->AC | CB，C->aCb |a | b，a->aA |ɛb->Bb | S->aS | Sb | a | b S->AC | CB，C->aCb |ɛ，A->aA |ɛ，B->Bb | S->AC | CB，C->aCb | A->aA | A，B->Bb | B

解决方案： 解决这类问题的最佳方法是排除不满足条件的选项。语言L的条件是a的数量，b的数量应该不相等。 在选项（B）中，S=>aS=>ab。它可以生成a和B相等的字符串。所以，这个选项是不正确的。 在选项（C）中，S=>AC=>C=>ɛ。在ɛ中，a和b是相等的（0），因此这不是正确的选项。 在选项（A）中，S将由AC或CB替代。C将生成a的数量大于b的数量1或b的数量大于a的数量1。但一个以上的a或一个以上的b可以分别通过b->bB|或a->aA|进行补偿。所以它可能会给出a和b数量相等的字符串。所以，这不是一个正确的选项。 在选项（D）中，S将由AC或CB替代。C总是会生成相同数量的a和b。如果我们用AC替换s，a至少会添加一个额外的a。如果我们用CB替换s，b至少会添加一个额外的b。所以这个语法永远不会生成相同数量的a和b。所以，选项（D）是正确的。 本文由Sonal Tuteja撰稿。 如果您发现任何不正确的地方，或者您想分享有关上述主题的更多信息，请写评论