加载中…
个人资料
太极儒
太极儒
  • 博客等级:
  • 博客积分:0
  • 博客访问:136,301
  • 关注人气:38
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

从有限状态机、图灵机到现代计算机(二)

(2010-02-05 03:45:22)
标签:

杂谈

分类: 学习工作

有限状态机示例:

有限状态机在现实生活中其实随处可见,伸缩式圆珠笔其实就是一个有限状态机(两种状态互相转换),下面我们用实现一个简单的有限状态机-自动门。

要求如下:有一自动门,它可以被锁上,也可以开锁。当门锁上时,某人可以在它的槽中塞进一枚硬币。这样,门就会自动开锁,转变到开锁的状态;人通过后,门就会自动锁上。

对状态进行分析可得下图:

 

 

  从有限状态机、图灵机到现代计算机(二) 

 

仿真代码:

LIBRARY IEEE;

USE IEEE.std_logic_1164.ALL;

 

ENTITY door_contr IS

PORT (

     clk,reset,coin,pass:   IN  std_logic;

     door,alarm,thank:    OUT std_logic

);

END door_contr;

 

ARCHITECTURE behavior OF door_contr IS

  TYPE states IS (lock,unlock);

  SIGNAL next_state: states;

  BEGIN

PROCESS (clk)

  BEGIN

    IF (reset = '1') THEN

      next_state <= lock;

      alarm <= '0';

      thank <= '0';

      door <= '0';

    ELSIF (clk'EVENT AND clk = '1') THEN

      CASE next_state IS     

      WHEN lock =>

        IF (coin = '1') THEN

          next_state <= unlock;

          thank <= '0';

          alarm <= '0';

          door <= '1';

        ELSIF (pass = '1') THEN

          next_state <= lock ;

          thank <= '0';

          alarm <= '1';

          door <= '0';

        END IF;              

      WHEN unlock =>

        IF (coin = '1') THEN

          next_state <= unlock;

          thank <= '1';

          alarm<= '0';

          door <= '1';

        ELSIF (pass = '1') THEN

          next_state <= lock;

          thank <= '0';

          alarm <= '0';

          door <= '0';

        END IF;

      END CASE;

    END IF;

  END PROCESS;

END behavior;

  

QuartusⅡ下的仿真结果:

 

 

 从有限状态机、图灵机到现代计算机(二)



 

当然,上面讲述的还是一个没有停止状态的有限状态机,而且是由电子电路实现的,接下来的例子是在软件方面具有有限状态的有限状态机。

这是一个地址识别的算法。日常我们描述地址(指中文)的语句中地址级别是依次降低的,国家、省(直辖市)、市、区县、街道、门牌号(或者从区县之后是乡、村)。而这些就是我们要构造的有限状态机的全部状态。这些状态构成的状态图是单向图,比如,当前的状态是,如果遇到一个词组(即输入)和市名有关,我们就进入状态相应(即状态转换);走到最低级的地址单位(即终止状态),那么这条地址是有效的,否则无效。比如说,北京市海淀区清华大学紫荆公寓2#”对于上面的有限状态机来讲有效,而上海市辽宁省石家庄市则无效(因为无法从市走回到省,即便可以也会由于石家庄市不属于辽宁省而进入错误状态)。

使用有限状态机识别地址,关键要解决两个问题,即通过一些有效的地址建立状态机,以及给定一个有限状态机后,地址字串的匹配算法,而这两个问题都有现成的算法。有了关于地址的有限状态机后,我们就可又用它分析网页,找出网页中的地址部分,建立本地搜索的数据库。同样,我们也可以在搜索引擎中对用户输入的查询进行分析,挑出其中描述地址的部分,当然,剩下的关键词就是用户要找的内容。

以上就是有限状态机的实际应用,这让我们感到它的功能的确很强大。其实想想看,无论对连续系统还是离散系统,状态概念无所不在,有限状态机提供了一种描述和控制应用逻辑的非常强大的方法,具有规则简单、可读性和可验证性强等特点。

 

有限状态机的弱点

 

1、 每一种有限状态机均功能唯一,即设计好之后无法完成其他原理不同的工作;

2、 因为其状态有限,当所要描述的系统的状态太多时,可能确定的有限状态机无能为力;

3、 有一些任务是有限状态机无法完成的,比如它可以判断输入的01数列中01的个数是否为奇数或偶数,但是无法判断0是否比1多或者相反。

前两个问题表示有限状态机的可扩展性差(或者对比计算机而言是无可编程性),而后者是因为有限状态机状态有限而且不能记下自己需要记录的东西(或者对比图灵机理论是不能写)。

于是我们发现有限状态机不但状态有限,功能也有限(根据计算理论,这是因为它只能接受正则语言,而正则语言是最低级的语言,所以能够解决的问题是有限的)。

事实上,最初的计算“机”(其实更应该说是计算器)都是功能单一的,虽然人们不断地试图在一台机器上集成更多的功能,但是相对于下面要讲到通用计算理论,这些行为还是“盲目”的。(to be continued)

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有