根据它的正式定义,不是每一种语言都是规则的吗?

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ⁿ 是一种语言,它只包含 带有 nx as 后跟 nx[ 的字符串=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_1L_2 都只包含一个词(分别是 ab),这个定义等价于 {vw | v = a, w = b},它是集合 {ab}.

因此,两种语言的拼接是集合{ab},而不是a^n b^n