下载文档原格式
离散数学有限自动机模型应用举例离散数学是数学的一个分支，主要研究离散对象和离散关系。
而有限自动机是离散数学中的重要概念之一，用于描述具有有限数量的状态和状态之间的转换关系。
有限自动机模型在计算机科学和其他领域中有着广泛的应用。
本文将从几个具体的应用案例来探讨离散数学有限自动机模型的应用。
案例一：自动售货机自动售货机是我们日常生活中常见的一种自动化设备。
它通过有限自动机模型来实现对商品的管理和售卖。
假设自动售货机有3个状态，分别为“待机”、“选择商品”和“完成交易”。
当用户投入硬币后，自动售货机会从“待机”状态转换为“选择商品”状态，用户可以通过按下相应按钮来选择商品。
一旦用户选定商品，自动售货机将通过有限自动机模型转换到“完成交易”状态，并同时释放商品和找零。
这个案例清晰地展示了有限自动机模型如何应用于自动售货机的控制。
案例二：电话拨号电话拨号也是离散数学有限自动机模型的一个应用。
在传统电话中，数字键盘上有10个数字按钮和几个特殊按钮（如*和#）。
每次按下一个按钮时，电话系统都会根据当前状态和按下的按钮进行状态转换。
例如，当你拨号时，初始状态为“待命”状态，按下数字按钮后，系统将从“待命”状态转移到“拨号中”状态，并显示所拨的号码。
这个过程中，电话系统一直在根据当前状态和按下的按钮进行状态转换，直到通话结束。
这种电话系统的设计正是基于离散数学有限自动机模型，它能够准确地响应用户的操作。
案例三：词法分析器在计算机科学中，词法分析器是编译器的一个基本组成部分，用于将源代码分解为有意义的元素（如标识符、关键字和运算符）。
离散数学有限自动机模型可以用来构建词法分析器。
通过使用有限自动机，可以将源代码作为输入，并根据代码的语法规则将其分解为不同的词法单元。
例如，当遇到空格时，词法分析器将从初始状态转换到“空格”状态，并且继续分析后续字符。
同样地，当遇到标识符或关键字时，词法分析器将进行相应的状态转换并识别它们。
事件驱动状态机实例讲解-回复什么是事件驱动？事件驱动（Event-driven）是一种计算机编程范例，它通过响应事件的方式来控制程序的执行流程。
事件驱动编程是一种反应性编程方法，它基于事件的发生而触发相应的处理流程。
在事件驱动的程序中，程序状态通常是静态的，只有当外部事件发生时，程序才会进入相应的处理流程，执行相关的代码。
事件驱动的编程模型可以适用于多种情况，如图形用户界面（GUI）开发、网络编程、服务器开发等。
在这些场景下，用户的操作、网络请求、外部设备的输入等都可以被视为事件，并通过事件驱动模型进行处理。
不同于传统的顺序编程模型，事件驱动模型具有以下几个特点：1. 程序按照事件顺序响应：程序会等待事件发生，然后根据事件的顺序依次进行处理。
事件驱动编程通常具有异步的特性，即不会一直等待事件的发生，而是可以同时处理多个事件。
2. 事件处理是离散的：每个事件都会有相应的处理流程，事件之间是相互独立的。
这使得程序能够更好地适应外部环境的变化。
3. 事件驱动编程具有高度的灵活性和可扩展性：由于事件驱动模型基于事件的发生来触发相应的处理流程，使得程序可以根据实际需求进行动态调整和扩展。
4. 事件驱动模型对并发和并行编程友好：事件驱动编程天然支持多线程、多任务并发执行。
不同的事件可以由不同的线程或进程处理，从而提高程序的执行效率和响应性。
什么是状态机？状态机（State machine）是一种将系统行为建模的数学模型。
它描述了一个系统的内部状态以及状态之间的转换规则。
状态机由一组状态和状态转移构成，状态表示系统所处的状态，转移表示状态之间的切换。
状态机可以分为两种类型：有限状态机（Finite-state machine，FSM）和无限状态机（Infinite-state machine）。
有限状态机中，状态的数量是有限的，系统的状态会在不同的输入条件下从一个状态转移到另一个状态，形成一个状态转移图。
无限状态机中，状态的数量是无限的，系统的状态可能具有连续性或无规律性。
Digital System Design12011/6/21Computer Faculty of Guangdong University of Technology例：用三进程状态机实现一个简单自动售货机控制电路，电路框图如下。
该电路有两个投币口（1元和5角），商品2元一件，不设找零。
In[0]表示投入5角，In[1]表示投入1元，Out 表示是否提供货品。
Digital System Design22011/6/21Computer Faculty of Guangdong University of Technology根据题意，可分析出状态机的状态包括： S0（00001）：初始状态，未投币或已取商品 S1（00010）：投币5角 S2（00100）：投币1元 S3（01000）：投币1.5元 S4（10000）：投币2元或以上用独热码表示状态编码，如上所示。
相应状态转换图如下（按Moore 状态机设计）。
Digital System Design32011/6/21Computer Faculty of Guangdong University of Technology自动售货机状态转换图Digital System Design42011/6/21Computer Faculty of Guangdong University of Technology设计代码第一个Always 块：状态转移。
Digital System Design52011/6/21Computer Faculty of Guangdong University of Technology第二个Always 块：状态转移的组合逻辑条件判断Digital System Design62011/6/21Computer Faculty of Guangdong University of Technology第三个Always 块：输出组合逻辑Digital System Design72011/6/21Computer Faculty of Guangdong University of Technology测试平台代码Digital System Design82011/6/21Computer Faculty of Guangdong University of Technology功能仿真结果Digital System Design92011/6/21Computer Faculty of Guangdong University of Technology综合结果。
1有限状态机有限状态机(Finite State Machine )是一种具有内部记忆的抽象机器模型，是时序电路的一种，通过有限状态机课实现高效率高可靠逻辑控制。
根据输出与输入关系、系统状态的关系，有限状态机又可以分为Moore型有限状态机和Mealy型有限状态机。
Moore型状态机的输出信号只于当前的状态有关；Mealy型状态机是输出信号不仅与当前的状态有关，还与输入信号有关。
Mealy机的示意图如图二所示：Mealy图二Mealy机的示意图Moore机的示意图如图三所示：Moore图三Moore机的示意图Moore型有限状态机和Mealy型有限状态机的区别：•在Moore机中，输出的时钟活动沿到达后的几个门电路的延迟时间之后即到达，并且在该时钟周期的剩余时间内保持不变，即使输入在该时钟周期内发生变化，输出值也保持不变。
然而，因为输出与当前的输入无关，当前输出产生的任何效果将延迟到下一个时钟周期。
Moore机的优点是将输出与输入分隔开。
einepde r registeroutputencoderoutputregisteroutputencoderoutput• 在Mealy 机中，因为输出是输入的函数，如果输入改变，则输出可以在下一个时钟周期的中间发生改变。
这使得Mealy 机比Moore 机，对输入变化的响应要早一个时钟周期，一旦输入信号或状态发生变化，输出信号随着输入信号变化。
• 实现同样功能，Moore 机要比Mealy 机需要更多的状态。
通过分析本次实验，利用Mealy 机更加容易理解，并且使用Moore 会使用更多的状态，所以本次实验使用Mealy 型有限状态机。
2 Soda Machine机的设计2.1 Soda Machine机的状态转换图Soda Machine 机的状态转换图如图四所示。
Soda Machine图四Soda Machine 机的状态转换图图中共有10个状态，为ST0 — ST9。
实验项目名称：有限状态机指导教师：实验日期：实验概述：【实验目的及实验设备】实验目的：(1)掌握有限状态机的应用方法。
(2)掌握有限状态机的静态测试方法，能够进行程序设计。
(3)学习测试模块的编写,综合和不同层次的仿真。
(4)用有限状态机设计一个自动售货机（饮料价格为2.5元）。
实验设备及仪器名称：CPU型号:英特尔*****************************操作系统类型:Windows XP SP3仿真软件:MAX Plus 2软件、Modelsim SE-64 10.0c实验内容及步骤：【实验原理及电路图】系统能够根据用户输入的硬币，判断钱币是否足够，当所投硬币达到或者超过购买者所选面值时，则根据顾客的要求自动售货，并找回剩余的硬币，然后回到初始状态，当所投硬币面值不够时，则给出提示，并通过一个复位键退回所投硬币。
然后回到初始状态。
该实验输入有4个clk，reset，表示投一元币y，表示投五角币w。
输出有2个，表示饮料出现的out和找五角钱的w_out.该实验共5个状态，s0:表示投币为0的状态，s1：表示投入5角的，s2：表示投入1元，s3：表示投入1.5元，s4：表示投入2元。
当投入2.5时out输出1，状态回到s0，当投入3元时out 和w_out都输出1，状态回到s0.【实验方案】（实验步骤，记录）1、打开Modelsim SE-64 10.0c软件。
else beginout=0;w_out=0;s=s4;endendcaseendendmodule测试程序：module shou;wire y;reg w;reg reset;reg clk;paramerer clkperiod=100;shouhuoji shou(y,w,reset,clk)initial beginw=0;clk=0;reset=1;#150 reset=0;#100 reset=1;endalways#(clkperiod/2) clk=~clk;always#(clkperiod+30) $random;initial $monitor(Stime, “y=%b”,y);endmodule3、编译并调试程序，出现错误立即修改直至无错误出现。
自动售货机VerilogHDL程序一个简单的自动售卖饮料机的程序.该机器具有投币，显示余额，购买六种饮料，退钱等功能,为了更具实用性，增添了饮料选择允许提示和投币允许提示的功能。
具体形容,可投入一元、五元、十元和二十元面值的钱币，显示出当前的余额，并根据当前的余额提示能购买哪些饮料，选择某种饮料，则输出选定的饮料，同时余额减去相应的金钱.若选择退钱，机器就退出所有的钱，余额清零.下图为功能示意图:程序的状态表:程序中包含了一个状态机,定义了一个任务（task）和函数（function），用该任务调用了该函数,使用若干分支语句,详见附后源程序和测试程序。
附上程序编译仿真图：源程序如下:`define one 3'b001`define five 3'b010`define ten 3'b011`define twenty 3’b100module automart(money，state，moneyout，coinable，adrkable,bdrkable，cdrkable,drkout1，drkout2，drkout3，drkout4,drkout5，drkout6,coin,clk，reset，moneyback,choice1,choice2,choice3，choice4,choice5,choice6)；input［2:0］coin;//投币输入，分为1、5、10、20元四种输入input clk,reset,moneyback，choice1,choice2，choice3,choice4,choice5，choice6；//moneyback为退钱输入,choice1~6是饮料选择output moneyout,coinable，adrkable,bdrkable，cdrkable,drkout1,drkout2，drkout3，drkout4，drkout5，drkout6;//依次为退钱输出，投币许可提示,饮料选择许可,6种饮料输出output［2:0] state;//状态记录output[7：0] money;//余额显示reg［7:0] money；reg［2:0] state；reg moneyout,coinable，backable,adrkable，bdrkable,cdrkable; parameter A=3'b000，B=3'b001，C=3'b010,D=3'b011，E=4’b100；assign drkout1=choice1＆adrkable；assign drkout2=choice2&adrkable；assign drkout3=choice3&bdrkable;assign drkout4=choice4＆bdrkable;assign drkout5=choice5&cdrkable;assign drkout6=choice6&cdrkable;always@（posedge clk）repeat(1）＠（posedge clk）if （！reset)beginstate<=A；money=0;moneyout=0;endelsebegincase（state)A：begin//初始状态A,可投币进入别的状态coinable=1；backable=0；adrkable=0；bdrkable=0;cdrkable=0;endB: begin//状态B,只能买1元的饮料，可退钱或投币coinable=1;backable=1;adrkable=1；bdrkable=0；cdrkable=0;endC: begin//状态C，可买1或2元的饮料，退钱或投币coinable=1;backable=1;adrkable=1；bdrkable=1；cdrkable=0;endD：begin//状态D，可买三档价格饮料，可退钱或投币coinable=1;backable=1;adrkable=1；bdrkable=1;cdrkable=1;endE：begin//状态E，可买三档价格饮料，可退钱，不可继续投钱coinable=0;backable=1；adrkable=1；bdrkable=1;cdrkable=1；enddefault: state=A;endcasecondition(money，state,coin，coinable）;//调用任务endalways@(negedge drkout1 or negedge drkout2）money=money—8’h01;//买1元的饮料,余额减1元always＠（negedge drkout3 or negedge drkout4)money=money—8'h02;//买2元的饮料，余额减2元always＠（negedge drkout5 or negedge drkout6）money=money—8'h04；//买4元的饮料，余额减4元always@(negedge moneyback)beginif（backable)beginmoneyout=1；money=0;//选择退钱,则推出金钱，余额清零endelsemoney=money+0;endtask condition；//该任务可以判断余额的改变,状态切换inout[7：0] moneycon;inout[2：0] statecon；input［2:0] coincon；input coinablecon;beginif (coinablecon）//允许投币时begincase （coincon）//根据投币面值改变余额，切换状态`one : moneycon=moneycon+8'h01；`five ：moneycon=moneycon+8'h05；`ten : moneycon=moneycon+8'h0a;`twenty ：moneycon=moneycon+8'h14;default：moneycon=moneycon+0；//无投币则余额不变endcasestatecon=condition_s（moneycon）；//调用函数endelse if （moneycon〈8’h14）//不允许投币时，根据余额变化statecon=condition_s(moneycon);//直接切换状态endendtaskfunction ［2:0] condition_s;//根据余额的值切换状态的函数input ［7：0] money_s；reg ［7：0］money_s；beginif （money_s==0）condition_s=A;else if(money_s==8’h01)condition_s=B；else if(money_s==8’h02||money_s==8’h03)condition_s=C；else if(money_s〉=8’h04&＆money_s〈8’h14）condition_s=D;else condition_s=E;endendfunctionendmodule测试程序如下:`timescale 100ns/1ns`define clk_cycle 50module test;reg moneyback，choice1,choice2，choice3，choice4，choice5，choice6; reg [2:0] coin;reg clk,reset；wire[7：0] money;wire[2：0］state;wire moneyout,coinable，adrkable，bdrkable，cdrkable,drkout1，drkout2,drkout3，drkout4，drkout5,drkout6;parameter one=3’b001,five=3’b010,ten=3'b011，twenty=3'b100;always ＃`clk_cycle clk= ~clk;initialbegincoin=0;moneyback=0;clk=0；choice1=0；choice2=0；choice3=0；choice4=0;choice5=0;choice6=0；reset=1;#10 reset=0;＃200 reset=1；＃400 coin=one；//投币1元，#220 coin=0；#200 coin=one;//投1元，余额2元＃220 coin=0；＃200 coin=five;//投5元,余额7元#220 coin=0；＃200 coin=twenty;//投20元，余27＃220 coin=0；#200 choice1=1；//买1元饮料，余26＃220 choice1=0;＃200 choice3=1;//买2元饮料,余24#220 choice3=0;＃200 choice4=1；//买2元饮料，余22#220 choice4=0;＃200 choice5=1；//买4元饮料，余18#220 choice5=0;#200 choice6=1；//买4元饮料，余14＃220 choice6=0；#200 choice6=1;//买4元饮料，余10＃220 choice6=0;#200 choice6=1;//买4元饮料，余6#220 choice6=0；＃200 choice6=1；//买4元饮料,余2#220 choice6=0；＃200 coin=five;//投5元，余7＃220 coin=0；#200 moneyback=1；//退钱＃220 moneyback=0;endautomart m（.money（money），。
Digital System Design
1
2011/6/21
Computer Faculty of Guangdong University of Technology
例：用三进程状态机实现一个简单自动售货机控制电路，电路框图如下。
该电路有两个投币口（1元和5角），商品2元一件，不设找零。
In[0]表示投入5角，In[1]表示投入1元，Out 表示是否提供货品。
自动 售货机
In[0] In[1] Clk Reset
Out
自动售货机顶层结构框图
Digital System Design
2
2011/6/21
Computer Faculty of Guangdong University of Technology
根据题意，可分析出状态机的状态包括： S0（00001）：初始状态，未投币或已取商品 S1（00010）：投币5角 S2（00100）：投币1元 S3（01000）：投币1.5元 S4（10000）：投币2元或以上
用独热码表示状态编码，如上所示。
相应状态转换图如下（按Moore 状态机设计）。
Digital System Design
3
2011/6/21
Computer Faculty of Guangdong University of Technology
xx/1
01/0 10/0
10/0
01/0
01/0
S1
S0
S4
S2
Reset
自动售货机状态转换图
10/0
S3
01/0
x1/0
Digital System Design
4
2011/6/21
Computer Faculty of Guangdong University of Technology
设计代码
第一个Always 块：状态转移。
`timescale 1ns/100ps
module saler_3always(Reset,Clk,In,Out); input Clk,Reset; input [1:0] In; output Out; reg Out;
reg [4:0] state, next_state;
parameter S0=5'b00001, S1=5'b00010, S2=5'b00100, S3=5'b01000,S4=5'b10000; always @(posedge Clk or posedge Reset)
Digital System Design
5
2011/6/21
Computer Faculty of Guangdong University of Technology
begin if (Reset) state<=S0; else
state<=next_state; end
第二个Always 块：状态转移的组合逻辑条件判断
always @(state or In) begin case(state)
S0:begin if (In[1]) next_state<=S2;
Digital System Design
6
2011/6/21
Computer Faculty of Guangdong University of Technology
else if(In[0]) next_state<=S1;
else
next_state<=S0; end S1:begin if (In[1]) next_state<=S3; else if(In[0]) next_state<=S2; else
next_state<=S1;
end S2:begin if (In[1]) next_state<=S4; else if(In[0]) next_state<=S3;
else
next_state<=S2; end S3:begin
if (In[0]|In[1]) next_state<=S4;
Digital System Design
7
2011/6/21
Computer Faculty of Guangdong University of Technology
else
next_state<=S3; end S4:begin
next_state<=S0;
end
default:next_state<=S0; endcase end
第三个Always 块：输出组合逻辑
always @(state ) begin
case(state) S0:begin
Out<=0; end S1:begin Out<=0;
Digital System Design
8
2011/6/21
Computer Faculty of Guangdong University of Technology
end S2:begin
Out<=0;
end S3:begin Out<=0; end
S4:begin
Out<=1;
end
default:Out<=0; endcase end endmodule
测试平台代码
Digital System Design
9
2011/6/21
Computer Faculty of Guangdong University of
Technology
`timescale 1ns/1ns module testbench_saler; reg clk,reset; reg [1:0] in; wire out;
parameter DELY=20; saler_3always
tb(.Clk(clk),.Reset(reset),.In(in),.Out(out)); always #(DELY/2) clk = ~clk; initial begin
clk=0; reset=0;
#20 reset=1;
#20 reset=0;
end
initial begin in=0; repeat(20)
#20 in=$random; end
Digital System Design
10
2011/6/21
Computer Faculty of Guangdong University of
Technology
initial #400 $finish;
endmodule
功能仿真结果
Digital System Design 11
2011/6/21 Computer Faculty of Guangdong University of Technology
综合结果
Digital System Design Array
12
2011/6/21 Computer Faculty of Guangdong University of
Technology。
