在计算机科学中，什么不是正式语言？

Question

在维基百科language上，我找到了一种正式语言的定义：

在数学、计算机科学和语言学中，形式语言是一组符号串，它们可能受到特定于它的规则的约束。

在我看来这很抽象。我无法想象任何不符合这个定义的语言。有没有人知道非正式语言是什么样子的，以及它是如何不符合定义的？

Answer 1

让我先回答你的问题。正规语言的一个很好的例子是自然语言。英语和斯洛文尼亚语就是例子。塔加洛和塔里费特·伯伯也是如此。不幸的是，语言学家似乎对自然语言没有一致的定义。

诺姆·乔姆斯基( Noam )在1956年的论文“https://chomsky.info/wp-content/uploads/195609-.pdf”中尝试用无上下文的游戏来模拟自然语言。他在那篇论文中发明了(或者发现，如果你愿意的话)；尽管他没有这么称呼它们；虽然它们对英语语言没有什么帮助，但它们彻底改变了计算机科学。

形式上，正式语言只是有限字母表上的一组字符串。就这样。

示例包括所有有效的C程序、所有有效的HTML文件、所有有效的XML文件、所有“平衡”括号(例如(), ()(), ((()))()(()), ...)的字符串、所有总是停顿的确定性图灵机器的集合(以某种编码方式编码)、可以用k-colors着色的所有简单图集(实际上是它们的代码在某种编码下)、所有以1结尾并以1开头的二进制字符串的集合，等等。

有些使用regex很容易识别(或者等效地说是DFA)；有些是不可能用DFA识别的，但是可以用PDA识别(或者，可以用上下文无关的语法来描述)；另一些不承认这样的描述，但是可以被图灵机器识别；有些甚至不能被图灵机器识别(称为无法计算)。

这就是为什么定义如此有用的原因。我们每天在CS中遇到的许多事情都可以用正式语言来表达。

为了更好地介绍这一主题，我强烈推荐由Hopcroft等人撰写的关于自动机理论、语言和计算的精湛书籍。

Answer 2

英语不是一种正式的语言。它不仅仅是一组字符串，它有一种口头形式，随着时间的推移而演变，还有方言，还有其他正式语言所没有的东西。一种正式的语言从一个十年到下一个十年都无法获得“电子邮件”这个词。

Answer 3

语言是由给定的符号组成的一组序列。它可以是有限的，也可以是无限的(英语句子集是无限的，即使有句子(如过长的句子，即使是以英语为母语的人也无法理解)。如果它是有限的，那么它的任何描述都是一个正式的定义。

如果语言是无限的，比如涉及数字的算术表达式的语言，两个二进制运算符'+'，'*‘和变量，那么您不可能列出属于该语言的所有字符串，但是有时(请参阅blazs下面的注释)，您可以将有限的描述描述为一组规则。

E := NUM _v_E '+‘E_x_E '*’E

(其中NUM是一个数字序列，v是一个变量)是无限集的有限描述。这就是它正式的原因。

其他各种方面，如言语或语言的演变都是不同的问题。这些也可以正式化。