语言( LANGUAGES) ◇举俐:设T={a,b} 则L1={abn|n21} L3={b|k是质数} 2={e}只有一个空句子的语言 L4={}=@空语言 均为字母表T上的语言。 ◇由语言的定义知语言是集合,对于集合的运算可 应用于对于语言的计算。如并,交,补,差。 College of Computer Science& Technology, BUPT 11
College of Computer Science & Technology, BUPT 11 语 言 （Languages） 举例：设T = {a，b} 则 L1 = {anbn | n≥1} L3 = { bk | k 是质数} L2 ={ε} 只有一个空句子的语言 L4 = { } = Φ 空语言 均为字母表T上的语言。 由语言的定义知语言是集合，对于集合的运算可 应用于对于语言的计算。如并，交，补，差
语言的基本运算 ◇语言的积: 两个语言L1和L2的积L1L2是由L1和L2中的字符 串连接所构成的字符串的集合。即L1中所有字符 串分别与L2中的字符串连接得到的集合。 设T={a,b},L1和L2是T上的语言。 L1=ab, ba L2 aa, bb] n L1 L2=abaa, abbb, baaa, babb] L1=aaab, aaba, bab, bbbal ■L1L2≠L2L1语言的积不可交换。 College of Computer Science& Technology, BUPT
College of Computer Science & Technology, BUPT 12 语言的基本运算 语言的积： 两个语言L1 和L2的积L1 L2是由L1和L2中的字符 串连接所构成的字符串的集合。即L1中所有字符 串分别与L2中的字符串连接得到的集合。 设T={a, b}， L1和 L2是T上的语言。 L1 ={ab, ba} L2 ={aa, bb} 则 L1 L2 ={abaa, abbb, baaa, babb} L2 L1 ={aaab, aaba, bbab, bbba} ◼ L1 L2 ≠ L2 L1 语言的积不可交换