Skip to Main Content
计算机科学导论:跨学科方法
book

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

by 罗伯特 塞奇威克, 凯文 韦恩
August 2021
Beginner to intermediate content levelBeginner to intermediate
450 pages
19h
Chinese
Pearson
Content preview from 计算机科学导论:跨学科方法

5.1 形式语言

为了给接下来介绍的重要理论问题奠定基础,开始之前,我们先定义一些非常简单的抽象概念。接下来,我们要介绍一个广泛使用的软件工具及其相关机制,并附上一些应用程序。

基本定义 我们从符号(symbol)这个抽象概念开始,这个概念是我们构建后继内容的基础。在数学上,符号可以是能够相互区分的任一标识。在刚开始时,把符号当成一个字符或者数字元素是非常有帮助的。下面我们阐明基本定义。

定义:一个符号集(或字母表)表示有限个符号的一个集合。

定义:一个字符串表示有限符号集的一个序列。

定义:一种形式语言是字符串的一个集合(有可能是无限大的),这些字符串都是由同一个符号集合的元素构成。

你可能会觉得这些定义中的前两个对你来说非常简单和熟悉,因此没有必要给出它们的定义。但是它们定义的这些概念是非常基本的,有一个清晰且明确的定义十分重要。第三个定义对于你来说可能是全新的,所以你应该着重理解它。这是一个简单的定义,而且从现在开始我们可以将术语“字符串的集合”和“形式语言”互换使用。

例如,十进制数字集就是一个你十分熟悉的符号集:{0,1,2,3,4,5,6,7,8,9}。像2147483648这样一个整数是由上面符号集组成的一个字符串,所以我们可以将形式语言正整数(positive integer)定义成由这个符号集构成的不以0为开头的字符串的集合。

二进制字符串。接下来我们分析一个二进制字符串的集合(由二进制符号集组成的形式语言),它仅仅涉及两个符号。具体这两个符号是什么并不重要,我们可以使用{0,1},但是在本章中我们使用{a,b}来避免与整数的0和1产生混淆。确定一种形式语言的最简单的方式就是枚举它的字符串。这是一种可以精确确定形式语言的方法,但我们通常还会用非形式的描述来描述语言。例如,我们可以用“长度为3的二进制字符串”这样的非形式描述来标识形式语言(字符串的集合):{aaa,aab,aba,abb,baa,bab,bba,bbb}。 ...

Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Start your free trial

You might also like

数据科学之编程技术:使用R进行数据清理、分析与可视化

数据科学之编程技术:使用R进行数据清理、分析与可视化

迈克尔 弗里曼, 乔尔 罗斯
C语言核心技术(原书第2版)

C语言核心技术(原书第2版)

Peter Prinz, Tony Crawford

Publisher Resources

ISBN: 9787111641414