字母表、字符串、字符串集合及运算-软考在线

字母表、字符串、字符串集合及运算



考试要求：掌握

知识路径： > 嵌入式系统软件基础知识 > 嵌入式系统程序设计 > 嵌入式程序设计语言 > 编译器和解释器的基础知识 > 程序设计语言的翻译基础 > 词法分析

（1）字母表∑：元素的非空有穷集合。例如，∑={a，b}。

（2）字符：字母表∑中的一个元素。例如，∑上的a或b。

（3）字符串：字母表∑中字符组成的有穷序列。例如，a、ab、aaa都是∑上的字符串。

（4）字符串的长度：字符串中的字符个数。例如，|aba|=3。

（5）空串ε：由0个字符组成的序列。例如，|ε|=0。

（6）连接：字符串S和T的连接是指将串T接续在串S之后，表示为S·T，连接符号“·”可省略。显然，对于字母表∑上的任意字符串S，S·ε=ε·S=S。

（7）空集：用符号Φ表示。

（8）∑*：指包括空串ε在内的∑上所有字符串的集合。例如，设∑={a，b}，∑*={ε，a，b，aa，bb，ab，ba，aaa，…｝。

（9）字符串的方幂：把字符串α自身连接n次得到的串，称为字符串α的n次方幂，记为αⁿ。α⁰=ε，αⁿ=ααⁿ^-1=αⁿ^-1α（n>0）。

（10）字符串集合的运算：设A、B代表字母表∑上的两个字符串集合。

.或（合并）：A∪B={α|α∈A或α∈B｝。

.积（连接）：AB=｛αβ|α∈A且β∈B｝。

.幂：Aⁿ=A·Aⁿ^-1=Aⁿ^-1·A（n>0），并规定A⁰={ε}。

.正则闭包+：A⁺=A¹∪A²∪A³∪…

.闭包*：A*=A⁰∪A⁺。显然，∑*=∑⁰∪∑¹∪∑²∪…

更多复习资料
请登录电脑版软考在线 www.rkpass.cn

京B2-20210865 | 京ICP备2020040059号-5