符号串集合:若集合A中所有元素都是某字母 表Σ上的符号串,则称A为字母表Σ上的符号 串集合 两个符号串集合A和B的乘积定义为 AB={xyx∈A且yEB} 若集合A={ab,cde}B={0,1} AI AB =abl, ab0, cdeO, cdel] 使用∑*表示∑上的一切符号串(包括e)组 成的集合。∑*称为∑的闭包 ∑上的除e外的所有符号串组成的集合记为 ∑+。∑+称为∑的正闭包 16
16 符号串集合：若集合A中所有元素都是某字母 表上的符号串，则称A为字母表上的符号 串集合。 两个符号串集合A和B的乘积定义为 AB =xy|xA且yB 若 集合A=ab,cde B = 0,1 则 AB =ab1,ab0,cde0,cde1 使用 * 表示上的一切符号串（包括ε）组 成的集合。Σ*称为Σ的闭包。 上的除ε外的所有符号串组成的集合记为 + 。 Σ+称为Σ的正闭包
∑={e}∪Σ∪Σ2 ∑+=∑-{e}=∑∑=22223… 例:∑={a,b} >*=e, a, b, aa, ab ba, bb, aaa, aab 2+=fa, b, aa, ab, ba, bb, aaa, aab,... 17
17 例：Σ={a,b} Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} Σ+={a,b,aa,ab,ba,bb,aaa,aab,…} { } ...... * 2 = { } ...... * * 2 3 = − = = +
有关定义和记号 语言是由句子组成的集合,是由一组符号所构成的集合。换言 之,字母表Σ上的一个语言是∑上的一些符号串的集合(字母表 ∑上的每个语言是∑*的一个子集) 例如:字母表Σ={a,b},Σ*={ε,a,b,aa,ab,ba,bb,aaa,ab, 集合{ab,abb, aaabbb,…,a"b",} 或表示为{ww∈∑*且w=a,n≥1}为字母表Σ上的一个语言 集合{a,a,aaa,,} 或表示为{Ww∈∑*且w=a,n≥1}为字母表Σ上的一个语 ε}是一个语言 Φ即{}是一个语言。 18
18 有关定义和记号 语言是由句子组成的集合，是由一组符号所构成的集合。换言 之,字母表上的一个语言是上的一些符号串的集合 (字母表 上的每个语言是*的一个子集)。 例如：字母表Σ={a,b} ,Σ*={ε,a,b,aa,ab,ba,bb,aaa,aab,…} 集合{ab,aabb,aaabbb,…,anb n ,…} 或表示为{w|w∈Σ*且w=anb n,n≥1}为字母表上的一个语言。 集合{a,aa,aaa,…} 或表示为{w|w∈Σ*且w=an,n≥1} 为字母表上的一个语 言。 ε是一个语言。 即 是一个语言
给出语言上的有关运算 设L是(∑上的)一个语言M是(∑上的)一个语 言,语言L和M的并,交,差,补是一个语言 语言L和M的并为LM,是一个语言:{wwis in L or is in Mi 如:L1={a,b,…,y,z}M1={1,28,9} L∪M1={a,b,…,y,z,1,2.8,9} 语言L和M的连接是一个语言,记为LM LM={sts∈L且t∈M} 如:L1M1={a1,b1,…,y1,z1,a2,b2a9.9 有L{e}={e}L=L。L的n次连接Ln=LLL 19
19 给出语言上的有关运算 设L是（上的）一个语言,M是（上的）一个语 言, 语言L和M的并，交，差，补是一个语言。 语言L和M的并为 LM，是一个语言: {w|w is in L or is in M} 如： L1 ={a,b,…y,z} M1 ={1,2…8,9 } L1M1={a,b,… y,z，1,2…8,9 } 语言L和M的连接是一个语言，记为 LM LM={st |s∈L且 t∈M} 如： L1M1 ={a1,b1,…y1,z1,a2,b2…a9…z9} 有L ε= εL=L。 L的n次连接L n= LL...L
语言上的运算 语言L的闭包记为L*,L*=L0∪L1∪L2U ■■ Lo=e, Ln=L Ln-i= Ln-lL, n>1 语言L的正闭包记为L+,L+=L1∪L2∪L3 L+〓LL*=L米L L*=L+U{ε} 如:L1={a,b,,y,z}M1={1,2.8,9} (LM1)={a,b,…,y,z,1,2.!8,9} (L1M1)*{a,b,…y,z,1,28,9, aa, la, .xyZ, 6789st L1(L1M1)*{所有字母打头的字母和数字符号 申}
20 语言上的运算 语言L的 闭包记为 L*， L*= L0 L 1 L 2 ... L 0= ε ， L n= L L n-1= L n-1 L,n1 语言L的正 闭包记为 L +， L += L1 L 2 L 3 ... L += LL*= L*L L*= L+ ε 如： L1 ={a,b,…y,z} M1 ={1,2…8,9 } （L1M1）={a,b,… y,z，1,2…8,9 } （L1M1）*={a,b,… y,z，1,2…8,9 ， aa,1a,…xyz,6789st..} L1（L1M1）*={所有字母打头的字母和数字符号 串}