什么是正则语言？

Question

我试图理解语言级别的概念（常规、上下文无关、上下文相关等）。

我可以轻松查找此信息，但是所有我找到的解释都是一堆符号，并且谈论了“集合”。 我有两个问题：

1. 您能用通俗易懂的语言描述什么是常规语言，以及这些语言之间的区别吗？

2. 人们在哪里学习了解这些内容？据我所知，这是正式的数学知识？我在大学修过几门使用它的课程，但几乎没有人理解，因为导师认为我们已经掌握了它。那我应该去哪里学习呢？为什么人们“期望”在许多资料中了解它？这就像教育中存在缺口。

以下是一个示例：

 

属于此集合的任何语言都是该字母表上的常规语言。

语言怎么会“在”什么东西上呢？

- FBryant87

---

实际上，维基百科对这一切的解释做得还不错。你可以从http://en.wikipedia.org/wiki/Formal_language开始，然后逐个学习相关主题。例如，在“理论计算机科学”课程中会涉及到这个问题。 - Bart

我认为这样的问题在SO上是符合主题的。请参考meta上的“在哪里讨论计算机科学？”（http://meta.stackexchange.com/questions/80023/where-on-se-to-discuss-computer-science）。 - hammar

什么是正则语言？为什么 a*b* 是正则的？但是语言 { a^nb^n | n > 0 } 不是一个正则语言。 - Grijesh Chauhan

Answer 1

在计算机科学中，一个“单词”是由“符号”连接而成的。使用的符号称为“字母表”。例如，由字母表{0,1,2,3,4,5,6,7,8,9}形成的一些单词是1、2、12、543、1000和002。

然后，“语言”是所有可能单词的子集。例如，我们可能想定义一个捕捉所有精英MI6特工的语言。它们都以双零开头，因此该语言中的单词将是007、001、005和0012，但不包括07或15。为简单起见，我们称“语言基于某个字母表”而不是“是由该字母表中符号连接而成的单词的子集”。

在计算机科学中，我们现在希望对语言进行分类。如果可以通过检查单词中的每个符号并决定单词是否属于该语言来使用算法/具有恒定（有限）内存的机器判断语言，则称该语言为“正则语言”。仅由单词42组成的语言是正则的，因为您可以判断单词是否属于该语言，而无需任意数量的内存；您只需要检查第一个符号是否为4，第二个符号是否为2，以及是否跟随其他数字。

所有词汇有限的语言都是正则的，因为我们可以（理论上）构建一个恒定大小的控制流树（您可以将其视为一堆嵌套的if语句，检查每个数字之后的一个）。例如，我们可以使用以下结构测试一个单词是否在“10到99之间的质数”语言中，除了编码当前所在代码行的内存外，不需要任何内存：

if word[0] == 1:
  if word[1] == 1: # 11
      return true # "accept" word, i.e. it's in the language
  if word[1] == 3: # 13
      return true
...
return false

请注意，所有有限语言都是正则的，但并非所有正则语言都是有限的；我们的双0语言包含无限数量的单词（007，008，还有004242和0012345），但可以用恒定的内存测试：要测试一个单词是否属于它，检查第一个符号是否为0，第二个符号是否为0。如果是这样，接受它。如果该单词长度小于三或不以00开头，则不是MI6代号。

形式上，有限状态机或正则文法的构建用于证明一种语言是正则的。它们类似于上面的if语句，但允许任意长的单词。如果有一个有限状态机，也有一个正则文法，反之亦然，因此只需证明其中之一即可。例如，我们的双0语言的有限状态机如下：

start state:  if input = 0 then goto state 2
start state:  if input = 1 then fail
start state:  if input = 2 then fail
...
state 2: if input = 0 then accept
state 2: if input != 0 then fail
accept: for any input, accept

对应的正则语法是：

start → 0 B
B → 0 accept
accept → 0 accept
accept → 1 accept
...

等价的正则表达式是：

00[0-9]*

有些语言是不规则的。例如，任意数量的数字1后跟相同数量的数字2的语言（通常写作1ⁿ2ⁿ，对于任意n）是不规则的——你需要更多的内存（=常数个状态）来存储1的数量，以确定一个单词是否属于该语言。

这个通常应该在理论计算机科学课程中解释。幸运的是，维基百科很好地解释了formal和regular languages。

- phihag

---

@user666254 始终允许使用常量内存，因为它可以编码为状态。问题是，当 n 趋近于无穷大时，你需要比任何常量内存更多的内存来测试 1^n2^n。正式地说，通常使用正则语言的泵引理来证明一个语言不是正则的。 - phihag

更具体地说，您需要3n+1个状态来确定一个字符串是否属于1n2n语言。 - laike9m

我个人认为，如果一个人没有学过数学符号，维基百科在解释常规语言方面做得并不好。即使他们解释了一些符号和变量，他们也会添加一些额外的内容，并且没有解释它们。这篇文章对于那些不需要它的人可能更易读，但对于我们其他人来说，它需要更多的澄清。 - Andrew S

@P.Soutzikevich 不，就像一个秤可以用来决定一辆车是否算作卡车（>12吨），但是秤并不定义汽车。还有其他几种方法可以证明一种语言不是正则的。你说的对，对于正则语言的泵引理与正则语言的定义非常密切相关。它只是没有_定义_正则语言。 - phihag

在表达式中，闭合括号的数量必须与开放括号匹配。((( 1)))是有效的Python代码，但(1))不是。因此（以及出于许多其他原因），Python编程语言的语法不形成正则语言。 - phihag

Answer 2

以下是来自维基百科的等效定义：

[...] 正则语言是指满足以下等价属性的形式语言（即，可能是有限字母表中有限序列的可能无限集合）：

- 可以被确定性有限状态机接受。 - 可以被非确定性有限状态机接受。 - 可以用正则表达式表示。

请注意，许多编程语言提供的“正则表达式”功能具有识别不是正则的语言的能力，并且因此不严格等同于正式的正则表达式。

首先需要注意的是，正则语言是一种形式语言，具有一定的限制。形式语言本质上是字符串的（可能是无限的）集合。例如，Java形式语言是所有可能的Java文件的集合，这是所有可能的文本文件的子集。

最重要的特征之一是，与无上下文语言不同，正则语言不支持任意嵌套/递归，但您可以进行任意重复。

语言始终具有底层字母表，这是允许使用的符号集。例如，编程语言的字母表通常是ASCII或Unicode，但在形式语言理论中，也可以讨论其他字母表上的语言，例如二进制字母表，其中仅允许使用0和1字符。

在我的大学里，我们在编译器课程中学习了一些形式语言理论，但这可能因学校而异。

- hammar