0

假设 E = {a, b}。令 L0 = {(b^(n))(a^(2n)) : n >= 0}。令 L = ((不操作)L0)

L 是正则的、上下文无关的但不是正则的，还是不是上下文无关的？证明你的答案。

我正在寻找 L 是什么，以及如何以与问题中描述 L0 的方式类似的方式来描述它，以及答案。

解释对我来说很重要，如果您愿意贡献，请具体说明。我希望了解此材料以进行测试。

非常感谢！

4

2 回答 2

1

我将尝试使用外行的语言向您解释，并提示您将其正式化。

LE={a,b}是一种语言，其中包含所有不在语言中的字母字符串。L0 这不是一种常规语言。

中的字符串L是所有以 L0 的 DFA 的非最终状态结束的字符串。但是由于您无法为 L0 构建 DFA/NFA，因此您也无法为 L 构建 DFA。

原因：在L0一个未绑定的数n中，需要在查看所有b后存储，然后在检查a时使用它，DFA没有记忆。您不能为上述语言编写正则表达式。

使用抽水引理 L 不是上下文无关语言

S=ab是 L 中的一个字符串 使用 PL 我将分为 5 个部分

S=uvxyz

u="" v=a x="" y=b z=""

现在对于n=0 新字符串是S(n=0)="" which is not in L.

如果我们将 ab 分为

   u="" v="" x=a y=b z=""

现在为n=2 S(n=2)=abb which is not in L

所以 L 不是 CFG。

PS：如果你在 m 上发现任何漏洞，请告诉我

于 2011-03-10T06:58:36.010 回答
0

我不确定你是否学会了抽水引理。但它是一种判断语言是否正常的方法。请记住，如果 L0 是常规的，那么 L1 也是常规的，因为您可以通过交换 L0 dfa 的最终和初始统计数据来制作 L1 的 dfa。

考虑 L0 的任何示例，其中 b^ma^2m 并且该字符串足够大以抽取 lema。

将示例分成三部分 xyz。

在哪里 |xy| < m（子字符串 xy 中的元素数）和 |y| >= 1。

由于块 xy < m 它必须是所有 b，因为有 b^m b。

现在让泵 y 0 次。

xy^0 z 如果你的 lang 是 bbbaaaaaa 并且 |y|=1 ur lang 变成 bbaaaaaa，则意味着它现在遵循 b^na^3n。这使它不是正则表达式。

这意味着 L1 不是正则表达式 2。

于 2011-03-11T00:51:34.160 回答