2.2符号和符号串p20 n字母表 n符号串 n符号串的头尾 n符号串的连接 n符号串的方幂 n符号串的集合
11 2.2 符号和符号串 p20 n 字母表 n 符号串 n 符号串的头尾 n 符号串的连接 n 符号串的方幂 n 符号串的集合
基本概念 符号和字母表p20 n符号（元素）可以相互区别的记号 u例ab01 n字母表（语言的基本字符集）非空有穷集 u例∑={0,1}二进制数语言的字母表 A={a,b}由符号a和b组成的字母表 u字母表包含语言中所允许出现的一切符号。 一种程序设计语言的字母表是该语言的基本字符集合。 uC语言字符集：大小写字母a-zA-Z、数字0-9、空白符、标 点和特殊符号。 C程序是在C基本字符集上按一定规则构成的符号串。符合 词法和语法规则的符号串。 12 可应
12 基本概念 符号和字母表 p20 n 符号(元素) 可以相互区别的记号 u 例 a b 0 1 n 字母表（语言的基本字符集）非空有穷集 u 例∑={0，1} 二进制数语言的字母表 A={a，b} 由符号a和b组成的字母表 u 字母表包含语言中所允许出现的一切符号。 n 一种程序设计语言的字母表是该语言的基本字符集合。 u C语言字符集：大小写字母a-z A-Z、数字0-9、空白符、标 点和特殊符号。 u C程序是在C基本字符集上按一定规则构成的符号串。符合 词法和语法规则的符号串
基本概念 符号串和符号串集合p20 符号串：由字母表中符号所组成的任何有穷序列。 u例01,110,001110是字母表∑={0,1}上的符号串。 u注意符号串中符号的顺序是重要的，110不同于011。 n符号串的长度：符号串中符号的个数。 u例x=001110,则x长度|x=6。 n空串e:长度为0的符号串，e|=0 n符号串集合：集合中的一切元素都是某字母表上的符号串。 u例∑={0,1}是字母表，其中0,1为符号 则字符串集合D={0,1}其中0,1为符号串 字符串集合E={e,0,1,00,01,10,11,000,.} 是∑上的符号串集合。 u特别空集记为中={}，注意与e、{e}区别。 ☒区 13
13 基本概念 符号串和符号串集合 p20 n 符号串：由字母表中符号所组成的任何有穷序列。 u 例01，110，001110是字母表∑={0,1}上的符号串。 u 注意符号串中符号的顺序是重要的，110不同于011。 n 符号串的长度：符号串中符号的个数。 u 例x=001110，则x长度|x|=6。 n 空串ε：长度为0的符号串，|ε|=0 n 符号串集合：集合中的一切元素都是某字母表上的符号串。 u 例 ∑={0，1}是字母表,其中0,1为符号 则字符串集合D={0,1} 其中0,1为符号串 字符串集合E= {ε, 0,1,00,01,10,11,000, .} 是∑上的符号串集合。 u 特别 空集记为ф ={ }，注意与ε、{ε}区别
符号串集合闭包和正闭包 p34 设字母表A={a,b},符号串集合V={a,b}。 n符号串集V的闭包V*={a,b}* uV*={s}Ufa,b}Ufaa,ab,ba,bb}U. =e,a,b,aa,ab,ba,bb,aaa,. uV的闭包*是V上的所有符号串（包括空串ε）的集合 n符号串集V正闭包v={a,b}+ uV+=fa,b}Ufaa,ab,ba,bb}U. =fa,b,aa,ab,ba,bb,aaa,. uV的正闭包V+是V上的所有的非空符号串的集合
14 符号串集合闭包和正闭包 p34 设字母表A={a，b}，符号串集合V={a，b}。 n 符号串集V的闭包 V *= {a,b} * u V * ={ε}∪{a，b} ∪{aa，ab，ba，bb}∪. ={ε，a，b，aa，ab，ba，bb，aaa，.} u V的闭包V *是V上的所有符号串(包括空串ε)的集合 n 符号串集V正闭包 V += {a,b}+ u V + ={a，b} ∪{aa，ab，ba，bb}∪. ={a，b，aa，ab，ba，bb，aaa，.} u V的正闭包V +是V上的所有的非空符号串的集合
语言的概念 n语言 u某个字母表∑上的符号串集合，是∑*的一个子集。 u 例有字母表∑={0,1} ∑*={0,1}*={e,0,1,00,01,10,11,000,001,} u则∑*的一个子集{1,11,111,1111，.}是一种语言。 ∑*的一个子集{0,1,00,01,10,11,000,001，.}是二进制语言。 nC语言 u字母表={所有C语言基本字符}一C语言基本字符集。 u所有C语言基本字符}*是符号串集合。 u符合C语言语法规则的符号串集合{所有C语言基本字 符}*的子集就是C语言。 章节目录 15 ☒
15 语言的概念 n 语言 u 某个字母表∑上的符号串集合，是∑*的一个子集。 u 例有字母表∑={0，1} ∑* ={0,1}* ={ε,0,1,00,01,10,11,000,001,.} u 则∑*的一个子集{1,11,111,1111,.}是一种语言。 ∑*的一个子集{0,1,00,01,10,11,000,001,.} 是二进制语言。 章节目录 n C语言 u 字母表={所有C语言基本字符}—C语言基本字符集。 u {所有C语言基本字符} *是符号串集合。 u 符合C语言语法规则的符号串集合{所有C语言基本字 符} *的子集就是C语言