第3章 自动机基础.ppt

※有限自动机化简练习删除无用状态合并等价状态第29页，共40页，星期日，2025年，2月5日(3)令getchar(ch)为读符号函数。3.4有限自动机的实现用计算机完成有限自动机的功能，其核心是“变换”的实现技术。这里介绍的是把变换表按某种方式存储起来，作为知识源来识别单词，实现机制是：控制程序变换表+【三点说明】(1)假定自动机只作为识别器，即对待识别的符号串：仅回答是(接受)或否(拒绝)。(2)为便于处理，可令#作为待识别的符号串的后继符。为此，扩展自动机如下：③①+⑥⑤-a④-b-##……ok4ok5…………631#ba+--空则no第30页，共40页，星期日，2025年，2月5日3.4.1控制程序设计开始结束state=1getchar(ch)查变换表：?(state,ch)=??=空?=ok回答:yes回答:noynystate=?n开始状态1赋给变量state从输入串中读取一符号到变量ch变量state重新被赋值为变换后的状态！第31页，共40页，星期日，2025年，2月5日n…②①3.4.2变换表存储结构设计变换表的存储结构可选择下述两种方式之一：(1)二维数组，其下标是(状态，输入符号)；※为了适应不同编码语言的需要，状态和输入符号可采取相应的编码形式；通常，使用连续的正整数：0,1,2,3,…。(2)压缩变换表，方法是把每个状态行作为子表，状态为索引，并把错误的输入符号合并在一起，如：no?…⑧b⑤ano?…②f④e…no?…⑨y①x索引表?(其他)--错误符号。状态变换子表第32页，共40页，星期日，2025年，2月5日④③②①※有限自动机实现示例【例3.11】有限自动机DFA:③①+②④ab-#abcd?no②b③a?no④dno?②c④b③a?nook#压缩变换表输入串aacd#识别过程：备注变换剩余chstate3acd#a1接受ok#44#d22d#c33cd#a3索引表第33页，共40页，星期日，2025年，2月5日第1页，共40页，星期日，2025年，2月5日3.1正规语言及其描述方法【定义】正规语言是指由正规文法定义的语言；程序设计语言中的单词，大都属于此种语言。正规语言有三种等价的表示方法：(1)正规文法(2)正规式(3)有限自动机正规文法仅有三种形式的产生式：(1)A-aB(2)A-a(3)A-?【例3.1】G(Z)：A-aA|?∵A=?;A=aA=aaA=aaaA=…=an,n≥0∴L(G)={an|n≥0}正规文法正规语言第2页，共40页，星期日，2025年，2月5日※正规语言判定示例:【例3.2】L1={ambn|m≥0,n≥1},正规语言?∵可由正规文法定义：G1(S):S-aS|bA;A-bA|?∴L1是正规语言。【例3.3】L2={(ab)n|n≥1},正规语言?∵可由正规文法定义：G2(S):S-aA;A-bB;B-aA|?∴L2是正规语言。【例3.4】L3={anbn|n≥0},正规语言?∵不能由正规文法定义(正规文法无法描述a和b数 量上相等！)：∴L3不是正规语言！第3页，共40页，星期日，2025年，2月5日3.1.1正规语言的另外两种表示方法Ⅰ.正规式表示法：※正规式是指由字母表中的符号，通过以下三种运算(也可以使用圆括号)连接起来构成的表达式e：闭包(*，+)连接(.)或(|)※设val(e),L(e)分别表示正规式e的值和语言，则：L(e)={x|x=val(e)}即正规式表示的语言是该正规式所有值的集合。正规式L3={abnc,bn|n≥0