什么是常规语言？

Question

我试图理解语言级别的概念(常规,上下文无关,上下文敏感等).

我可以很容易地看清楚这一点,但我发现的所有解释都是一堆符号并谈论集合.我有两个问题:

1. 你能用语言描述常用语言是什么,以及语言有何不同？

2. 人们在哪里学会理解这些东西？据我了解,这是正式的数学？我在大学有几个课程使用它,几乎没有人理解它作为导师只是假设我们知道它.我在哪里可以学到它以及为什么人们"期望"在如此多的资源中知道它？就像教育方面存在差距一样.

这是一个例子:

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

语言怎么能"超过"任何东西？

Answer 1

在计算机科学的背景下,一个词是符号的串联.使用的符号称为字母表.例如,形成了字母表中的一些字{0,1,2,3,4,5,6,7,8,9}将是1,2,12,543,1000,和002.

然后,语言是所有可能单词的子集.例如,我们可能想要定义一种捕获所有精英MI6代理的语言.这些都开始双0,所以在语言中的单词是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

请注意,所有有限语言都是常规语言,但并非所有常规语言都是有限的; 我们的double-0语言包含无限多个单词(007,008但也004242和0012345),但可以使用常量内存进行测试:要测试一个单词是否属于它,请检查第一个符号0是否为,以及第二个符号是否为0.如果是这种情况,请接受它.如果单词短于3或不是以字母开头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)是不规则的 - 您需要的不仅仅是恒定的内存量(=常数的状态) )存储1s 的数量以决定一个单词是否在该语言中.

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

Answer 2

以下是维基百科的一些等价定义:

[...]常规语言是一种形式语言(即,有限字母表中可能无限的有限符号序列集),它满足以下等效属性:

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

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

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

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

其中一个最重要的特征是,与无上下文语言不同,常规语言不支持任意嵌套/递归,但您确实有任意重复.

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

在我的大学里,我们在编译器课上学过一些正式的语言理论,但这在不同的学校之间可能有所不同.