根据它的正式定义,不是每一种语言都是规则的吗?
Isn't every language regular, according to formal definition of it?
这是来自Wikipedia's article的常规语言的定义:
The collection of regular languages over an alphabet Σ
is defined recursively as follows:
The empty language Ø
is a regular language.
For each a ∈ Σ
(a belongs to Σ), the singleton language {a}
is a regular language.
If A
and B
are regular languages, then A ∪ B
(union), A • B
(concatenation), and A*
(Kleene star) are regular languages.
No other languages over Σ
are regular.
现在想一想aⁿbⁿ
我们知道不是正则,但是它不符合上面的规则吗?
{a}
是常规的,{b}
也是常规的,它们的串联也是如此,因此提到的 lang!
感觉我搞错了一组语言,换句话说,一组组;对于一组单词,即语言?
aⁿbⁿ
是一种语言,它只包含 带有 n
x a
s 后跟 n
x[ 的字符串=14=]s.
您可以创建一种常规语言,它是该语言的超集,但不是该语言本身。
你的说法是错误的,你可以从规则中形成这种特定的语言。形式上,这遵循 Pumping Lemma。不过,要解决您问题中的推理:
{a}是正则的,所以通过重复拼接,{a^m}是正则
{b}是正则的,所以通过重复串联,{b^n}是正则的
所以它们的串联,也就是任何形式的 {a^m b^n} 也是规则的,但这恰恰是约束 m = = n 你不能通过这个家庭制定。
你说得对,{a}
是正则,{b}
是正则。因此,根据您提到的规则,它们的连接也是规则的。但是,两种语言的串联定义为 {vw | v in L_1, w in L_2}
。由于 L_1
和 L_2
都只包含一个词(分别是 a
和 b
),这个定义等价于 {vw | v = a, w = b}
,它是集合 {ab}
.
因此,两种语言的拼接是集合{ab}
,而不是a^n b^n
。
这是来自Wikipedia's article的常规语言的定义:
The collection of regular languages over an alphabet
Σ
is defined recursively as follows:
The empty language
Ø
is a regular language.For each
a ∈ Σ
(a belongs to Σ), the singleton language{a}
is a regular language.If
A
andB
are regular languages, thenA ∪ B
(union),A • B
(concatenation), andA*
(Kleene star) are regular languages.No other languages over
Σ
are regular.
现在想一想aⁿbⁿ
我们知道不是正则,但是它不符合上面的规则吗?
{a}
是常规的,{b}
也是常规的,它们的串联也是如此,因此提到的 lang!
感觉我搞错了一组语言,换句话说,一组组;对于一组单词,即语言?
aⁿbⁿ
是一种语言,它只包含 带有 n
x a
s 后跟 n
x[ 的字符串=14=]s.
您可以创建一种常规语言,它是该语言的超集,但不是该语言本身。
你的说法是错误的,你可以从规则中形成这种特定的语言。形式上,这遵循 Pumping Lemma。不过,要解决您问题中的推理:
{a}是正则的,所以通过重复拼接,{a^m}是正则
{b}是正则的,所以通过重复串联,{b^n}是正则的
所以它们的串联,也就是任何形式的 {a^m b^n} 也是规则的,但这恰恰是约束 m = = n 你不能通过这个家庭制定。
你说得对,{a}
是正则,{b}
是正则。因此,根据您提到的规则,它们的连接也是规则的。但是,两种语言的串联定义为 {vw | v in L_1, w in L_2}
。由于 L_1
和 L_2
都只包含一个词(分别是 a
和 b
),这个定义等价于 {vw | v = a, w = b}
,它是集合 {ab}
.
因此,两种语言的拼接是集合{ab}
,而不是a^n b^n
。