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

Question

在维基百科的https://www.wikiwand.com/en/Formal_language上，我找到了正式语言的定义：

在数学、计算机科学和语言学中，正式语言是一组可以受到特定规则限制的符号字符串。

这听起来非常抽象，我很难想象有任何不符合这个定义的语言。是否有人对什么是非正式语言以及它为什么不符合该定义有什么想法？

- Hanfei Sun

---

我投票关闭此问题，因为它不属于在SO上应用该术语的编程范畴内。 - High Performance Mark

@HighPerformanceMark，这太糟糕了，因为我认为最近SO上有很少有趣的问题。 - Z boson

Answer 1

让我先回答你的问题。一个不好的正式语言的反例就是“自然”语言。英语和斯洛文尼亚语就是例子。他加洛语和塔里菲特柏伯语也是。不幸的是，语言学家似乎没有一个所有人都同意的自然语言定义。

诺姆·乔姆斯基在他1956年的论文“Three Models for the Description of Language”中试图使用无上下文语法模拟自然语言。他在那篇论文中发明（或发现，如果你喜欢这样说）了它们；虽然它们对于模拟英语语言并不有用，但它们彻底改变了计算机科学。

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

例子包括所有有效的C程序，所有有效的HTML文件，所有有效的XML文件，所有“平衡”括号字符串（例如（），（）（），（（））（）（），...），所有总是停机的确定性图灵机的集合（某些编码下的代码），可以用k种颜色着色的所有简单图形的集合（实际上是它们在某些编码下的代码），所有以1开头和结尾的二进制字符串等等。

有些正则表达式（或等价的DFA）易于识别；有些不可能使用DFA识别，但可以使用PDA识别（或等价地，可以用上下文无关文法描述）；其他一些不适合这样的描述，但可以通过图灵机识别；有些甚至不能被图灵机识别（称为不可计算）。

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

对于这个主题的良好介绍，我强烈推荐Hopcroft等人的杰出著作《自动机理论、语言和计算导论》。

- blazs

Answer 2

英语不是一种正式的语言。它不仅仅是一组字符串；它有口语形式、随时间演变、方言等各种正式语言所没有的东西。正式语言无法在一年中从一个词汇中获得“电子邮件”这个单词。

- user2357112

Answer 3

一种语言是由给定符号组成的序列集合。它可以是有限的或无限的（例如，英语句子的集合是无限的，即使有些句子太长了，甚至母语人士也无法理解）。如果它是有限的，那么对它的任何描述都是一个正式的定义。

如果语言是无限的，比如涉及数字、两个二进制运算符“+”、“*”和变量的算术表达式语言，那么你不可能列出所有属于该语言的字符串，但有时候（见下面blazs的评论），你可以给出一个有限的规则集作为形式化的描述。

E：= NUM | v | E '+' E | E '*' E

（其中NUM是数字序列，v是变量）是一个无限集合的有限描述。这就是它的形式化之处。

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

- user1666959

---

你不能总是使用上下文无关文法来描述形式语言... 有时候你需要更强大的工具。 - blazs

我从未说过产生式系统的左侧必须是单个符号。如果您愿意，它甚至可以是 epsilon。 - user1666959

好的，让 T 成为所有确定性图灵机的集合，在有限步骤后始终停止（在每个输入上）。给我一个描述。我会等着的。 :) - blazs

当你说你会等待，是不是意味着你甚至不会吃东西？ :) 我在可形式化性的陈述中添加了“有时候”，以反映并非所有集合都是易处理的。 - user1666959