什么是常规语言？

我试图理解语言水平的概念（规则，上下文无关，上下文敏感等）。

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

  1. 你能用文字来描述常规语言是什么，以及语言有何不同？

  2. 人们在哪里学会了解这些东西？ 据我所知，这是正式的math？ 我在uni使用过几门课程，几乎没有人知道这是因为我们知道的导师。 我在哪里可以学到这些知识，为什么人们“期望”能够从众多来源中了解它呢？ 就好像教育上有差距

这是一个例子 ：

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

一个语言如何能“超越”任何东西？

在计算机科学的背景下，一个词就是符号的连接。 使用的符号被称为字母表 。 例如，由字母{0,1,2,3,4,5,6,7,8,9}组成的一些单词将是{0,1,2,3,4,5,6,7,8,9}和002 。

一种语言是所有可能单词的一个子集。 例如，我们可能想要定义一种捕捉所有精英军情六处特工的语言。 这些都以0开头，所以语言中的词将是007和0012 ，但不是07或15 。 为了简单起见，我们说一种语言是“ 在字母表上”，而不是“字母中的符号连接形成的单词的子集”。

在计算机科学中，我们现在要分类语言。 如果能够通过一个接一个地检查单词中的所有符号来判断一个单词是否在具有恒定（有限）记忆的algorithm/机器的语言中，我们称之为语言规则 。 由单词42组成的语言是规则的，因为您可以决定是否在其中包含一个单词而不需要任意数量的内存。 你只要检查第一个符号是否是4，第二个是否是2，以及是否有更多的数字跟在后面。

所有语言数量有限的语言都是规则的，因为我们可以（理论上）只是build立一个恒定大小的控制stream树（你可以把它想像成一堆嵌套的if语句来检查一个数字）。 例如，我们可以用下面的构造来testing一个单词是否在“10到99之间的素数”语言中，除了要编码我们当前在哪个代码行上的内容之外，不需要内存： 

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

请注意，所有有限的语言都是规则的，但并不是所有的规则语言都是有限的 我们的double-0语言包含无限数量的单词（ 004242 ，也包括004242和0012345 ），但可以用常量内存进行testing：要testing单词是否属于它，请检查第一个符号是否为0 ，以及是否第二个符号是0 。 如果是这样的话，接受它。 如果单词短于3或者不以00开始，则不是MI6代码名称。

forms上， 有限状态机或常规语法的结构被用来certificate语言是规则的。 这些与上面的陈述类似，但允许任意长的单词。 如果有一个有限状态机，也有一个正规的语法，反之亦然，所以它也足够了。 例如，我们的双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 ...

等效的正则expression式是： 

 00[0-9]*

有些语言是不正规的。 例如，任何数字1的语言，后面跟着相同的数字2 （对于任意的n ，通常写成1 n 2 n ）是不规则的 – 你需要的不止是一个恒定数量的内存（=一个常数的状态）来存储1s的数量来决定一个单词是否在该语言中。

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

以下是维基百科的一些等同定义：

常规语言是一种forms语言（即，来自有限字母表的符号的有限序列的可能无限集合），其满足以下等价性质：

  • 它可以被一个确定性的有限状态机所接受。
  • 它可以被一个不确定的有限状态机所接受

  • 它可以用一个正式的正则expression式来描述。

    请注意，随许多编程语言提供的“正则expression式”function都增加了使其能够识别不规则语言的function，因此不完全等同于正式正则expression式。

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

其中一个最重要的特征是，与上下文无关的语言不同 ，常规的语言不支持任意的嵌套/recursion，但是你有任意的重复。

一种语言总是有一个潜在的字母表，这是一组允许的符号。 例如，编程语言的字母表通常是ASCII或Unicode，但是在forms语言理论中，谈论其他字母的语言也是好的，例如只允许字符为0和1的二进制字母表。

在我的大学里，我们在编译器课上学了一些正式的语言理论，但不同的学校可能不同。

我从Michael Sipser的“计算理论导论”中学到了很多东西， 我发现它非常有用。

这里是内容：

  • 介绍
  • 第1部分：自动机和语言
    • 1.正规语言
    • 2.上下文无关语言
  • 第2部分：可计算性理论
    • 3.教会图灵论文
    • 4.可决定性
    • 5.可缩减性
    • 6.可计算性理论的高级话题
  • 第三部分：复杂性理论
    • 7.时间复杂性
    • 8.空间复杂性
    • 9.难以分辨
    • 10.复杂性理论的高级话题。
Interesting Posts