将不确定的有限自动机转换为确定的自动机

确定有限自动机（NFA ）到确定有限自动机（DFA ）的转化是正则表达式和有限自动机等形式化语言理论中的一个重要概念。

这个过程涉及将非确定性自动机转化为等价的确定性自动机。

下面是一个简单的例子，演示如何将一个NFA 转化为DFA 。

示例 NFA:考虑一个NFA ，它接受所有包含子串 "01" 的二进制字符串。

NFA 状态转移图：NFA 状态转移规则：1. q0→0q12. q1→1q23. q2→1,εq34. q3→1,εq35. q3→0,εq0NFA 状态图解释：•q0 是起始状态。

•q2 是接受状态。

•从 q0 开始，读入 "0" 到达 q1，再读入 "1" 到达 q2，形成 "01" 子串。

•从 q2 通过 "1" 和 ε 达到 q3，表示可以在 "01" 后面追加 "1"。

•q3 可以通过 "1" 和 ε 一直回到自身，表示可以在 "01" 后面追加任意数量的 "1"。

• q3 还可以通过 "0" 和 ε 返回到 q0，表示可以在任意位置重新开始 "01" 的匹配。

NFA到DFA转换：下面是将上述NFA转化为DFA的步骤：1.构建子集构造法的初始状态：初始状态是 NFA 的起始状态的ε-闭包。

在这个例子中，初始状态为 {q0, q3}。

2.状态扩展：对于每个状态集合，找出它的ε-闭包，并对每个可能的输入符号应用状态转移规则，形成新的状态集合。

–对于输入 "0"：•从 {q0, q3} 中的 q0 通过 "0" 可以到达 q1，形成 {q1}。

–对于输入 "1"：•从 {q0, q3} 中的 q0 通过 "1" 可以到达 q2，形成 {q2}。

编译原理-题库1、关于有限自动机叙述正确的是（）A、有限自动机分为确定的有限自动机和不确定的有限自动机B、有限自动机可由状态转换图表达C、有限自动机可由状态转换矩阵表达D、有限自动机可以识别正规集答案：ABCD2、编译原理各阶段的工作都涉及到（）A、表格管理B、语法分析C、出错处理D、代码优化答案：AC3、程序语言一般分为（）和（）A、高级语言B、专用程序语言C、低级语言D、通用程序语言答案：AC4、高级语言的翻译方式有（）和（）A、汇编方式B、模拟方式C、解释方式D、编译方式答案：CD5、语法分析器的常用方法是（）A、自顶向下B、自底向上C、自左向右D、自右向左答案：AB6、请说明你使用的语法分析方法（）A、LL1B、OPGC、LRD、YACC答案：ABCD7、数据的逻辑结构有哪些（）A、集合结构B、线性结构C、树形结构D、图形结构答案：ABCD8、NFA与DFA的不同之处（）A、初态定义不同B、字母表定义不同C、转换函数定义不同D、终态定义不同答案：AC9、A、B、C、D、答案：A 10、A、B、C、D、答案：C 11、A、是B、不是C、无法判断D、可能答案：A12、A、上下文有关B、上下文无关C、正则D、0型答案：C13、A、B、C、D、答案：D14、A、B、C、D、答案：D15、LL(1)文法的充要条件是（ ）。

A、B、该文法对应的LL(1)分析表中每个项目最多只有一条产生式。

C、A和BD、都不是答案：B16、文法A->aAb|ab生成的语言是（ ）。

A、{ab}B、{aAb}C、D、答案：C17、以下说法中正确的是（ ）A、B、C、D、答案：B18、8. 正则式的“*”读作（ ）。

A、并且B、连接C、正则闭包D、闭包答案：D19、一个LR(0)文法一定是SLR(1)文法。

答案：正确20、在类型声明文法中，类型属性type是继承属性。

答案：正确21、在构造递归下降伪代码时，将非终结符A翻译为一个匹配过程match（A）。

《计算机编译原理》试卷B参考答案一、单项选择题（每小题1分，共25分）1、有文法G：E→E*T|TT→T+i|i句子1+2*8+6按该文法G归约，其值为＿＿＿B＿＿＿。

A、23B、42C、30D、172、规范归约指＿＿＿B＿＿＿。

A、最左推导的逆过程B、最右推导的逆过程C、规范推导D、最左归约的逆过程3、词法分析所依据的是＿＿＿B＿＿＿。

A、语义规则B、构词规则C、语法规则D、等价变换规则4、词法分析器的输出结果是＿＿＿C＿＿＿。

A、单词的种别编码B、单词在符号表中的位置C、单词的种别编码和自身值D、单词自身值5、正规式M1和M2等价是指＿＿＿C＿＿＿。

A、M1和M2的状态数相等B、M1和M2的有向弧条数相等C、M1和M2所识别的语言集相等D、M1和M2状态数和有向弧条数相等6、下面的状态转换图接受的字集为＿＿＿D＿＿＿。

A、以0开头的二进制数组成的集合B、以0结尾的二进制数组成的集合C、含奇数个0的二进制数组成的集合D、含偶数个0的二进制数组成的集合7、词法分析器作为独立的阶段使整个编译程序结构更加简洁、明确，因此，＿＿＿B＿＿＿。

A、词法分析器应作为独立的一遍B、词法分析器作为子程序较好C、词法分析器分解为多个过程，由语法分析器选择使用D、词法分析器并不作为一个独立的阶段8、若a为终结符，则A→α·aβ为＿＿＿B＿＿＿项目A、归约B、移进C、接受D、待约9、若项目集I k含有A→α·，则在状态k时，仅当面临的输入符号a∈FOLLOW(A)时，才采取“A→α·”动作的一定是＿＿＿D＿＿＿。

A、LALR文法B、LR（0）文法C、LR（1）文法D、SLR（1）文法10、就文法的描述能力来说，有＿＿＿C＿＿＿。

A、SLR（1）⊂LR（0）B、LR（1）⊂LR（0）C、SLR（1）⊂LR（1）D、无二义文法⊂LR（1）11、在LR（0）的ACTION子表中，如果某一行中存在标记“r j”的栏，则＿＿＿A＿＿＿。

编译技术命题指导意见教学内容知识点及题型第一章编译器概述A （1）编译的阶段划分[选择题2分][1] 编译程序绝大多数时间花在( )上。

A. 出错处理B. 词法分析C. 目标代码生成D. 符号表管理答案：D[2] ( ) 和代码优化部分不是每个编译程序都必需的。

A. 语法分析B. 中间代码生成C. 词法分析D. 代码生成答案：B[3] 编译程序前三个阶段完成的工作是( )。

A. 词法分析、语法分析和代码优化B. 代码生成、代码优化和词法分析C. 词法分析、语法分析和语义分析D. 词法分析、语法分析和代码生成答案：C（2）遍的概念[填空题2分][1] 编译阶段的活动常用一遍扫描来实现，一遍扫描包括和。

答案：读一个输入文件写一个输出文件[2] 将编译程序分成若干个“遍”是为了________。

答案：使程序的结构更加清晰[3] 编译器从逻辑上可以分为7个阶段，其中，可以作为一个后端遍的是___________阶段。

答案：代码生成（3）前端和后端的划分[简答题5分][1] 什么是前端？[5分]答案：编译器分成分析和综合两大部分。

分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。

[2] 什么是后端？[5分]答案：编译器分成分析和综合两大部分。

综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。

[3] 什么是前端？什么是后端？[5分]答案：编译器分成分析和综合两大部分。

分析部分揭示源程序的基本元素和它们所形成的层次结构，决定它们的含义，建立起源程序的中间表示，分析部分经常被称为前端。

综合部分从源程序的中间表示建立起和源程序等价的目标程序，它经常被称为后端。

第二章2.1 2.2 词法记号的定义及描述B （1）词法分析器的功能[选择题2分][1] 词法分析程序的输出结果是（）。

A. 单词的种别编码B. 单词在符号表中的位置C. 单词的种别编码和单词属性值D. 单词的单词属性值答案：C[2] 词法分析器用于识别_____。

NFA转化为DFA的转换算法及实现摘要确定有限⾃动机确定的含义是在某种状态，⾯临⼀个特定的符号只有⼀个转换，进⼊唯⼀的⼀个状态。

不确定的有限⾃动机则相反，在某种状态下，⾯临⼀个特定的符号是存在不⽌⼀个转换，即是可以允许进⼊⼀个状态集合。

在⾮确定的有限⾃动机NFA中,由于某些状态的转移需从若⼲个可能的后续状态中进⾏选择，故⼀个NFA对符号串的识别就必然是⼀个试探的过程。

这种不确定性给识别过程带来的反复，⽆疑会影响到FA的⼯作效率。

⽽DFA则是确定的,将NFA转化为DFA将⼤⼤提⾼⼯作效率,因此将NFA转化为DFA是有其⼀定必要的。

对于任意的⼀个不确定有限⾃动机（NFA）都会存在⼀个等价的确定的有限⾃动机（DFA），即L(N)=L(M)。

本⽂主要是介绍如何将NFA转换为与之等价的简化的DFA，通过具体实例，结合图形，详细说明转换的算法原理。

关键词：有限⾃动机；确定有限⾃动机（DFA），不确定有限⾃动机（NFA）AbstractFinite automata is determinate and indeterminate two class. Determine the meaning is in a certain state, faces a particular symbol only one conversion, enter only one state. Not deterministic finite automata is the opposite, in a certain state, faces a particular symbol is the presence of more than one conversion, that is to be allowed to enter a state set.Non deterministic finite state automata NFA, because of some state are transferred from a number of possible follow-up state are chosen, so a NFA symbol string recognition must be a trial process. This uncertainty to the recognition process brought about by repeated, will undoubtedly affect the efficiency of the FA. While the DFA is determined, converting NFA to DFA will greatly improve the working efficiency, thus converting NFA to DFA is its necessary.For any a nondeterministic finite automaton ( NFA ) can be an equivalent deterministic finite automaton ( DFA ), L ( N ) =L ( M ). This paper mainly introduces how to convert NFA to equivalent simplified DFA, through concrete examples, combined with graphics, a detailed description of the algorithm principle of conversion.Keywords:：finite automata; deterministic finite automaton ( DFA ), nondeterministic finite automaton ( NFA⽬录1.前⾔： (1)1.1背景 (1)1.2实践⽬的 (1)1.2课程实践的意义 (1)2.NFA和DFA的概念 (2)2.1 不确定有限⾃动机NFA (2)2.2确定有限⾃动机DFA (3)3．从NDF到DFA的等价变化步骤 (5)3.1转换思路 (5)3.2.消除空转移 (5)3.3⼦集构造法 (7)4程序实现 (9)4.1程序框架图 (9)4.2 数据流程图 (9)4.3实现代码 (10)4.4运⾏环境 (10)4.5程序实现结果 (10)5.⽤户⼿册 (12)6.课程总结： (12)7.参考⽂献 (12)8. 附录 (13)1.前⾔：1.1背景有限⾃动机作为⼀种识别装置，它能准确地识别正规集，即识别正规⽂法所定义的语⾔和正规式所表⽰的集合，引⼊有穷⾃动机这个理论，正是为词法分析程序的⾃动构造寻找特殊的⽅法和⼯具。

有限状态自动机的确定化姓名：翟彦清学号：E10914127一、实验目的设计并实现将 NFA确定化为DFA的子集构造算法，从而更好地理解有限自动机之间的等价性，掌握词法分析器自动产生器的构造技术。

该算法也是构造LR分析器的基础。

输入：非确定有限(穷)状态自动机。

输出：确定化的有限(穷)状态自动机二、实验原理一个确定的有限自动机(DFA M可以定义为一个五元组，M k( K,E, F, S, Z),其中：(1)K是一个有穷非空集，集合中的每个元素称为一个状态；(2)刀是一个有穷字母表，刀中的每个元素称为一个输入符号；(3)F是一个从K XE^ K的单值转换函数，即 F (R, a)= Q ( R, Q€ K)表示当前状态为R,如果输入字符 a,则转到状态 Q,状态Q称为状态R的后继状态；(4)S€ K,是惟一的初态；(5)Z K,是一个终态集。

由定义可见,确定有限自动机只有惟一的一个初态,但可以有多个终态,每个状态对字母表中的任一输入符号,最多只有一个后继状态。

对于DFAM,若存在一条从某个初态结点到某一个终态结点的通路，则称这条通路上的所有弧的标记符连接形成的字符串可为DFAM所接受。

若M的初态结点同时又是终态结点，则称&可为 M所接受(或识别)，DFA M所能接受的全部字符串(字)组成的集合记作 L(M)。

一个不确定有限自动机(NFA M可以定义为一个五元组，M=(K, E, F, S, Z), 其中：( 1) k 是一个有穷非空集,集合中的每个元素称为一个状态；(2)E是一个有穷字母表，E中的每个元素称为一个输入符号；(3)F是一个从K xE^ K的子集的转换函数；(4)S K,是一个非空的初态集；(5)Z K,是一个终态集。

由定义可见，不确定有限自动机 NFA与确定有限自动机DFA的主要区别是：(1)NFA的初始状态S为一个状态集，即允许有多个初始状态；(2)NFA中允许状态在某输出边上有相同的符号，即对同一个输入符号可以有多个后继状态。

第三章词法分析练习3.1给出一个正则表达式和自动机，使之表示满足下面条件的0、1序列：1）只包含两个1。

2）不包含连续的1。

3）包含偶数个1。

3.2写出下面符号串集的正则表达式：1）{a,b,c}a偶数出现2）{a,b,c}不包含子串baa3）二进制数，大于1010014)二进制数，4的倍数5)偶数个0奇数个1的0/1串3.3构造识别下列正则表达式定义的NFA：1)(a|(b)+2)(a*|(b*)*3)(a|(bc)*d*4)((0|1)*(2|3)*)|00115)(a|b)*abb(a|b)*3.4为下列正则表达式构造极化的DFA:1)(a|b)*a(a|b)2)(a|b)*a(a|b)(a|b)3.5利用自动机原理构造模式匹配程序，即构造一个程序，使它能识别给定a/b串是不是a i b j a k b m类串：，其中i和j是大于等于0的整数，而k和m是大于0的整数。

3.5将下面不确定自动机NFA转换为确定自动机DFA:3.6将下面不确定自动机NFA转换为确定自动机DFA:3.7试将下面不确定自动机NFA转换为确定自动机DFA:3.8试写出下面确定自动机DFA的正则表达式：3.9设置一个名字表NameL和整数表ConstL，当遇到标识符时，将其字符串送入名字表NameL，并把其名字表地址作为标识符的Value值。

整常数情形也一样，不要求翻译成二进制数。

要求在NameL表和ConstL表中没有相同元素。

试用C语言写一个针对上述单词集的词法分析器。

单词class valuebegin BeginSymbend EndSymbvar VarSymbinteger IntSymbif IfSymbthen ThenSymbelse ElseSymb;SemiSymb:ColonSymb:=AssigSymb<LittleSymb<=LittEquiSymb标识符IdentSymb名字表地址整常数ConstSymb常数表地址3.10实数的语法定义如下面所述：<实数>::=<整数部分><小数部分><指数部分><整数部分>::=<数字>|<整数部分><数字><小数部分>::=ε|.<整数部分><指数部分>::=ε|e<指数符号><整数部分><指数符号>::=ε|+|-试写出实数的非确定自动机。

编译原理课后习题答案编译原理习题答案习题11.1翻译程序：把⽤某种程序设计语⾔（源语⾔）编写的程序（源程序）翻译成与之等价的另⼀种语⾔（⽬标语⾔）的程序（⽬标程序）。

编译程序：⼀种翻译程序，将⾼级语⾔编写的源程序翻译成等价的机器语⾔或汇编语⾔的⽬标程序。

1.2词法分析、语法分析、语义分析和中间代码⽣成、代码优化、⽬标代码⽣成1.3词法分析：根据语⾔的词法规则对构成源程序的符号进⾏扫描和分解，识别出⼀个个的单词。

语法分析：根据语⾔的语法规则，把单词符号串分解成各类语法单位。

语义分析及中间代码⽣成：对语法分析识别出的语法单位分析其含义，并进⾏初步翻译。

代码优化：对中间代码进⾏加⼯变换，以产⽣更⾼效的⽬标代码。

⽬标代码⽣成：将中间代码变换成特定机器上的绝对指令代码、可重定位的指令代码或会变指令代码。

以上5个阶段依次执⾏。

习题22.1 （1）有穷⾮空的符号集合（2）利⽤产⽣是规则A->v将A替换为v时与A的上下⽂⽆关。

（3）略（4）推导是把句型中的⾮终结符⽤⼀个产⽣是规则的右部开替代的过程；直接推导是将⾮终结符的替代结果只⽤了⼀次产⽣式规则。

（5）略（6）⼀个句型的最左直接短语（7）如果⼀个⽂法存在某个句⼦对应两棵不同的语法树或有两个不同的最左（右）推导，则称这个⽂法是⼆义的。

2.2（1）VN =｛Z,A,B｝ VT ={a,b,c,d,e}（2）abbcde,abbbcde是，acde不是。

2.3 （1）L[G]={d|n≥1,m≥0}（2）2.4 （1） A=>B=>c=>fAg=>fBg=>fCg=>feg（2）A=>AaB=>AaC=>Aae=>Bae=>BcCae=>Bceae=>Cceae=>eceae（3）A=>B=>BcC=>BcfAg=>BcfAaBg=>BcfAaCg=>BcfAaeg=>BcfBaeg =>BcfCaeg=>Bcfeaeg=>Ccfeaeg=>ecfeaeg（3）中题⽬有错应为C fCg|e2.5L[G]=｛a?b?c?|aab,n≥2｝2.6 (1)Z→AB A→Aa|ε B→Bb|ε(2)Z→aZb|ab(3)Z→aAb A→aAb|b(4)Z→AB A→aAb|ab B→cB|ε(5)Z→aaAb|ab Z→aaBb|bb A→aaAb|ab B→aaBb|bb2.7 ⼀位数：Z→2|4|6|8两位数：Z→AB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8三位以上：Z→ACB A→1|2|3|4|5|6|7|8|9 B→0|2|4|6|8 C→CDD→0|1|2|3|4|5|6|7|8|92.8证明：E=>E+T=>E+T*F短语：T*F E+T*F 直接短语：T*F 句柄：T*F2.9 语法树： E 短语：E*T , (E*T) , F↑(E*T) ，F ,E* F↑(E*T)E *F 直接短语：E*T , FT ↑ F 句柄：FF ( E )E * T2.10（1）语法树（2）直接短语：a , ZZ 句柄：Z( L )L , ZZ ( L )Za2.11最左推导：Z=>ZaB=>BaB=>B+AaB=>A+AaB=>(+)Z*aB=>(+)ZaB*aB =>(+)+aB*aB=>(+)+aA*aB=>(+)+a(*aB=>(+)+a(*aA=>(+)+a(*a(直接短语：（，+句柄：(2.12(1) S=>iSeS=>iiSeS=>iiIeS=>iiIeIS=>iS=>iiSeS=>iiIeS=>iiIeI(2) S=>SaS=>cSaS=>cfaS=>cfafS=>cS=>cSaS=>cfaS=>cfaf(3) E=>EOE=>EOEOE=>iOEOE=>i+EOE=>i+iOE=>i+i-E=>i+i-iE=>EOE=>iOE=>i+E=>i+EOE=>i+iOE=>i+i-E=>i+i-i2.13 Z→aABZ|cCACdA→bAB|aZA|cCCB→bAB|CzbC→cZ|c习题33.1(1)确定的有限⾃动机(2)不确定的有限⾃动机(3)正规集是⼀类特殊的单词集合，正规式是正规集的描述⼯具 3.2 (1) (1|2|3|4|5|6|7|8|9|0)*(1|3|5|7|9) (2) 11(0|1)*00 3.3 证明：b *(a|b)+=｛a,b,ab,ba,aa,bb …｝ (a|b)+=｛a,b,ab,ba,aa,bb …｝ 3.4 (1)(2)DDDD3.5(1) (2)(3)3.6(1) (01|10) *(01|10)(2) (0(1|00)*)|003.7(1) Z →1AB (2)Z →ABA →(0|1)A A →0A|εA →0|1B →(0|1)B|ε B →0B B →ε3.8 r=a(a|b )*bb3.9 Z →1BB →0Z|0 Z →0Z|ε3.10 3.11DDD习题44.1 (1)若⽂法G[Z]满⾜①⽂法不含左递归②③(2)4.2(1) First(S)={a,d} First(B)={a,d,c,ε}First(A)={a,d,e,c} First(D)={a,d,ε}Follow(S)={#,a,b,d,e} Follow(B)={a,d}Follow(A)={b} Follow(D)={e,a,d,b}(2) 不是4.3 (1) 证明： First(Z)={a,b,c} Follow(S)={#,a,b,c,d} First(A)={a,b,c,d} Follow(A)={ #,a,b,c,d }First(B)={a,d,c} Follow(B)={ a,b,c,d } 是LL(1)⽂法。

nfa转dfa子集法-回复"NFA转DFA子集法"：从非确定有限自动机到确定有限自动机的转换引言：在计算机科学中，有限自动机是一种数学模型，用于描述和识别具有确定语言特征的字符串集。

非确定有限自动机（NFA）和确定有限自动机（DFA）是两种主要类型的有限自动机。

NFA由于其灵活性和简明性而被广泛使用，在某些场景下，我们需要将NFA转换为DFA以提高运行效率和可靠性。

本文将详细介绍一种常用的NFA转DFA的转换方法，即子集法。

第一步：了解NFA和DFA的基本概念和特征在深入探讨NFA转DFA的转换方法之前，我们需要先了解NFA和DFA 的基本概念和特征。

NFA是一种具有多个可能的转换路径的有限自动机，可以在每个状态上有多个转换选项。

DFA则是一种每个输入符号仅对应一个转换路径的自动机，具有确定性的转换行为。

在NFA中，我们可以通过ε-转换实现从一个状态到另一个状态的跳转，而在DFA中则不存在ε-转换。

第二步：理解子集法的基本思想子集法是一种常用的将NFA转换为DFA的方法。

它的基本思想是通过构建一个等价的DFA，其中NFA的每个状态对应DFA的一个状态。

子集法的核心步骤是将NFA的状态集合进行组合，形成DFA的状态集合。

第三步：具体步骤及示例说明下面将详细介绍将NFA转换为DFA的子集法步骤，并通过一个示例说明该方法的应用：步骤1：构建初始状态将NFA的初始状态作为DFA的初始状态，同时闭包操作（closure）该初始状态。

闭包操作是一个将状态集合扩展为包括可达到的所有状态的过程。

例如，对于一个NFA状态q0，我们可以通过闭包操作找到所有通过ε-转换可达到的状态集合{q0, q1}。

步骤2：使用闭包操作和转移函数对于DFA的初始状态，使用闭包操作获取新的状态集合，并通过转移函数计算每个输入符号的下一个状态。

假设我们有一个NFA状态q0，输入符号为a，通过转移函数可以得到新的状态集合{q0, q1, q2}。

有限自动机ATM机状态转换0引言有限自动机源于20世纪40年代，是一种用于研究离散事件动态系统的数学模型,1943年麦克卡赛(McCulloch)与皮特斯(Pitts)建立了模拟神经网络的自动机。

1956年莫尔(Moore)建立了描述计算机的时序机的概念。

此后,自动机理论迅速发展,与计算机技术密切结合,在人工智能、自动控制等领域有广泛应用。

有限自动机是计算机科学的重要基石,它可以用来研究时序线路与计算机的构造,是计算机硬件的理论基础。

由于计算机中的数以二进制形式表示,所以计算机基本的加法器功能可以用有限自动机来实现。

计算机的操作系统在信息处理进程中需要一定资源。

在不同资源条件下,进程处于不同的状态。

进程活动中要不断提出申请资源和归还资源的请求,这些请求与进程的状态和资源的条件有关。

操作系统的这些活动体现了一个有限自动机的功能特征,因此操作系统的信息处理过程可以用有限自动机来刻画。

1 ATM机状态分析ATM机是当前银行较为常用的一种用户自助操作的机器，它是以实时操作系统软件基础实现的强实时系统。

ATM机具有事务的基本特性，即：原子性、一致性、隔离性、持久性。

其中，原子性保证了事务的操作是一个完整的过程，要么做，要么不做；一致性：保证事务从一个一致性状态转换到另外一个一致性状态，此特性与原子性密切相关；隔离性：即一个事务的执行不被其他事务所干扰，各事务之间执行互不干扰；持久性：即一个事务一旦提交，它对数据库中的数据改变就是永久性的。

从插卡到某个动作操作成功为一个原子操作，要么成功，提交事务，更新数据库；要么失败，退回到插卡前的操作，数据库中数据仍为原来的数据，不发生改变。

本文从ATM机的基本状态出发来讨论ATM机中的状态迁移。

ATM机的基本状态包含了插卡，输入密码，余额查询，取款，存款，转账，退出这几个基本状态。

其中初始阶段为等待插卡阶段，此阶段等待磁卡的插入；插入以后则系统状态变为插卡状态，此状态判断插入的磁卡是否有效，有效则跳转到输入密码状态，系统状态变为登录状态，此时可以根据需要进行查询、取款、存款、转账等状态的转换；若输入密码错误则继续保持插卡状态等待正确的用户密码；查询状态，直接查询账户余额；取款状态，输入取款金额，此状态需要判断取款金额是否大于账户余额，若大于，则操作失败，返回取款前的状态，若小于，则操作成功，提交事务，更新数据库数据；存款状态，判断放入的钱币是否有假钞和放入钱币的金额，若有假钞，退回到存入之前的操作直到放入的钱币全部为真，清点放入金额，提交事务，更新数据库数据。