首页 理论教育符号串及其运算符号集合的定义与性质

符号串及其运算符号集合的定义与性质

【摘要】:典型的符号有字母、数字、各种标点符号和各种运算符。定义B-7(符号串)由符号集∑中0个或多个符号相连而成的有穷序列称为∑上的符号串。包括空串在内的∑上符号串的全体记为∑。如果x是符号串,把x自身连接n(n≥0)次得到的符号串x,称为x的n次方幂,记作xn。定义B-11设V是符号集∑上的一个符号串集合,则V的正闭包定义为V的闭包定义为例如:V={a,b},则V+={a,b,aa,ab,ba,bb,aaa,aab,…

定义B-6(符号集)符号集∑是符号元素的非空有穷集合。典型的符号有字母、数字、各种标点符号和各种运算符。

例如,集合{abc,+,∗}是一个含有5个符号的符号集,而符号集{0,1}只有两个符号。

定义B-7(符号串)由符号集∑中0个或多个符号相连而成的有穷序列称为∑上的符号串。特殊地,不包括任何符号的符号串称为空串,记作ε。包括空串在内的∑上符号串的全体记为∑∗。

例如,有符号集{abc,+,∗},则abc+,∗,aaaba+a∗,aaac+∗等等都是该符号集上的符号串。

定义B-8(符号串的长度)若x是符号集∑上的符号串,那么,其长度指x中所含符号的个数,记为x

例如:abc=3,abc+∗abc=8,而ε=0。

“连接”和“闭包”是符号串操作中的两种基本运算。

定义B-9(符号串的连接)假定xy是符号集∑上的符号串,则把y的各个符号依次写在x符号串之后得到的符号串称为xy的连接,记作xy

例如:∑={abc},x=abcy=cba,那么,xy=abccba

如果x是符号串,把x自身连接n(n≥0)次得到的符号串978-7-111-38182-2-Chapter09-2.jpgx,称为xn次方幂,记作xn。当n=0时,x0=ε。当n≥1时,xn=xxn-1=xn-1x

定义B-10(集合的乘积运算)设AB是符号集∑上的两个符号串集合,则AB的乘积定义为

其中,A0={ε}。当n≥1时,An=An-1A=AAn-1

定义B-11(集合的闭包运算)设V是符号集∑上的一个符号串集合,则V的正闭包定义为

V的闭包定义为

例如:V={ab},则

V+={abaaabbabbaaaaab,…}

V∗={εabaaabbabbaaaaab,…}