《半群与独异点》ppt课件

《《半群与独异点》ppt课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第十六章半群与独异点SemigroupandMonoid1©PekingUniversity半群与独异点的定义2©PekingUniversity一.半群(Semi-group)1.定义：S是个非空集合，是S上的二元运算，如果在S上满足封闭性、可结合性，则称是半群。例.,,,,,,,,都是半群。3©PekingUniversity二.独异点(Monoid)1.独异点定义：设是个半群,如果对有幺元(identity)。则称

2、是个独异点，也称它是含幺半群。,幺元是0,幺元是1,幺元是B,幺元是Φ幺元是Φ所以它们都是独异点。2.交换独异点是独异点，如是可交换的，则称它是交换独异点。例.,,,都是交换独异点。4©PekingUniversity半群与独异点的幂运算5©PekingUniversity证明：anam=an+m(an)m=anm证:(1)固定n,归纳于m若m=1,则xnox1=xnox=xn+1假设对m=k有

3、xnoxk=xn+k成立,则对m=k+1有xnoxk+1=xno(xkox1)=(xnoxk)ox1=xn+k+1根据数学归纳法，对一切n,mZ+，结论为真6©PekingUniversity证明：(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,mZ+，结论为真7©PekingUniversity实例8©PekingUniversity实例9©PekingUni

4、versity定理16.2任何半群都可以扩张成独异点证：任取e使得e不属于S，令S’=S{e},且定义o’运算为任意x,yS,xo’y=xoy,任意xS,xo’e=eo’x=xeo’e=e可知o’运算在S’上是可结合的，且单位元为e,因此为独异点10©PekingUniversity子半群、子独异点1．子半群：半群的子代数2.子独异点：独异点的子代数3.判别:非空子集B，B对于V中的运算（含0元运算）封闭.11©PekingUniversity子半群、子独异点定理：若干子半群的非空交集仍为子半群；若干子

5、独异点的交集仍为子独异点.证明:Si是子群S的子半群的非空交集，任意x,ySi，则x,y属于每个Si,因为Si是S的子半群，所以xySi，这就证明了xySi，则Si是S的子代数，即子半群.Vi是独异点V的子独异点的交集，设V的单位元为e，因为Vi是V的子代数，eVi，所以eVi，再根据上面证明，Vi是V的子独异点.12©PekingUniversity若干个子半群的并不一定是子半群例：2Z={2k

6、kZ}，3Z={3k

7、kZ}但2Z3Z不是的子半群13©PekingUniversity重要的子半群---子集合B生成

8、的子半群S为半群，B是S的非空子集,则S的所有包含B的子半群的交仍是S的子半群，称为由B生成的子半群。V=,BS,包含B的最小的半群={A

9、A是S的子半群，BA}=,令Bn={b1b2…bn

10、biB,i=1,2,…,n}定义16.4:14©PekingUniversity实例例V=半群，B={4,6},则={4i+6j

11、i,jN,i和j不同时为0}={4,6,8,10,12,14,16,…}=2Z+{2}15©PekingUniversity半群独异点的直积、商代数、同态16©PekingUniversity半

12、群的同态性质17©PekingUniversity独异点的表示定理18©PekingUniversity实例19©PekingUniversity形式语言与自动机自动机的概念在1936年图灵(Turing)提出，他设计的自动机叫图灵机。后来，丘奇(Church)提出一个假设：图灵机的计算能力代表着可实现的计算装置的基本范围。可以证明，任何能在电子计算机上实现的计算都能用图灵机进行描述。形式语言约于1956年问世，N.乔姆斯基(Chomsky)给出文法的数学模型，1959年他将文法分为4类，0型(无限止)文法，1型(上下文有关)文法，2型(上下文无关)文法

13、，3型(正则)文法。分别与图灵机、不确定的线性界限自动机、不确定的下推自动机和有