美文网首页
8.1 有穷自动机

8.1 有穷自动机

作者: 马小跳_ | 来源:发表于2018-12-20 21:05 被阅读6次

在固定字符串的处理上,正则表达式的速度是赶不上简单字符串处理的;如果要进行复杂多变的字符处理,正则表达式的速度则要胜于简单字符串处理,比如正则表达式a(bb)+a,它能匹配的字符串是abba、abbbba、abbbbbba....,如果用简单的字符串匹配算法,我们可能需要逐个寻找可能的形态,此类尝试不知道要进行多少次,效率自然大打折扣。本章就是要了解正则表达式的匹配原理

正则表达式能迅速进行复杂处理的秘密就在于,它采用了一种特殊的理论模型:有穷自动机(finite automata),也叫做有穷状态自动机(finite-state machine)。这种机器具备有限个状态,可以根据不同条件在状态之间转移。

卖饮料的自动售货机就是一种有穷自动机:假设其中的饮料价格都是整数元,而且只接受5块钱的纸币,根据余额的不同,可能状态有6个:5元、4元、3元、2元、1元、0元。你塞进去5块钱,此时的状态就是“5元”,点了一罐可乐,花去3元,于是切到状态“2元”,这时你按下退币,就把剩下的2元退给你,并把状态切换到“0元”,“0元”这个状态也叫做“最终状态”。到此,这一轮状态结束,如果你再塞5块钱,就开始新的一轮状态转移。

严格的说起来,有穷自动机必须满足4个条件:

  1. 具有有限多个状态
  2. 有一套状态转移函数(规则)
  3. 有一个开始状态
  4. 有一个或多个最终状态

我们说自动售货机是一种有穷自动机,就是因为它满足这4个条件:

  1. 具有有限多个状态(0-5元 六个状态)
  2. 有一套状态转移函数(比如越为3,买了一罐2元的饮料,则转移状态到“1元”,如果选择买4元的饮料,则提示余额不足,状态并不变化)
  3. 有一个开始状态(余额5元)
  4. 有一个或多个最终状态(余额0元)

在固定字符串的处理上,正则表达式的速度是赶不上简单字符串处理的;如果要进行复杂多变的字符处理,正则表达式的速度则要胜于简单字符串处理,比如正则表达式a(bb)+a,它能匹配的字符串是abba、abbbba、abbbbbba....,如果用简单的字符串匹配算法,我们可能需要逐个寻找可能的形态,此类尝试不知道要进行多少次,效率自然大打折扣。本章就是要了解正则表达式的匹配原理

正则表达式能迅速进行复杂处理的秘密就在于,它采用了一种特殊的理论模型:有穷自动机(finite automata),也叫做有穷状态自动机(finite-state machine)。这种机器具备有限个状态,可以根据不同条件在状态之间转移。

卖饮料的自动售货机就是一种有穷自动机:假设其中的饮料价格都是整数元,而且只接受5块钱的纸币,根据余额的不同,可能状态有6个:5元、4元、3元、2元、1元、0元。你塞进去5块钱,此时的状态就是“5元”,点了一罐可乐,花去3元,于是切到状态“2元”,这时你按下退币,就把剩下的2元退给你,并把状态切换到“0元”,“0元”这个状态也叫做“最终状态”。到此,这一轮状态结束,如果你再塞5块钱,就开始新的一轮状态转移。

严格的说起来,有穷自动机必须满足4个条件:

  1. 具有有限多个状态
  2. 有一套状态转移函数(规则)
  3. 有一个开始状态
  4. 有一个或多个最终状态

我们说自动售货机是一种有穷自动机,就是因为它满足这4个条件:

  1. 具有有限多个状态(0-5元 六个状态)
  2. 有一套状态转移函数(比如越为3,买了一罐2元的饮料,则转移状态到“1元”,如果选择买4元的饮料,则提示余额不足,状态并不变化)
  3. 有一个开始状态(余额5元)
  4. 有一个或多个最终状态(余额0元)

自动售货机并不关心你买了什么商品,也不关心你的选择顺序,无论你买什么,它总处在这六个状态之一,只需要根据状态转移函数在其中转移即可。每一个状态下都可以直接退币,所以有一个转移函数直达最终状态。

自动售货机并不关心你买了什么商品,也不关心你的选择顺序,无论你买什么,它总处在这六个状态之一,只需要根据状态转移函数在其中转移即可。每一个状态下都可以直接退币,所以有一个转移函数直达最终状态。

相关文章

  • 8.1 有穷自动机

    在固定字符串的处理上,正则表达式的速度是赶不上简单字符串处理的;如果要进行复杂多变的字符处理,正则表达式的速度则要...

  • 第八章 匹配原理

    8.1 有穷自动机 正则表达式能迅速进行复杂处理的秘密就在于,它采用了一种特殊的理论模型:有穷自动机(finite...

  • 编译器笔记6-词法分析-有穷自动机

    一 有穷自动机 (Finite Automata) 简介 有穷自动机(Finite Automata,FA)由两位...

  • JavaScript 有穷自动机实现

    有穷自动机实现##

  • NFA到DFA的转换及DFA的简化

    还不太了解有穷自动机或是NFA的同学可以先看我的上一篇文章:正则到NFA的转换 确定型有穷自动机 确定型有穷自动机...

  • 第二章第3节 有穷自动机

    有穷自动机 有穷自动机(Finite Automata ,FA) 由两位神经物理学家 MeCuloch 和 Pit...

  • python实现DFA模拟程序

    DFA(确定的有穷自动机) 一个确定的有穷自动机M是一个五元组: K是一个有穷集,它的每个元素称为一个状态。 ∑是...

  • 有穷自动机

    前言 计算理论要面对的第一个问题是:什么是计算机?现实的计算机相当复杂,很难直接为它们建立一个容易处理的数学理论,...

  • 丘奇-图灵论题

    计算机通用模型 4.1 图灵机 图灵机与有穷自动机相似,但图灵机有一个无限存储。 有穷自动机与图灵机之间的区别: ...

  • 泵引理

    前言 要了解有穷自动机的能力,就必须要了解它们的局限性。我们知道能被一台有穷自动机识别的语言被称为正则语言,但在很...

网友评论

      本文标题:8.1 有穷自动机

      本文链接:https://www.haomeiwen.com/subject/zliukqtx.html