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

? 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有穷自动机(有限状态自动机) 有穷半自动机: 三元组