吉林大学：《编译原理》课程教学资源（PPT课件讲稿）有限自动机（Finite Automata）

有限自动机( Finite automata) 描述程序设计语言中的单词的识别过程。 主要内容: ●确定有限自动机DFA( deterministic Fa 确定有限自动机DFA的实现 非确定有限自动机NFA( Nondeterministic fa ●NFA到DFA的转换 ●DFA的化简

有限自动机(Finite Automata) 描述程序设计语言中的单词的识别过程。 主要内容： ⚫ 确定有限自动机DFA(Deterninistic FA) ⚫ 确定有限自动机DFA的实现 ⚫ 非确定有限自动机NFA(Nondeterninistic FA) ⚫ NFA到DFA的转换 ⚫ DFA的化简

确定有限自动机DFA 确定有限自动机DA为一个五元组 (Σ,Ss,S,f,TS),其中 ●∑是一个有穷字母表,它的每个元素称为一个 输入字符; SS是一个有穷集,它的每个元素称为一个状态; ●S∈SS是唯一的一个初始状态; f是在Ss×∑>SS上的转换函数 ● TScSS,是一个终止状态集,又称为接受状态 集

确定有限自动机DFA ⚫ 确定有限自动机DFA为一个五元组 (,SS,S0,f,TS)，其中： ⚫ 是一个有穷字母表，它的每个元素称为一个 输入字符； ⚫ SS是一个有穷集，它的每个元素称为一个状态； ⚫ S0 SS是唯一的一个初始状态； ⚫ f是在 SS  → SS上的转换函数 ⚫ TSSS，是一个终止状态集，又称为接受状态 集

DFA的两种表示方式 状态转换图 结点表示状态,转换边表示转换函数,边 的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。 状态转换表: 可用二维数组描述。标识出初始状态和终 止状态 Trans (S,, a)=s

DFA的两种表示方式 ⚫ 状态转换图： 结点表示状态，转换边表示转换函数，边 的箭头方向指向转换函数中定义的转换方 向。标识出初始状态和终止状态。 ⚫ 状态转换表： 可用二维数组描述。标识出初始状态和终 止状态。 Trans（ SI ，a）＝ SJ

个DFA的例子 DFA M=(a, b, S,U,,Q, S,f( Q) 其中f定义为: f(s,a=U f(v,a=U f(S,b)=Ⅴ f(V,b=Q f(U, a=Q f(Q, a=Q f(U, b=v f(Q, b=Q

一个DFA的例子 ⚫ DFA M=( {a,b}, {S,U,V,Q}, S, f, {Q} ), ⚫ 其中 f 定义为： f ( S, a )=U f ( V, a )=U f ( S, b )=V f ( V, b )=Q f ( U, a )=Q f ( Q, a )=Q f ( U, b )=V f ( Q, b )=Q

状态转换图

S U V Q a b b a b a a,b 状态转换图

字符 状态 aUQUQ bVvQQ Q 状态转换表

字符 状态 a b S U V U Q V V U Q Q Q Q 状态转换表

DFA接受的字符串 ●对于∑*中的任何字符串t,若存在一条从初始 结点到某一终止结点的路径,且这条路上所 有弧的标记符连接成的字符串等于t,则称t 可为DFAM所接受(识别) DFAM所能接受的字符串的全体记为L(M)

DFA接受的字符串 ⚫ 对于*中的任何字符串t,若存在一条从初始 结点到某一终止结点的路径，且这条路上所 有弧的标记符连接成的字符串等于t,则称t 可为DFA M所接受（识别）。 ⚫ DFA M 所能接受的字符串的全体记为L(M)

DFA的确定性 ●初始状态唯 转换函数fSSx∑>SS是一个单值函数,也就 说,对任何状态s∈SS,和输入符号a∈∑ f(s,a)唯一地确定了下一个状态。即转换函 数至多确定一个状态。 ●没有空边。即没有输入为8()

DFA的确定性 ⚫ 初始状态唯一。 ⚫ 转换函数f:SS→SS是一个单值函数，也就 是说，对任何状态SSS,和输入符号a  , f(S,a)唯一地确定了下一个状态。即转换函 数至多确定一个状态。 ⚫ 没有空边。即没有输入为（）

DFA的实现1 ●状态转换表的形式:(数组T存放转换函数) 1.当前状态 State置为初始状态 2.读一个字符→ Current char 3.如果 Cur rentcha≠0f并且 T(State, CurrentChar)terror 则当前状态转为新的状态 T(State, Current), 读下一字符。重复第3步工作。 4.如果当前字符为Eof并且当前状态属于终止状态, 则接受当前字符串,程序结束。否则报错 特点: 程序短小,但占用存储空间多

DFA的实现1 ⚫ 状态转换表的形式：（数组T存放转换函数） 1.当前状态State置为初始状态 2.读一个字符 → CurrentChar 3.如果CurrentCharEof并且 T(State,CurrentChar)error 则当前状态转为新的状态T(State,Current)， 读下一字符。重复第3步工作。 4.如果当前字符为Eof并且当前状态属于终止状态， 则接受当前字符串，程序结束。否则报错 ⚫ 特点： 程序短小，但占用存储空间多

DFA的实现2 ●状态转换图的形式: 每个状态对应一个带标号的case语句 转向边对应goto语句 Li: case Currentchar of goto Li b k b goto Lk other Error( ●特点: 程序长,但占用存储空间少

b DFA的实现2 ⚫ 状态转换图的形式： ⚫ 每个状态对应一个带标号的case语句 ⚫ 转向边对应goto语句 ⚫ 特点： 程序长，但占用存储空间少 i j k a Li: case CurrentChar of a ：goto Lj b : goto Lk other : Error( )