《半群与独异点》PPT课件.ppt

Peking University,1,第十六章 半群与独异点 Semigroup and Monoid, Peking University,2,半群与独异点的定义, Peking University,3,一. 半群(Semi-group) 1.定义：S是个非空集合， 是S上的二元运算，如果在 S上满足封闭性、可结合性，则称是半群。 例. , , , ,都是半群。, Peking University,4,二. 独异点 ( Monoid ),1.独异点定义：设是个半群,如果对有幺元(identity) 。则称是个独异点，也称它是含幺半群。 , 幺元是0 , 幺元是1 ,幺元是B ,幺元是 幺元是 所以它们都是独异点。 2.交换独异点 是独异点，如是可交换的，则称它是交换独异点。 例. ,都是交换独异点。, Peking University,5,半群与独异点的幂运算, Peking University,6,证明：anam = an+m (an)m = anm 证:(1) 固定n,归纳于m 若m=1,则xnox1=xnox=xn+1 假设对m=k有xnoxk=xn+k成立,则对m=k+1有 xnoxk+1= xno(xkox1)= (xnoxk)ox1=xn+k+1 根据数学归纳法，对一切n,mZ+，结论为真, Peking University,7,证明：(an)m = anm 证:(2) 固定n,归纳于m 若m=1,则(xn)1=xn=xn*1 假设对m=k有(xn)k=xn*k成立,则对m=k+1有 (xn)k+1= (xn)koxn= xn*koxn=xnk+n=xn(k+1) 根据数学归纳法，对一切n,mZ+，结论为真, Peking University,8,实例, Peking University,9,实例, Peking University,10,定理16.2,任何半群都可以扩张成独异点 证：任取e使得e不属于S，令S=Se,且定义o运算为 任意 x,yS,x o y=xoy, 任意 xS,x oe=eox=x eoe=e 可知o运算在S上是可结合的，且单位元为e,因此为独异点, Peking University,11,子半群、子独异点,1子半群：半群的子代数 2. 子独异点：独异点的子代数 3. 判别: 非空子集B， B对于V中的运算（含0元运算）封闭., Peking University,12,子半群、子独异点,定理：若干子半群的非空交集仍为子半群； 若干子独异点的交集仍为子独异点. 证明:Si是子群S的子半群的非空交集，任意x,ySi，则x,y属于每个Si ,因为Si是S的子半群，所以xySi，这就证明了xySi ，则 Si是S的子代数，即子半群. Vi是独异点V的子独异点的交集，设V的单位元为e，因为Vi是V的子代数，eVi，所以eVi ，再根据上面证明，Vi是V的子独异点., Peking University,13,若干个子半群的并不一定是子半群 例： 2Z=2k|k Z， 3Z=3k|k Z 但2Z3Z不是的子半群, Peking University,14,重要的子半群-子集合B生成的子半群 S为半群，B是S的非空子集,则S的所有包含B的子半群的交仍是S的子半群，称为由B生成的子半群。 V=, BS,包含B的最小的半群 =A | A是S的子半群，BA = , 令Bn=b1b2bn |biB,i=1,2,n,定义16.4:, Peking University,15,实例,例 V=半群， B=4,6, 则=4i+6j | i,j N, i和j 不同时为0 =4,6,8,10,12,14,16,=2Z+2, Peking University,16,半群独异点的直积、商代数、同态, Peking University,17,半群的同态性质, Peking University,18,独异点的表示定理, Peking University,19,实例, Peking University,20,形式语言与自动机,自动机的概念在1936年图灵(Turing)提出，他设计的自动机叫图灵机。后来，丘奇(Church)提出一个假设：图灵机的计算能力代表着可实现的计算装置的基本范围。可以证明，任何能在电子计算机上实现的计算都能用图灵机进行描述。 形式语言约于1956年问世，N.乔姆斯基(Chomsky)给出文法的数学模型，1959年他将文法分为4类，0型(无限止)文法，1型(上下文有关)文法，2型(上下文无关)文法，3型(正则)文法。分别与图灵机、不确定的线性界限自动机、不确定的下推自动机和有限自动机等价。形式语言和编译原理密切相关。, Peking University,21,形式文法,形式语言中任一句子类似于自然语言中的句子，可逐次应用文法规则构造而成 Jack and Jill ran up the hill. x:=(1+(0+x), Peking University,22,例1：规则,1 = 2 = 3 = 4 = 5 =and 6 =Jack 7 =Jill 8 = 9 =ran 10= 11 =up 12 =the 13 =hill,Jack and Jill ran up the hill., Peking University,23,例2：ALGOL语言规则,1 = 2 =:= 3 =x 4 = 5 = 6 =() 7 = + 8 =1 9 =0 10 =,x:=(1+(0+x), Peking University,24,文法主要组成部分,字母表：表中的字母为终结符，最终的句子中只能含有这些字母，也称为终结符集 非终结符集：一个中间字母集 文法规则或生成式集合, Peking University,25,形式文法,形式文法：四元组G= VN是非终结符集 VT是终结符集 P是生成式集 A（ 为串，A为非终结符） 是开始符, Peking University,26,文法分类,无限止(0型)文法 | 缩减规则 上下文有关(1型)文法 A,要求非空 上下文无关(2型)文法 A 正则(3型)文法 A(至多含有一个非终结符) AaB，Aa，右线性文法 ABa，Aa，左线性文法,27,16.2有穷自动机(有限状态自动机),有穷半自动机: 三元组M=,Q为有穷状态集, 为有穷输入字符表,： QQ为状态转移函数 有穷自动机：五元组M=, 为有穷输出字符表,: Q 为输出函数, Peking University,28,扩展的有穷自动机,有穷半自动机: 三元组M*=,Q为有穷状态集, *为上的串的集合, * ：Q*Q为状态转移函数 有穷自动机：五元组M*=, *为上的串的集合,*: Q* *为输出函数, Peking University,29,任意给定半自动机，可以得到一个对应的独异点；任意给定独异点，可以得到一个对应的半自动机。 定理16.8 定理16.9, Peking University,30,定理16.8,半自动机M*=，对于任意*，定义f:QQ, f(q)=*(q, ), 令S=f| *是所有这样定义的函数的集合，是函数的合成运算，则TM=是一个独异点。, Peking University,31,定理16.9 设T=是独异点，则存在半自动机M，且M对应的独异点TM同构于T。 构造性证明 M=, Q=S, ：SSS，()=ba fa: SS， fa(q)=(),A=fa|aS,则TM=是M对应的独异点, Peking University,32,例16.3,T=是独异点，S=1,-1,