现在的位置: 首页 > 综合 > 正文

计算理论导引–状态机

2012年05月18日 ⁄ 综合 ⁄ 共 604字 ⁄ 字号 评论关闭
转载时请注明出处和作者联系方式
作者联系方式:李先静 <xianjimli at hotmail dot com>

有穷自动机的形式定义:有穷自动机是一个5元组:状态集, 字母表, 转移函数, 起始状态, 接受状态。转移函数定义了从一个状态转换到另一个状态的转换规则。

A是机器M接受的全部字符串,称A是机器M的语言,记作LM=A,又称M识别AM接受A

设计有穷自动机:

       首先,为了能做出这样的判断,必须估算出当读一个字符串时需要记住它的哪些东西。
       其次,通过观察怎么根据读到的符号,从一种可能性转移到另一种可能性来设计转移函数。
       再次,把起始状态设置为对应于到现在为止,还没有看到任何符号相关联的可能性状态。
       最后,把接受状态设置为这样一些状态,它们对应于你打算要接受输入串的可能性。  


正则运算:并、连结和星号,正则语言在正则运算下是封闭的。


非确定性有穷自动机(
NFA):允许读入空时转移。NFADFA是等价的,有时构造NFA比构造DFA容易,NFA可能比DFA小得多。 


正则表达式的形式定义:

  1. 字母表中的任何一个元素都是正则表达式。
  2. e是是正则表达式。
  3. 空集是是正则表达式。
  4.  正则表达式并上正则表达式仍是正则表达式。
  5. 正则表达式连接正则表达式仍是正则表达式。
  6. 正则表达式重复后仍是正则表达式。

广义的非确定性有穷自动机:转移箭头可以用任何正则表达式来标记。

关于正则语言的泵引理:言多必复。

抱歉!评论已关闭.