84

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

我可以很容易地查到这个，但我找到的所有解释都是一堆符号和谈论集合。我有两个问题：

  1. 你能用语言描述什么是常规语言，以及这些语言有什么不同吗？

  2. 人们从哪里学会理解这些东西？据我了解，它是形式数学？我在大学有几门课程使用它，几乎没有人理解它，因为导师只是假设我们知道它。我在哪里可以学习它，为什么人们“期望”在这么多来源中知道它？好像教育有差距。

这是一个例子：

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

一种语言怎么能“超越”任何东西？

4

2 回答 2

165

在计算机科学的语境中，一个词是符号的串联。使用的符号称为字母表。例如，一些由字母组成的单词{0,1,2,3,4,5,6,7,8,9}是1, 2, 12, 543, 1000, 和002。

因此，语言是所有可能单词的子集。例如，我们可能想要定义一种语言来捕获所有精英军情六处特工。这些都以双 0 开头，所以语言中的单词是007, 001, 005, and 0012，但不是07or 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, 还有004242and 0012345），但可以用常数记忆进行测试：要测试一个单词是否属于其中，检查第一个符号是否是0，以及第二个符号是否是0。如果是这样，请接受它。如果单词短于三或不以 开头00，则不是军情六处代号。

形式上，有限状态机或正则文法的构造用于证明语言是正则的。这些类似于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 n 2 n，对于任意n）是不规则的 - 您需要的内存量不只是恒定数量（= 恒定数量的状态) 来存储1s 的数量来决定一个词是否在该语言中。

这通常应该在理论计算机科学课程中解释。幸运的是，维基百科很好地解释了正式语言和常规语言。

于 2011-07-16T15:18:19.557 回答
5

以下是来自Wikipedia的一些等效定义：

[...] 常规语言是满足以下等效属性的形式语言（即，来自有限字母表的一组可能无限的有限符号序列）：

  • 它可以被确定性有限状态机接受。

  • 它可以被非确定性有限状态机接受

  • 它可以用正式的正则表达式来描述。

    请注意，许多编程语言提供的“正则表达式”功能都增加了一些功能，使它们能够识别非正则语言，因此不严格等同于正式的正则表达式。

首先要注意的是，常规语言是一种形式语言，有一些限制。形式语言本质上是一个（可能是无限的）字符串集合。例如，形式语言 Java 是所有可能的 Java 文件的集合，它是所有可能的文本文件集合的子集。

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

一种语言总是有一个底层字母表，它是一组允许的符号。例如，编程语言的字母表通常是 ASCII 或 Unicode，但在形式语言理论中，谈论其他字母表的语言也很好，例如二进制字母表，其中唯一允许的字符是0和1。

在我的大学里，我们在编译器课上学习了一些形式语言理论，但这可能在不同学校之间有所不同。

于 2011-07-16T15:17:38.080 回答