[转载]计算理论导引--状态机
计算理论导引--状态机
计算理论导引--状态机
计算理论导引--状态机
有穷自动机的形式定义：有穷自动机是一个5元组：状态集, 字母表, 转移函数, 起始状态, 接受状态。转移函数定义了从一个状态转换到另一个状态的转换规则。
设A是机器M接受的全部字符串，称A是机器M的语言，记作L（M）=A，又称M识别A或M接受A。
设计有穷自动机：
首先，为了能做出这样的判断，必须估算出当读一个字符串时需要记住它的哪些东西。 其次，通过观察怎么根据读到的符号，从一种可能性转移到另一种可能性来设计转移函数。 再次，把起始状态设置为对应于到现在为止，还没有看到任何符号相关联的可能性状态。 最后，把接受状态设置为这样一些状态，它们对应于你打算要接受输入串的可能性。
设A是机器M接受的全部字符串，称A是机器M的语言，记作L（M）=A，又称M识别A或M接受A。
设计有穷自动机：
首先，为了能做出这样的判断，必须估算出当读一个字符串时需要记住它的哪些东西。 其次，通过观察怎么根据读到的符号，从一种可能性转移到另一种可能性来设计转移函数。 再次，把起始状态设置为对应于到现在为止，还没有看到任何符号相关联的可能性状态。 最后，把接受状态设置为这样一些状态，它们对应于你打算要接受输入串的可能性。
正则运算：并、连结和星号，正则语言在正则运算下是封闭的。
非确定性有穷自动机（NFA）：允许读入空时转移。NFA和DFA是等价的，有时构造NFA比构造DFA容易，NFA可能比DFA小得多。
正则表达式的形式定义：
- 字母表中的任何一个元素都是正则表达式。
- e是是正则表达式。
- 空集是是正则表达式。
- 正则表达式并上正则表达式仍是正则表达式。
- 正则表达式连接正则表达式仍是正则表达式。
- 正则表达式重复后仍是正则表达式。
广义的非确定性有穷自动机：转移箭头可以用任何正则表达式来标记。
关于正则语言的泵引理：言多必复。
来自 “ ITPUB博客 ” ，链接：https://blog.itpub.net/374079/viewspace-130610/ ，如需转载，请注明出处，否则将追究法律责任。
上一篇：
[转载]文法和语言的分类
下一篇：
[转载]ZX手机平台的几个问题
请登录后发表评论
登录
全部评论
