自动机编程历史

自动机编程的技术常用在以自动机原理为基础的算法中，例如形式语言分析[1]。

约翰逊等在1968年发表的《Automatic generation of efficient lexical processors using finite state techniques》论文是早期提到自动机编程的论文[2]。 Peter Naur在1963年的论文将自动机编程当成一种通用的软件技术[3]。作者将此技术称为“图灵机的方法”，不过此论文是以自动机的状态及步骤为基础，没有提到图灵机。

自动机编程有以下的二项特征：

程式执行的时间中可以清楚划分成数个自动机的步骤（step），每一个步骤即为一个程式区段，有单一的进入点，可以是一个函数或其他程序。若有需要时，程式区段可以再依其状态的不同，划分为子区段。

不同步骤的程式区段只能透过一组清楚标示的变量交换资讯，这些变量称为状态（state），使用自动机编程的程式不能用其他不显然可见的方式标示状态，例如区域变量的数值、回传位址、程式指标的位置等。因此一程式在任二个不同时间下的差异，只有状态数值的不同，其余都相同。

自动机编程的执行过程是一个由自动机步骤形成的循环。

自动机编程中处理问题的思考方式很类似在利用图灵机、马尔可夫算法处理问题时的思考方式。

考虑一个C语言的程式，由标准输入流一行一行的读取资料，打印各一行的第一个英文单字。因此一开始需确认第一个英文单字之前是否有空白，若有，需读取所有空白后略过不打印，读取第一个英文单字然后打印，之后读取其他内容略过不打印，直到读到换行符号为止。任何情形下只要读到换行符号，就重新开始此算法，任何情形下只要读到档案结束（end-of-file）的符号，就结束程式。

传统C语言的程式

以下是传统指令式编程的C语言程式：

#include int main(void)

{int c;

do

{

c =getchar();

while(c ==' ') c =getchar();

while(c != EOF && c !=' '&& c !=' ')

{

putchar(c); c =getchar();}putchar(' ');

while(c != EOF && c !=' ') c =getchar();

}

while(c != EOF);return0;}

自动机编程的程式

上述问题也可以用有有限状态机的方式处理，此程式有三个不同的阶段：读取并跳过第一个单字前的空白、读取第一个单字并且打印、跳过后续的所有字符。以下将这三个阶段定义为三个状态before、inside及after。自动机编程的程式如下：

#include int main(void){enum states { before, inside, after } state;int c;、 state = before;while((c =getchar())!= EOF){switch(state){case before:if(c ==' '){putchar(' ');}elseif(c !=' '){putchar(c); state = inside;}break;case inside:switch(c){case' ': state = after;break;case' ':putchar(' '); state = before;break;default:putchar(c);}break;case after:if(c ==' '){putchar(' '); state = before;}}}return0;}

虽然此程式较长，至少有一个明显的好处，程式中只呼叫一个读取字符的getchar()函数，而且程式中只有一个循环，不像之前程式使用四个循环。

此程式中while循环内的程式即为自动机的步骤，而循环本身即可重复的执行自动机的程序。

此程式实现有限状态机，其中 N表示换行字符、 S表示空白、 A表示其他的字符。自动机依状态及读取的字符不同，会执行一个箭头所示的动作，可能是由一个状态跳到下一个状态，也者停在原来的状态。其中有些箭头有标示星号，表示需打印读到的字符。

自动机编程中，不一定要为每一个状态撰写独立的处理程序，而且有时状态是由许多变量组成，无法针对每一个状态规划个别的处理程序。此想法有时有助于程式的精简，例如在上述程式中，不论是在哪一个状态，针对换行字符的处理都一様，因此程式可以先处理换行字符，其他输入字符时才依不同状态进行处理，简化后变成以下的程式：

#include int main(void){enum states { before, inside, after } state;int c; state = before;while((c =getchar())!= EOF){if(c ==' '){putchar(' '); state = before;}elseswitch(state){case before:if(c !=' '){putchar(c); state = inside;}break;case inside:if(c ==' '){ state = after;}else{putchar(c);}break;case after:break;}}return0;}

独立的自动机步骤程式

上述程式的一个重要特点是自动机步骤的程式区块都只使用区域变量，以下的例子将自动机步骤整合为一个独立的函式step()，更可以突显上述的特点：

#include enum states { before, inside, after };void step(enum states *state,int c){if(c ==' '){putchar(' ');*state = before;}elseswitch(*state){case before:if(c !=' '){putchar(c);*state = inside;}break;case inside:if(c ==' '){*state = after;}else{putchar(c);}break;case after:break;}}int main(void){int c;enum states state = before;while((c =getchar())!= EOF){ step(&state, c);}return0;}

此例清楚的呈现自动机编程程式的基本特点：

各自动机步骤程式的执行时间不互相重叠。

前一个步骤和下一个步骤之间所交换的资料只有标示为“自动机状态”的变量（此例中为变量state）。

显式的状态转换表

自动机编程可以用显式的状态转换表来表示。以下的程式中的the_table阵列即为状态转换表，其列表示三个不同的状态，其每一栏对应输入的字符（从左到右分别是空白、换行字符及其他字符）。

对于每一种可能的状态及输入字符的组合，表中有其对应的新状态及一个决定是否否显示输入字符的旗标。在实务的专案中状态转换表可能更为复杂，例如可能包括所有可能条件组合下需呼叫的函式指标。

#include enum states { before =0, inside =1, after =2};struct branch {unsignedchar new_state:2;unsignedchar should_putchar:1;};struct branch the_table[3][3]={/* ' ' ' ' others *//* before */{{before,0},{before,1},{inside,1}},/* inside */{{after,0},{before,1},{inside,1}},/* after */{{after,0},{before,1},{after,0}}};void step(enum states *state,int c){int idx2 =(c ==' ')"para" label-module="para">

自动化技术和自动机

自动机编程相当类似自动化技术领域需要的程式。

制造周期一般会用以下的方式定义：

一串依输入资料决定状态的程序。

依状态输出对应资料的程序。

许多编程语言可以用类似的方式撰写程式。

上述程式可以用此观点改写，以下是改写后程式的虚拟码，其使用关键字和符号说明如下：

'set'是指设定变量（此处为状态）的数值

':'为设定变量，'='是判断是否相等

SPC :' 'EOL :' ' states :(before, inside, after, end) setState(c){if c=EOF then set end if before and (c!=SPC and c!=EOL) then set inside if inside and (c=SPC or c=EOL) then set after if after and c=EOL then set before} doAction(c){if inside then write(c)elseif c=EOL then write(c)} cycle { set before loop { c : readCharacter setState(c) doAction(c)} until end}

上述程式中将更新状态的程式独立为setState函式，另外将依状态和输入更新输出的程式独立为doAction函式，此作法可以产生较清楚及简单的程式码。

[编辑]自动化技术及事件在自动化领域中，步骤之间的切换是依照机器本身的输入资料，在本例中为读到的输入字符，在实务上可能是位置、速度、温度等机器的关键资料。

自动化领域有些设计方式类似图形用户界面的程式设计，机器状态的改变可以视为由事件而造成，由于事件使机器由一个状态变为下一个状态，直到到达最后的状态为止。可能出现状态的组合可以产生许多的事件，因此可以定义较复杂的制造周期，其产生的制造周期一般会比线性循序流程复杂许多。一般常常会有一些同时执行的平行路径，以及依不同事件决定执行方式的路径。

s:状态 c:条件 s1 | |-c2 | s2 | ---------- | | |-c31 |-c32 | | s31 s32 | | |-c41 |-c42 | | ---------- | s4

面向对象程式

若编程语言支援面向对象程式设计，就可以将自动机封装为一个物件，隐藏自动机实现的细节。一种称为“状态模式（英语：State pattern）”的设计模式即包括了此作法。上述的程式可以改为为以下的面向对象程式，利用C 来实现：

#include class StateMachine {enum states { before =0, inside =1, after =2} state;struct branch {enum states new_state:2;int should_putchar:1;};staticstruct branch the_table[3][3];public: StateMachine(): state(before){}void FeedChar(int c){int idx2 =(c ==' ')"para" label-module="para">

注：为了减少和此主题不直接相关的修改，此处的输入输出函数使用C语言的标准函式库，另外，其中的三元运算符

上述自动机接受的语言家族被称为正规语言(Regular Expression)。更强力的自动机可以接受更复杂的语言。比如:

自动机PDA

PDA(下推自动机)这种机器等同于 DFA (或 NFA)，除了它们额外的装备了栈形式的内存。转移函数 δ 也依赖于在栈顶的符号，并在每次转移时指定如何变更栈。非确定 PDA 接受上下文无关语言。

自动机LBA

LBA （线性有界自动机）是有限制的 图灵机；不使用无限磁带，它的磁带有同输入字元串成正比的空间。LBA 接受上下文有关语言。

自动机图灵机

它们是最强力的电脑器。它们拥有磁带形式的无限内存，和可以读取和变更磁带的磁头，它可在磁带上向任何方向移动。图灵机等价于演算法，是现代电脑的理论基础。图灵机判定递归语言并识别递归可枚举语言。

下面是三类有限自动机

确定有限自动机(DFA)

自动机的每个状态都有对字母表中所有符号的转移。

非确定有限自动机(NFA)

自动机的状态对字母表中的每个符号可以有也可以没有转移，对一个符号甚至可以有多个转移。自动机接受一个字，如果存在至少一个从 q0 到 F 中标记(label)著这个输入字的一个状态的路径。如果一个转移是「未定义」的，自动机因此不知道如何继续读取输入，则拒绝这个字。

有ε转移的非确定有限自动机(FND-ε或ε-NFA)

除了有能力对任何符号跳转到更多状态或没有状态可以跳转之外，它们可以做根本不关于符号的跳转。就是说，如果一个状态有标记著 ε 的转移，则 NFA 可以处在 ε-转移可到达的任何状态中，直接或通过其他有 ε-转移的状态。从一个状态 q 通过这种方法可到达的状态的集合叫做 q 的 ε-闭包。

尽管可以证明所有这些自动机都「可以接受同样的语言」。你总是可以构造接受与给定的 NFA M 同样语言的某个 DFA M。

自动机是有限状态机(FSM)的数学模型。

FSM 是给定符号输入，依据(可表达为一个表格的)转移函数“跳转”过一系列状态的一种机器。在常见的 FSM 的“Mealy”变体中，这个转移函数告诉自动机给定当前状态和当前字符的时候下一个状态是什么。

逐个读取输入中的符号，直到被完全耗尽(把它当作有一个字写在其上的磁带，通过自动机的读磁头来读取它；磁头在磁带上前行移动，一次读一个符号)。一旦输入被耗尽，自动机被称为“停止”了。

依赖自动机停止时的状态，称呼这个自动机要么是“接受”要么“拒绝”这个输入。如果停止于“接受状态”，则自动机“接受”了这个字。在另一方面，如果它停止于“拒绝状态”，则这个字被“拒绝”。自动机接受的所有字的集合被称为“这个自动机接受的语言”。

自动机 automaton 原来是模仿人和动物的行动而做成的机器人的意思。但是现已被抽象化为如下的机器。时间是离散的（t=0，1，2……），在每一个时刻它处于所存在的有限个内部状态中的一个。对每一个时刻给予有限个输入中的一个。那么下一个时刻的内部状态就由现在的输入和现在的内部状态所决定。每个时刻的输出只由那个时刻的内部状态所决定。作为自动机的例子可以举出由McCulloch-pitts的神经模型组合所得到的神经网络模型、数字计算机等。