非常规语言与常规语言的连接总是不规律的吗?

问题描述 投票:4回答:3

我想知道两种语言(一种是常规语言还是另一种语言)之间的连接是否总是不规则,或者输出是否是常规语言。谢谢。

computer-science context-free-grammar regular-language chomsky-normal-form
3个回答
3
投票

不,因为我们可以找到一个证明有时会发生的反例:

L1不规则:(a ^ 2)^ n,n> 1 L2常规:a *

连接产生语言L3 = aa *,这显然是规则的。


0
投票

a ^(2 ^ n)n> = 0是非常规的,除了将它与常规的*连接起来,产生常规语言。它变为L = {a ^(2 ^ n)a *,n> = 0},它基本上抵消了L = {aa *},这是规则的。

Patrick87,(a ^ 2)^ n n> 1有正则表达式(aaaa)(aa)*


0
投票

请记住空语言和空集;并且空字符串{ε}的单例语言都是规则的。任何非正规语言和空语言的连接都是空语(常规),任何非常规语言和{ε}的连接都是原始语言(非常规)。因此,答案取决于语言的选择。

(@Hyruma92给出了连接给出常规语言的另一个例子;我添加了这个答案,因为我认为它更直接而且简单地让你在那里。这里的直觉是空语言是语言连接的零元素和{ε}是标识元素,它激发了你可能想要尝试它们的原因。)

© www.soinside.com 2019 - 2024. All rights reserved.