介绍有关符号串的一些运算。 符号串的头,尾,固有头和固有尾:如果z-xy是一符号 串,那么x是z的头,y是z的尾,如果ⅹ是非空的,那 么y是固有尾;同样如果y非空,那么x是固有头 举个例子:设z=abc,那么z的头是ea, ab abc除abc外, 其它都是固有头;z的尾是ε,cbc,abcz的固有尾是 C bC 当对符号串zxy的头感兴趣而对其余部分不感兴趣 时,采用省略写法: 如果只是为了强调ⅹ在符号串z中的某处出现,则可 表示为:z=.x.;符号t是符号串z的第一个符号, 则表示为zt
介绍有关符号串的一些运算。 符号串的头,尾，固有头和固有尾：如果z=xy是一符号 串，那么x是z的头，y是z的尾，如果x是非空的，那 么y是固有尾；同样如果y非空，那么x是固有头。 举个例子:设z=abc,那么z的头是ε,a,ab,abc,除abc外， 其它都是固有头；z的尾是ε,c,bc,abc,z的固有尾是 ε,c,bc。 当对符号串z=xy的头感兴趣而对其余部分不感兴趣 时，采用省略写法：z=x…； 如果只是为了强调x在符号串z中的某处出现，则可 表示为：z=…x…；符号t是符号串z的第一个符号， 则表示为z=t…
符号串的连接:设ⅹ和y是符号串,它们的连接xy 是把y的符号写在x的符号之后得到的符号串.由 于e的含义,显然有εX=Xe=X。 ●例如ⅹST,y=abu,则它们的连接xy= STab,看 ly|=3,|xy|=5 符号串的方幂:符号串自身连接n次得到的符号串 an定义为a.aan个aal=a,a2=aa且a0=E 例:若x=AB则 e XI=AB X2=ABAB x3=ABABAB xn=xXn-I=Xn-I X (n>0)
符号串的连接：设x和y是符号串，它们的连接xy 是把y的符号写在x的符号之后得到的符号串. 由 于ε 的含义，显然有ε x=x ε =x。 例如 x=ST，y=abu，则它们的连接xy=STabu，看 出｜x｜=2，｜y｜=3，｜xy｜=5 符号串的方幂：符号串自身连接n次得到的符号串 a n 定义为 aa…aa n个a a1=a, a2=aa且a 0=ε 例；若x=AB 则: x 0 = ε x 1 =AB x 2 = ABAB x 3 = ABABAB x n = xxn-1 = xn-1 x (n>0)
符号串集合:若集合A中所有元素都是某字母表 ∑上的符号串,则称A为字母表Σ上的符号串集合 两个符号串集合A和B的乘积 定义为AB=(xyx∈A且y∈B} 若集合A={ab,cde}集合B={0,1} JI AB=abl, abO, cdeO, cdel) 使用Σ*表示Σ上的一切符号串(包括ε)组成的 集 ∑^称为∑的閉包。 ∑上的除ε外的所有符号串组成的集合记为∑+。 ∑+称为∑的正閉包
符号串集合：若集合A中所有元素都是某字母表 上的符号串，则称A为字母表上的符号串集合。 两个符号串集合A和B的乘积 定义为 AB =xy|xA且yB 若 集合A=ab,cde 集合B = 0,1 则 AB =ab1,ab0,cde0,cde1 使用 * 表示上的一切符号串（包括ε）组成的 集合。 Σ*称为Σ的闭包。 上的除ε外的所有符号串组成的集合记为 + 。 Σ+称为Σ的正闭包
∑+=Σ-{e}=∑Σ=∑∪22∪Σ3∪ 区区{3}=区 例:Σ={a,b} ∑*={ε,a,b,aa,ab,ba,bb,aaa,ab, 2+=a, b aa, ab, ba, bb, aaa, aab
例：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} Σ+={a,b,aa,ab,ba,bb,aaa,aab,…} ...... } { 2 * = { } ...... * * 2 3 = − = = +
卫规式 正规式也称正则表达式,正规表达式 ( regular expression)是 是说明单词的模式 ( pattern)的一种重要的表示法(记号) 是定义正规集的数学工具。我们用以描 述单词符号。下面是正规式和它所表示 的正规集的递归定义
正规式 正规式也称正则表达式,正规表达式 （regular expression）是说明单词的模式 (pattern)的一种重要的表示法（记号）， 是定义正规集的数学工具。我们用以描 述单词符号。下面是正规式和它所表示 的正规集的递归定义