第十六章半群与独异点SemigroupandMonoid.pptVIP

第十六章半群与独异点SemigroupandMonoid.ppt

  1. 1、本文档共34页,可阅读全部内容。
  2. 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
  3. 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载
  4. 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
  5. 5、该文档为VIP文档,如果想要下载,成为VIP会员后,下载免费。
  6. 6、成为VIP后,下载本文档将扣除1次下载权益。下载后,不支持退款、换文档。如有疑问请联系我们
  7. 7、成为VIP后,您将拥有八大权益,权益包括:VIP文档下载权益、阅读免打扰、文档格式转换、高级专利检索、专属身份标志、高级客服、多端互通、版权登记。
  8. 8、VIP文档为合作方或网友上传,每下载1次, 网站将根据用户上传文档的质量评分、类型等,对文档贡献者给予高额补贴、流量扶持。如果你也想贡献VIP文档。上传文档
查看更多
第十六章半群与独异点SemigroupandMonoid

? Peking University 3-2 证明: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,m?Z+,结论为真 证明:(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+,结论为真 定理16.2 任何半群S,o都可以扩张成独异点S’,o’,e 证:任取e使得e不属于S,令S’=S?{e},且定义o’运算为 任意 x,y?S,x o’ y=xoy, 任意 x?S,x o’e=eo’x=x eo’e=e 可知o’运算在S’上是可结合的,且单位元为e,因此S’,o’,e为独异点 1.子半群:半群的子代数 2. 子独异点:独异点的子代数 3. 判别: 非空子集B, B对于V中的运算(含0元运算)封闭. 定理:若干子半群的非空交集仍为子半群; 若干子独异点的交集仍为子独异点. 证明:?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的子独异点. 若干个子半群的并不一定是子半群 例: 2Z={2k|k ? Z}, 3Z={3k|k ? Z} 但2Z?3Z不是Z,+的子半群 重要的子半群---子集合B生成的子半群 S为半群,B是S的非空子集,则S的所有包含B的子半群的交仍是S的子半群,称为由B生成的子半群。 V=S,?, B?S,包含B的最小的半群 B=?{A | A是S的子半群,B?A} = , 令Bn={b1b2…bn |bi?B,i=1,2,…,n} 例 V=Z,+半群, B={4,6}, 则B={4i+6j | i,j ?N, i和j 不同时为0} ={4,6,8,10,12,14,16,…}=2Z+?{2} 形式语言与自动机 自动机的概念在1936年图灵(Turing)提出,他设计的自动机叫图灵机。后来,丘奇(Church)提出一个假设:图灵机的计算能力代表着可实现的计算装置的基本范围。可以证明,任何能在电子计算机上实现的计算都能用图灵机进行描述。 形式语言约于1956年问世,N.乔姆斯基(Chomsky)给出文法的数学模型,1959年他将文法分为4类,0型(无限止)文法,1型(上下文有关)文法,2型(上下文无关)文法,3型(正则)文法。分别与图灵机、不确定的线性界限自动机、不确定的下推自动机和有限自动机等价。形式语言和编译原理密切相关。 形式文法 形式语言中任一句子类似于自然语言中的句子,可逐次应用文法规则构造而成 Jack and Jill ran up the hill. x:=(1+(0+x)) 例1:规则 1 句子=主语谓语 2 主语=名词短语 3 名词短语=名词 4 名词短语=名词连接词 名词短语 5 连接词=and 6 名词=Jack 7 名词=Jill 8 谓语=动词前置词短语 9 动词=ran 10前置词短语=前置词冠词名词 11 前置词=up 12 冠词=the 13 名词=hill 例2:ALGOL语言规则 1 语句=左部表达式 2 左部=标识符:= 3 标识符=x 4 表达式=算术量 5 算术量=项 6 项=(表达式) 7 项=项 + 算术量 8 项=1 9 项=0 10 项=标识符 文法主要组成部分 字母表:表中的字母为终结符,最终的句子中只能含有这些字母,也称为终结符集 非终结符集:一个中间字母集 文法规则或生成式集合 形式文法 形式文法:四元组G=VN,VT,P,σ VN是非终结符集 VT是终结符集 P是生成式集 α?β φAψ?φωψ( φωψ 为串,A为非终结符) σ是开始符 文法分类 无限止(0型)文法 |α||β| 缩减规则 上下文有关(1型)文法 φAψ?φωψ,要求ω非空 上下文无关(2型)文法 A?ω 正则(3型)文法 A?ω(ω至多含有一个非终结符) A?aB,A?a,右线性文法 A?Ba,A?a,左线性文法 16.2有穷自动机(有限状态自动机) 有穷半自动机: 三元组

文档评论(0)

118books + 关注
实名认证
文档贡献者

该用户很懒,什么也没介绍

1亿VIP精品文档

相关文档