编译原理

符号串的运算
　　符号串的长度：符号串中符号的个数.符号串s的长度记为|s|。 ε的长度为0
　　连接：符号串x、y的连接,是把y的符号写在x的符号之后得到的符号串xy 如 x=ab,y=cd 则 xy=abcd 有εa = aε
　　方幂：符号串自身连接n次得到的符号串aⁿ 定义为 aa…aa n个a a¹=a, a²=aa则a⁰=ε使用∑^* 表示S上的一切符号串（包括ε）组成的集合。∑^*称为Σ的闭包。
　　∑上的除ε外的所有符号串组成的集合记为∑⁺ 。 ∑⁺ 称为Σ的正闭包。
语言
　　语言是由句子组成的集合，是由一组符号所构成的集合。换言之，
　　字母表∑上的一个语言是∑上的一些符号串的集合 (字母表∑上的每个语言是∑^* 的一个子集)。例如：若有字母表Σ={a,b} ,则∑^*={ε,a,b,aa,ab,ba,bb,aaa,aab,…}
　　根据上述关于语言的概念，我们说集合A={ab,aabb,aaabbb,…,aⁿ bⁿ,…}
　　为字母表∑上的一个语言，也可以把集合A描述为{w|w∈∑^*且w=aⁿ bⁿ,n≥1}。
　　我们说集合B={a,aa,aaa,…}为字母表∑上的一个语言，同样也可以把集合B描述为{w|w∈∑^*且w=aⁿ,n≥1}。
注意：
　　{ε}是一个语言。
　　Φ 即{ }是一个语言。
　　给出有关语言的运算
　　既然将语言定义为一个集合，那么有关集合的运算也适合语言。即：设L是（∑上的）一个语言,M是（∑上的）一个语言，则语言L和M的并，交，差，补是一个语言。
　　语言L和M的并表示为 L∪M，是一个语言，满足: {w|w is in L or is in M}
　　如： L1 ={a,b,…y,z} M1 ={1,2…8,9 } L1∪M1 ={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ⁿ= LL...L
　　语言L的闭包记为 L^*　L^* = L⁰ ∪ L¹ ∪ L² ∪... L⁰= {ε} ，
　　　　　　　　　Lⁿ= L L^n-1 = L^n-1 L,n≥1
　　语言L的正闭包记为 L⁺， L⁺= L¹ ∪ L² ∪ L³ ...
　　　　　　　　　　L⁺ = LL^*= L^*L
　　　　　　　　　　L^* = L⁺ ∪ {ε}
　　如：（L1∪M1）^*={a,b,… y,z，1,2…8,9 ，aa,1a,…xyz,6789st..}
　　　　L1（L1∪M1）^*={所有字母打头的字母和数字符号串}