描述程序设计语言单词的正规式例子p45-46 0 例∑={字母，数字}={A,B,Z,a,b,乙，0,1，9} 令1=AB.Z a b.lz d=012.|9 口标识符集的正规式： r=1(1d)* 定义的正规集：{1,11,1d,1dd,.} 口无符号整数集的正规式： s dd* 节目录 25.4.2
25.4.2 11 描述程序设计语言单词的正规式例子 p45-46 例 ∑={字母，数字}={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 * 节目录
正规文法和正规式的等价性p46-47 0 正规式r转换成正规文法G[S]S→r略 口正规文法G[S]转换成正规式r掌握 对G,利用规则，减少非终结符号，直至只剩下$。 0 例如文法G[S] 文法产生式 正规式 S→aAS→a 规则1 AxB B→y A=xy A→aAA→dA 规则2 A→xAy A=x*y 规则3 A→xA→y A=xly A→aA→d 利用规则3： A代入S: S=aAa S=a(a d)*(a d)a A=(aA dA)(a d) S=a((a d)*(a d)s) 利用规则2： S=a(a d)* A=(a d)*(a d) 最终r=a(ad) 25.4.2 节目录
25.4.2 12 正规文法和正规式的等价性 p46-47 正规文法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) 正规式r转换成正规文法G[S] S→r 略
3.4有限自动机(FA)p47 是一种识别装置，能准确地识别正规集（正规语言） 有限自动机是具有离散输入输出系统的数学模型； 输 它具有有穷数目的内部状态，概括了对过去输入处 带 理的信息、，根据当前所处状态和面临输入即可决定 起 系统的后继行为。 状态变迁的作 d 输入带 读头 有穷控制器 25.4.2 ☒>3
25.4.2 13 3.4 有限自动机（FA）p47 是一种识别装置，能准确地识别正规集(正规语言) 有限自动机是具有离散输入输出系统的数学模型； 它具有有穷数目的内部状态，概括了对过去输入处 理的信息，根据当前所处状态和面临输入即可决定 系统的后继行为。 输入带 有穷控制器 读头 输 入 带 起 激 励 状 态 变 迁 的 作 用 s t u d 0 1
3.4.1确定有限自动机(DFA)的定义p4748 DFAM定义 确定的有限自动机DFAM是一个五元组 M=(S,∑，δ，s0,F) (1)S是一个非空有限集，它的每个元素称为一个状态。 (2)∑是一个有穷字母表，它的每个元素称为一个输入 符号，所以也称为输入符号字母表。 (3)δ是状态转换函数，是在S×∑→S上的单值映射。 (具体解释见下页) (4) s0S0∈S,是唯一的一个初态。 (5)FFS,可空，是一个终态集，终态也称可接受状 态或结束状态。 25.4.2 ☒214
25.4.2 14 3.4.1 确定有限自动机(DFA)的定义 p47-48 DFA M 定义 确定的有限自动机DFA M是一个五元组 M =（S，，δ ，s0 ，F ) (1) S 是一个非空有限集，它的每个元素称为一个状态。 (2) 是一个有穷字母表，它的每个元素称为一个输入 符号，所以也称为输入符号字母表。 (3) δ是状态转换函数，是在S×→S上的单值映射。 （具体解释见下页） (4) s0 s0 ∈S，是唯一的一个初态。 (5) F F S，可空,是一个终态集,终态也称可接受状 态或结束状态
DFA举例p48 SUVQ S Q 例如有DFA M=（{0,1,2,3},{a,b},6,0,{3 其中δ定义为：δ(0，a)=16(0,b)=2 δ(1，a)=36(1,b)=2 8（2,a)=1δ(2，b)=3 δ(3，a)=36(3,b)=3 其它表示形式：状态转换矩阵和状态转换图 a b 0 1 2 1 3 2 2 1 3 3+ 3 3 表示初态 +表示终态 25.4.2
25.4.2 15 DFA举例 p48 其它表示形式：状态转换矩阵和状态转换图 例如有DFA M =（{0,1,2,3},{a,b}，δ,0,{3}） 其中δ定义为：δ（0，a）=1 δ（0，b）=2 δ（1，a）=3 δ（1，b）=2 δ（2，a）=1 δ（2，b）=3 δ（3，a）=3 δ（3，b）=3 a 1 0 b 3 2 a a b b a,b 0 1 2 a b 3 1 2 3 2 1 3 3 3 - + - 表示初态 + 表示终态 S U V Q S Q