参讨论两个例子 ●例3.1 令Σ={1,d},则Σ上的正规式r1(1d)*定义的正规集为 (1,1dld-.},其中代表字母,d代表数字,正规式即是 字母(字母数字)*,它表示的正规集中的每个元素的模式 是“字母打头的字母数字串”,就是 Pascal和多数程序 设计语言允许的的标识符的词法规则 例32 ∑={d,·,e,+,-}, 则Σ上的正规式d(d|E)(e(+|-|E)d|e)表示的是 无符号数的集合。其中d为0~9的数字。 程序设计语言的单祠都能用正规式亲定义
讨论两个例子 例3.1 令={l，d}，则上的正规式 r=l(l d) 定义的正规集为: {l,ll,ld,ldd,……},其中l代表字母,d代表数字,正规式 即是 字母(字母|数字) ,它表示的正规集中的每个元素的模式 是“字母打头的字母数字串”,就是Pascal和 多数程序 设计语言允许的的标识符的词法规则. 例3.2 ={d，•，e，+，-}, 则上的正规式 d (•dd )(e(+- )dd )表示的是 无符号数的集合。其中d为0~9的数字。 程序设计语言的单词都能用正规式 来定义
有穷自动机 有穷自动机(也称有限自动机)作为一种识别装 置,它能准确地识别正规集,即识别正规式所 表示的集合应用有穷自动机这个理论,为词法 分析程序的自动构造寻找有效的方法和工具 有穷自动机分为两类:确定的有穷自动机 ( Deterministic finite automata)和不确定的有 穷自动机( Nondeterministic Finite Automata)
有穷自动机 有穷自动机(也称有限自动机)作为一种识别装 置，它能准确地识别正规集，即识别正规式所 表示的集合.应用有穷自动机这个理论，为词法 分析程序的自动构造寻找有效的方法和工具。 有穷自动机分为两类：确定的有穷自动机 (Deterministic Finite Automata)和不确定的有 穷自动机(Nondeterministic Finite Automata)
关于有穷自动机我们将讨论如下题目 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化
关于有穷自动机我们将讨论如下题目 确定的有穷自动机DFA 不确定的有穷自动机NFA NFA的确定化 DFA的最小化
确定的有穷自动机DFA ●DFA定义: 一个确定的有穷自动机(DFA)M是一个五元 组:M=(K,Σ,f,S,Z)其中 1.K是一个有穷集,它的每个元素称为一个状 太 2.∑是一个有穷字母表,它的每个元素称为 个输入符号,所以也称Σ为输入符号表;
确定的有穷自动机DFA DFA定义： 一个确定的有穷自动机（DFA）M是一个五元 组：M=（K，Σ，f，S，Z）其中 1.K是一个有穷集，它的每个元素称为一个状 态； 2.Σ是一个有穷字母表，它的每个元素称为一 个输入符号，所以也称Σ为输入符号表；
DFA定义 3.f是转换函数,是在K×∑→K上的映射,即, 如f(ki,a)=kj,(ki∈K,kj∈K)就 意味着,当前状态为ki,输入符为a时,将转 换为下一个状态k,我们把kj称作ki的一个 后继状态; 4S∈K是唯一的一个初态; 5.ZcK是一个终态集,终态也称可接受状态 或结束状态
DFA定义 3.f是转换函数，是在K×Σ→K上的映射，即， 如 f（ki，a）=kj，（ki∈K，kj∈K）就 意味着，当前状态为ki，输入符为a时，将转 换为下一个状态kj，我们把kj称作ki的一个 后继状态； 4.S∈K是唯一的一个初态； 5.Z K是一个终态集，终态也称可接受状态 或结束状态