正规式的等价性p53 一个正规式r表示的正规集也就是r 所定义的语言，记为L(r) 0 若两个正规式r和s所表示的正规集 L(r)=L(s),则称r,s等价 记作r=S 例如：1(01)*=(10)*1 (a b)=ba {1,101,10101,.} (ab)*=(a*b*)* 25.4.3 ☒216
25.4.3 16 正规式的等价性 p53 一个正规式 r 表示的正规集也就是 r 所定义的语言，记为 L(r) 若两个正规式r和s所表示的正规集 L(r)=L(s),则称r,s等价 记作 r = s 例如：1(01) *=(10) *1 {1,101,10101,.} (a|b)=b|a (a|b)*=(a*|b*) *
描述程序设计语言单词的正规式例子p53 0 例∑={字母，数字}={A,B,Z,a,b,z,0,1,9} 令1=ABl.Z a b.lz d=012.|9 口标识符集的正规式： r=1(1d)* 定义的正规集：{1,11,1d,1dd,.} 口无符号整数集的正规式： s dd* 0 正规文法和正规式的等价性p53-54 了解略 25.4.3 7
25.4.3 17 描述程序设计语言单词的正规式例子 p53 例 ∑={字母，数字}={A,B,.,Z,a,b,.,z,0,1,.,9} 令 l=A|B|.|Z|a|b|.|z d=0|1|2|.|9 标识符集的正规式 ： r = l( l|d ) * 定义的正规集：{l，ll，ld，ldd,.} 无符号整数集的正规式： s = dd * 正规文法和正规式的等价性 p53-54 了解 略
正规文法和正规式的等价性 p53-54 o正规式r转换成正规文法G[S]S→r 对r,利用规则，增加非终结符号，直至符合G要求。 o例如r=a(ad)* 正规式 文法产生式 S→a(ad)* 规则1 A→Xy A→xB B→y A→xBA→y 利用规则1： 规则2 A→x*y BxBB→y S→aAA→(ad)* 规则3 A→xy A→xA→y 利用规则2： S→aAA→(ad)BA→eB→(ad)BB→e 利用规则3： S→aAA→aBA→dBA→eB→aBB→dBB→e 25.4.3 ☒18
25.4.3 18 正规文法和正规式的等价性 p53-54 正规式r转换成正规文法G[S] S→r 对r，利用规则，增加非终结符号，直至符合G要求。 正规式 文法产生式 规则1 A→xy A→xB B→y 规则2 A→x*y A→xB A→y B→xB B→y 规则3 A→x|y A→x A→y 例如r=a(a|d) * S→a(a|d) * 利用规则1： S→aA A→(a|d) * 利用规则2： S→aA A→(a|d)B A→ε B→(a|d)B B→ε 利用规则3： S→aA A→aB A→dB A→ε B→aB B→dB B→ε
正规文法和正规式的等价性p53-54 口正规文法G[S]转换成正规式r 对G,利用规则，减少非终结符号，直至只剩下S。 o例如文法G[S] 文法产生式 正规式 S→aAS→a 规则1 A-xBB→y A=xy 规则2 A→aAA→dA A→xAy A=x*y 规则3 A→xA→y A=xly A→aA→d 利用规则3： A代入S: S=aA a S=a(a d)*(a d)a A=(aA dA)(a d) S=a((a d)*(a d)e) 利用规则2： S=a(a d)* A=(a d)*(a d) 最终r=a(ad)* 25.4.3 节目录 219
25.4.3 19 正规文法和正规式的等价性 p53-54 正规文法G[S]转换成正规式r 对G，利用规则，减少非终结符号，直至只剩下S。 节目录 文法产生式 正规式 规则1 A→xB B→y A=xy 规则2 A→xA|y A=x*y 规则3 A→x A→y A=x|y 例如文法G[S] S→aA S→a A→aA A→dA A→a A→d 利用规则3： S=aA|a 利用规则2： A=(a|d) *(a|d) A代入S： S=a(a|d) *(a|d)|a S=a((a|d) *(a|d)|ε) S=a(a|d) * 最终r=a(a|d) * A=(aA|dA)|(a|d)
3.3有限自动机(FA)p47 是一种识别装置，能准确地识别正规集（正规语言） 有限自动机是具有离散输入输出条统的数学模型； 输入带 它具有有穷数目的内部状态，概括了对过去输入处 理的信息、，根据当前所处状态和面临输入即可决定 系统的后继行为。 激 状态变迁的作 t 输入带 读头 有穷控制器 25.4.3 ☒220
25.4.3 20 3.3 有限自动机（FA）p47 是一种识别装置，能准确地识别正规集(正规语言) 有限自动机是具有离散输入输出系统的数学模型； 它具有有穷数目的内部状态，概括了对过去输入处 理的信息，根据当前所处状态和面临输入即可决定 系统的后继行为。 输入带 有穷控制器 读头 输 入 带 起 激 励 状 态 变 迁 的 作 用 s t u d 0 1