给定语言是：（常规|上下文无关|等）
假设 E = {a, b}。设 L0 = {(b^(n))(a^(2n)) : n >= 0}。令 L = ((不操作)L0)
L 是正则的、上下文无关的但不是正则的、还是非上下文无关的？证明你的答案。
我正在寻找 L 是什么，以及如何以与问题中描述 L0 类似的方式来描述它，以及答案。
这个解释对我来说非常重要，如果你愿意贡献，请具体说明。我希望了解这些材料以进行测试。
非常感谢！
Assume E = {a, b}. Let L0 = {(b^(n))(a^(2n)) : n >= 0}. Let L = ((NOT OPERATION)L0)
Is L regular, context-free but not regular, or not context-free? Prove your answer.
I'm looking for what L would be, and how to describe it in a similar fashion of how L0 was described in the question, along with the answer.
The explanation is very important to me, if you'd like to contribute, please be specific. I'm looking to understand this material for a test.
Thanks very much!
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
我将尝试用通俗易懂的语言向您解释，并提示您将其形式化。
L是一种语言，包含E={a,b}中所有不属于语言L0的字母字符串这不是一种常规语言。
L中的字符串是所有以L0的DFA非最终状态结束的字符串。但是，由于您无法为 L0 构建 DFA/NFA，因此您也无法为 L 构建 DFA。
原因：
L0中有一个未绑定的数n，需要在查看所有b后存储，然后在检查a时使用它，DFA没有内存。您无法为上述语言编写正则表达式。
使用泵引理 L 不是上下文无关语言
S=
ab是 L 中的字符串分为 5 个部分
使用 PL，我现在将
n=0new String 是
S(n=0)=""，它不在 L中。如果我们将 ab 分为
Now for
n=2S(n=2)=abb它不在 L中，所以 L 不是 CFG。
PS：如果你发现m上有洞，请告诉我
I will try to explain you using layman's language and hints for you to do formalize it.
Lis a language with all the strings of alphabetE={a,b}which are not in languageL0This is a not a regular language.
Strings in
Lare all the strings which end at non-final states of DFA of L0.But as you can't build DFA/NFA for L0, you can't have a DFA for L too.
Reason: In
L0one unbound number n, which need to be stored after look at all b's then use it while checking a's, DFA have no memory.You can't write a regular expression for above language.
Using Pumpping lemma L is not a Context Free Language
S=
abis a string in LUsing PL I'll divide in into 5 parts
Now for
n=0new String is
S(n=0)=""which is not in L.if we divide ab into
Now for
n=2S(n=2)=abbwhich is not in LSo L is not CFG.
PS: Let me know if you find any hole in m
我不确定你是否学会了泵送lema。
但这是判断语言是否规则的一种方法。
请记住，如果 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 你的 lang 变成 bbaaaaaa 意味着现在它遵循 b^na^3n。这使得它不是正则表达式。
这意味着 L1 不是正则表达式 2。
I'm not sure if you've learned the pumping lema.
But its a way to tell whether the language is regular.
And remember that if L0 is regular then L1 is regular too since you can make a dfa of L1 by swapping the final and initial stats of the L0 dfa.
Consinder any example of L0 where b^m a^2m and this string is big enough for pumping lema.
Divide the example into three parts xyz.
where |xy| < m (number of elements in the substring xy)
and |y| >= 1.
Since the chunk xy < m it must be all b's since there are b^m b's.
now lets pump y 0 times.
x y^0 z has so if your lang was bbbaaaaaa and |y|=1 ur lang becomes bbaaaaaa meaning that now it follow b^n a^3n. Which makes it not a regex.
Meaning that L1 is not a regex 2.