基本概念 符号和字母表p20 加符号（元素）可以相互区别的记号 0例ab01 口字母表符号的非空有穷集合 口例∑={0,1}二进制数语言的字母表 A={a,b}由符号a和b组成的字母表 口字母表包含语言中所允许出现的一切符号 口一种程序设计语言的字母表是该语言的基本字符集 口C语言是C程序的集合 口C程序是在C基本字符集上定义的，按一定规则构成 的符号串 15
15 基本概念 符号和字母表 p20 符号(元素) 可以相互区别的记号 例 a b 0 1 字母表 符号的非空有穷集合 例∑={0，1} 二进制数语言的字母表 A={a，b} 由符号a和b组成的字母表 字母表包含语言中所允许出现的一切符号 一种程序设计语言的字母表是该语言的基本字符集 C语言是C程序的集合 C程序是在C基本字符集上定义的，按一定规则构成 的符号串
基本概念符号串p20 ▣符号串由字母表中的符号所组成的任何有穷序 列称为该字母表上的符号串 口例001110是字母表∑上的符号串 a,b,aa,bb,abb,bba,.都是字母表A上的符号 串 口注意符号串中符号的顺序是重要的 例ab不同于ba 口符号串的长度符号串中符号的个数 ▣例x=001110 则x长度x=6 0 空串（ε一空字）长度为0的符号串 0e=0 4 ☒ 6
16 基本概念 符号串 p20 符号串 由字母表中的符号所组成的任何有穷序 列称为该字母表上的符号串 例 001110是字母表∑上的符号串 a,b,aa,bb,abb,bba,.都是字母表A上的符号 串 注意 符号串中符号的顺序是重要的 例 ab不同于ba 符号串的长度 符号串中符号的个数 例 x=001110 则x长度|x|=6 空串 (ε—空字) 长度为0的符号串 |ε|=0
关于符号串操作 口运算设x是某字母表上的符号串 0连接（并置）x=123,y=45那么xy=12345 o方幂：x的n次方幂即将n个x连接 x0=8 x1=x x2=xx. o子符号串v是xvy的子符号串，v非空 o头，尾x是xy的头，y是xy的尾 迎 17
17 关于符号串操作 运算 设x是某字母表上的符号串 连接(并置) x=123, y=45那么xy=12345 方幂：x的n次方幂即将n个x连接 x 0=ε x1=x x2=xx. 子符号串 v是xvy的子符号串，v非空 头，尾 x是xy的头，y是xy的尾
符号串集合 0符号串集合 口若集合A中的一切元素都是某字母表上的符号 串，则称A为该字母表上的符号串的集合 0例∑={0,1}是字母表，其中0,1为符号 则D={0,1}其中0,1为符号串 E={ε，0,1,00,01,10,11,000，.} 是∑上的符号串集合 口特别空集记为中={}注意与e区别 18 ☑)
18 符号串集合 符号串集合 若集合A中的一切元素都是某字母表上的符号 串，则称A为该字母表上的符号串的集合 例 ∑={0，1}是字母表,其中0,1为符号 则D={0,1} 其中0,1为符号串 E= {ε, 0,1,00,01,10,11,000, .} 是∑上的符号串集合 特别 空集记为ф ={ } 注意与ε区别
符号串集合的运算p21 o乘积UV={aBa∈U且B∈V} a例A={a,b}B={c,d} 则AB={ac,ad,bc,bd} o方幂V的n次方幂就是将n个V相乘 a设A={a,b} A0={e} A1=A ={a,b} A2=AA=aa,ab,ba,bb} 0An=AA.A(n个A的乘积) 所有由A中符号构成的长度为n的符号串的集合 19
19 符号串集合的运算 p21 乘积 UV = {αβ|αU且βV} 例 A={a，b} B={c，d} 则AB={ac，ad，bc，bd} 方幂 V的n次方幂就是将n个V相乘 设A={a，b} A 0={ε} A 1=A ={a，b} A 2=AA={aa，ab，ba，bb} A n=AA.A (n个A的乘积） 所有由A中符号构成的长度为n的符号串的集合