符号串集合：若集合A中所有元素都是某字母 表Σ上的符号串，则称A为字母表Σ上的符号 串集合。 两个符号串集合A和B的乘积定义为 AB={xyx∈A且y∈B} 若集合A={ab,cde}B={0,1} AB ={ab1,ab0,cde0,cde1} 使用∑*表示Σ上的一切符号串（包括ε）组 成的集合。∑*称为∑的闭包。 Σ上的除ε外的所有符号串组成的集合记为 ∑+。∑+称为∑的正闭包。 16
16 符号串集合：若集合A中所有元素都是某字母 表上的符号串，则称A为字母表上的符号 串集合。 两个符号串集合A和B的乘积定义为 AB =xy|xA且yB 若 集合A=ab,cde B = 0,1 则 AB =ab1,ab0,cde0,cde1 使用 * 表示上的一切符号串（包括ε）组 成的集合。Σ*称为Σ的闭包。 上的除ε外的所有符号串组成的集合记为 + 。 Σ+称为Σ的正闭包
∑={8}U2U∑2U.. =∑*-{8}=Σ=2J∑2JΣ3d.. 例：∑={a,b} ∑*={e,a,b,aa,ab,ba,bb,aaa,aab,…} ∑t={a,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},∑*={e,a,b,aa,ab,ba,bb,aaa,aab,…} 集合{ab,aabb,aaabbb,..,abn,.} 或表示为{ww∈∑*且w=ab",n≥1}为字母表∑上的一个语言。 集合{a,aa,aaa,.} 或表示为{ww∈∑*且w=an,n≥l}为字母表Σ上的一个语 言。 {e}是一个语言。 Φ即{}是一个语言。 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的并为LUM,是一个语言：{wwis in L or is in M} 如：1={a,b,y,z} M1={1,2..8,9} L1UM={a,b,.y,z,1,2..8,9} 语言L和M的连接是一个语言，记为LM LM={st|s∈L且t∈M} 如：LM1={a1,b1,…y1,z1,a2,b2..a9..z9} 有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*=L0UL1UL2U… Lo={8,Ln=L Ln-1=Ln-i L,n21 语言L的正闭包记为L+,L+=L1UL2UL3.: L+=LL*=L*L L*=L+ e 如：L1={a,b,…y,z}M1={1,2.8,9} (L1UM1)={a,b,…y,z,1,2.8,9} (L1UM1)*={a,b,.y,z,1,2.8,9, aa,1a,...xyz,6789st..} L1(LUM1)*={所有字母打头的字母和数字符号 串} 20
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）*={所有字母打头的字母和数字符号 串}