计算机科学导论：跨学科方法

问答环节

问：符号的定义是什么？

答：符号是形式语言的基本抽象构件。从一个数学家的角度来看，符号的定义并没有什么区别：对形式语言的研究就是对符号序列集合的研究。从科学家或工程师的角度看，符号是至关重要的，因为它们构成了形式语言抽象世界与我们使用形式语言的真实世界之间微弱的联系。一个符号可能是真实世界中的任何一个东西，比如一个触发器、一个基因、一个神经元、一个分子，或者是抽象世界中的任何一个东西，比如一位、一个数字、一个小写字母或者一个Unicode符号。

问：交集也是集合的基本操作之一。为什么不把交集也作为正则表达式基本定义的一部分呢？

答：这是个好问题。由于语言仅仅是一些集合，所以很多东西可以从集合理论延续到正则表达式中。你可以为语言定义交集，而且两个正则语言的交集语言也是正则的（见练习5.1.37）。

问：那些用于指定元符号的转义字符有点令人困惑。可以使用缩写来描述它们吗？

答：恰恰相反，只会写得更长。当你在Java字符串文本里描述一个正则表达式时，你需要另一个级别的转义来转义字符元符号。例如，你需要输入“\\s”来代表一个空格字符，输入“\\\\”来代表一个单斜杠字符。有时候你需要对命令行中的特殊字符进行转义。例如，美国货币的正则表达式，它的命令行参数使用了“\\\$”来表示一个美元符号，使用“\\.”来表示一个小数点。

问：学习NFA有什么意义？它们比DFA更难想象，我不清楚它的优势在哪。

答：我们使用NFA来证明克林定理，并且使用它们可能实现正则表达式识别问题。另一个原因是NFA往往比DFA拥有更少的状态。尝试为倒数第10个符号为1的所有字符串构建一个DFA。你会发现即使构建这种语言的NFA仅仅需要10种状态，却无法在512种状态内构建一个DFA。

问：如何才能写出一个正则表达式来指定包含空字符串的单元素集合？ ...