[求教] 什么是有限状态自动机

Perlvim

看了很多资料，都搞不懂这是个什么东西，有什么用，谁能用简单一些的言语描述一下。千万别用算法导论里面的词汇。

linux_c_py_php

不懂, 只做过AC自动机的题目, 是否算有限.

Perlvim

人做出来的东西，都是有限。说说无妨

sonicling

它是一种模型，代表一种计算模式，就是那种用有限个状态就能表达的计算。

你能理解“状态”和“无限状态”吗？绝大部分的计算都是无限状态的。

JohnBull

把问题的求解过程划分成离散的“状态”，并用一个有向图建立状态（结点）的迁移关系。
实现一个程序单位，在给定初始状态后，能够根据输入信息实现状态间的迁移，并可以在有限步骤后迁移到预定的“终态”。
在迁移的过程中，问题得到解决。

Perlvim

无限状态，通常说有很多状态，很难一一列明。

有限状态机在语法解析中应用，我理解的是：
通常输入的一个队列的token, 输出的是一个抽象语法树。
要么就说：语法错误，就退出了。

Perlvim

JohnBull 发表于 2013-02-27 18:32
把问题的求解过程划分成离散的“状态”，并用一个有向图建立状态（结点）的迁移关系。
实现一个程序单位， ...

您的抽象思维能力比我高几个数量级，我实在无法理解这么抽象的言语。

fender0107401

JohnBull 发表于 2013-02-27 18:32
把问题的求解过程划分成离散的“状态”，并用一个有向图建立状态（结点）的迁移关系。
实现一个程序单位， ...

描述的很好。

fender0107401

Perlvim 发表于 2013-02-27 17:48
看了很多资料，都搞不懂这是个什么东西，有什么用，谁能用简单一些的言语描述一下。千万别用算法导论里面的 ...

你去看看英文的Wiki。

sonicling

Perlvim 发表于 2013-02-27 18:33
无限状态，通常说有很多状态，很难一一列明。

有限状态机在语法解析中应用，我理解的是：

错了，有限状态机用于词法分析，判断词性用的。字典中词条的数目是有限的，所有单词的长度也是有限的，所以可以用有限状态表示。语言可是无限的，你怎么用有限状态表示？

这里的状态有两种：一种是狭义状态，就是定义模型时说的状态，就是一个编号；另一个是广义状态，当把模型看作一个抽象机时，这个抽象机在每个时刻的数据快照构成这个时刻的状态。

有限状态机的狭义状态和广义状态指的是同一个东西，因为有限状态机只存储一个数据：就是当前的那个狭义状态（状态编号）。

下推自动机的狭义状态和有限状态机一样，也是有限的，但是它可不止存储一个状态，它有一个状态堆栈，这个堆栈是无限的！它的数据快照有无限多种可能，所以它的广义状态是无限的。

图灵机的狭义状态是图灵机指令的位置。图灵机程序一定是有限长的，所以图灵机的狭义状态也是有限的。但是图灵机不光存储当前的狭义状态，它还有一条（或多条）纸带，虽然每个格子上的字母数目是有限的，但是纸带的长度是无限的，所以图灵机的广义状态也是无限的。