有限状态自动机

大家好，欢迎来到IT知识分享网。

目录

有限状态自动机

前言

• 输入一个字符串，判断其是否是合法的C语言标识符
• 输入一个字符串，判断其是否是$a^n{b}^n{c}^n$形式(即先输入a、在输入b、最后输入c，且输入的a，b，c的个数相同)
• 读取C源代码，去除注释；
• … …
• 针对类似的字符串识别，处理问题，建立有限状态自动机模型，可以为分析、求解带来很大的帮助。

基本概念

例1:打电话(自动机在通信领域的应用)

在一次呼叫中，从建立连接到通话完毕，要经历摘机，拨号，应答，进行通话等过程，话机的状态及状态迁移如下所示。

例2:串口通信

两台微机通过串口通信, 需在两台机器间建立好连接后，才可以传递数据，可以使用有限状态自动机，描述串口通信的状态。

电话和串口都可抽象为有限自动机

1. 对象处于某一相对稳定的状态
2. 某个事件(输入)发生
3. 这一事件引起一串处理发生，包括执行特定的功能，产生相应的输出等
4. 处理结束，对象迁移到一个新的相对稳定状态

什么是有限状态自动机

• 是一种具有离散输入/输出系统的数学模型，简称 有限自动机。这一系统具有任意有限数量的内部“状态”。
• 状态:一个标识，能区分自动机在不同时刻的状况。有限状态系统具有任意有限数目的内部“状态”
• 自动机接受一定的输入，执行一定的动作，产生一定的结果。
• 自动机的本质:根据状态、输入和规则决定下一个状态
  • 状态 +输入(激励)+规则 -> 状态迁移
  • 可能的状态、运行的规则都是事先确定的。一旦开始运行，就按照实现确定的规则工作，因此叫”自动机”。使用状态迁移描述整个工作过程
• 有限自动机示意图:

  

  工作原理:读头在输入带上从左向右移动，每当读头从带上读到一个字符时，便引起控制器状态的改变，同时读头右移一个符号的位置。

  • 控制器:
    • 控制器包括有限个状态，状态与状态之间存在着某种转换关系。每当在某一状态下读入一个字符时，便使状态发生改变（称为状态转换）。
    • 状态转换包括以下几种情况:
      • 转换到自身–保持当前状态不变
      • 转换的后继状态只有一个
      • 转换的后继状态有若干个
    • 如果一个有限自动机每次转换的后继状态都是唯一的，称为确定的有限自动机DFA

      反之，称为不确定的有限自动机NFA

    • 通常把有限自动机开始工作的状态称为“初始状态”，把结束工作的状态称为“终止状态”或“接受状态”.
  • 确定的有限自动机的形式化定义：

    

    状态转换图:

    

    

应用有限自动机解题步骤

1、确定输入集

2、绘制状态迁移图（确定状态，在每一个状态下对输入进行分类，针对每一类输入，确定下一个状态）

3、确定状态转移函数（在某状态下，接收到某一字符后，自动机要执行的操作，以及迁移到的下一状态）

例1:设计交通车量观测统计

问题描述:

• 在一个路口设置一个探测器，通过通信线路连接到后台的计算机。路口每通过一辆汽车，探测器向计算机发出一个车辆信号‘1’，探测器每隔1秒钟向计算机发出一个时钟信号‘0’，观测结束向计算机发出结束信号‘＃’。
• 要求在计算机上设计一个程序，能够接收探测器发出的信号，统计出观测的时长、在观测时长内通过的车辆总数、以及两辆车之间最大的时间间隔。

问题分析

探测器向计算机发出的信号可以认为是一个任意长的字符序列（以EOF结束），比如：“0101”，这样设计程序实际上演变为读取该字符序列，然后进行相关的操作。

观测时长：字符序列中0的个数(6秒)；
车辆总数：字符序列中1的个数(9辆)；
两车间最大时间间隔：两个1之间的最大连续0的个数(3秒)；

三步走解法-1

q0:初始状态 q1:读入字符'1'即进入q1状态，说明前一个字符是'1' q2:读入字符'0'即进入q2状态，说明前一个字符是'0' q3:终止状态 

3、确定状态转移函数

当前状态是q0 (state==q0)： 读入'1'：vehicles++; state=q1 读入'0'：seconds++; state=q2 读入EOF： state=q3 当前状态是q1 (state==q1，说明前一个字符是'1')： 读入'1'(11)：vehicles++; 读入'0'(10)：interval=1;seconds++; state=q2 读入EOF： state=q3 当前状态是q2 (state==q2，说明前一个字符是'0')： 读入'1'(01)：if(vehicles>0) 处理最大时长 vehicles++; state=q1 读入'0'(00)：seconds++; if(vehicles>0) interval++; 读入EOF： state=q30 

代码1

#include<stdio.h> #difine START 0 #define GET1 1 #define GET0 2 #define END 3 int main () { 
    char ch; int cars,seconds,interval,longest; int state; state = START; cars = 0; seconds = 0; longest = 0; printf("input signals,'#'to end: \n"); while(state != END){ 
    ch = getchar(); switch(state){ 
    case START: switch(ch){ 
    case '1': cars++; state = GET1; break; case '0': second++; state = GET0; break; case '#': state = END; break; } break; case GET1: switch(ch){ 
    case '1'://11 cars++; state = GET1; break; case '0'://10 seconds++; interval = 1; state = GET0; break; case '#': state = END; break; } break; case GET0: switch(ch){ 
    case '1'://01 cars++; if(interval >=1) { 
    longest = (longest>interval?longest:interval); interval = 0; } state = GET1; case '0'://00 seconds++; if(interval >= 1) { 
    interval++; } state = GET0; case '#': state = END; break; } break; } } printf("%d cars passed in %d seconds\n",cars,seconds); printf("the longest gap was %d seconds\n",longest); return 0; } 

三步走解法2

1、确定输入集T＝{‘1’，‘0’，‘#’}
2、对输入集中的‘1’和‘0’进行进一步分类，确定状态:
‘0’
这不是两个1之间的‘0’：进入状态 q1
这是两个1之间的‘0’ ：进入状态 q2
‘1’
这不是需要处理时间间隔的‘1’：进入状态 q3
这是需要处理时间间隔的‘1’：进入状态 q4
‘#’
进入结束状态 q5

3、绘制迁移图

说明：在q0~q4的任何一个状态下，如果接收到字符’#’,则进入终止状态q5。此处为了保持图的整洁，没有画出到q5的迁移。 q1：接收到0，且这不是两个1之间的0 q2：接收到0，且这是两个1之间的0 q3：接收到1，且这不是需要处理最长时间间隔的1 q4：接收到1，且这是需要处理时间间隔的1 

4、确定状态转义函数

当前状态q0(起始位置):

读入‘1’：//无效1 vehicles++; state=q3; 读入‘0’：//无效0 seconds++; state=q1; 读入‘#’ ： state=q5; 

当前状态q1(无效0)

读入‘1’：//无效1 vehicles++; state=q3; 读入‘0’：//无效0 seconds++; state = q1; 读入‘#’ ： state=q5; 

当前状态q2(有效0)

读入'1'://有效1(结尾1) vehicles++; longest = (longest>interval?longest:interval); interval = 0; state = q4; 读入'0'://有效0 seconds++; interval++; state = q2; 读入'#': state = q5; 

当前状态q3(无效1)

读入'1'://无效1 vehicles++; state = q3; 读入'0'://第一个有效0 seconds++; interval = 1; state = q2; 读入'#': state = q5; 

当前状态q4(有效1)

读入'1'://无效1 vehicles++; state = q3; 读入'0'://第一个有效0 seconds++; interval = 1; state = q2; 读入'#': state = q5; 

例2-检查输入字符串是否是合法的C语言注释/*...*/

三步走:

1.确定输入集

/; *; other; EOF; 

2.对输入集进一步分类，确定状态

'/': 有效'/': 头'/':q1; 尾'/':q4; 无效'/':q2; '*': 有效'*': 头'*':q2; 尾'*':q3; 无效'*':q2; other: 有效other:q2; 无效other:error; 

q1:等待注释开始的* q2:等待注释结束的* q3: 等待注释结束的/ q4：等待EOF状态 

3.绘制状态转换图

4.转换函数分析

start(等待’/’)

读入'/'://有效开头'/' state = q1; 读入'other'://读到别的东西 state = error; 

q1(开头’/‘等待’*’)

读入'*'://有效开头'*' state = q2; 读入'other'://读到别的东西 state = error; 

q2(内容物等待’*’)

读入'*'://有效结尾'*' state = q3; 读入'EOF': state = error; 读入'other': state = q2; 

q3(结尾’*‘等待’/’)

读入'/'://有效结尾'/' state = q4; 读入'*'://结尾'*' state = q3; 读入'EOF': state = error; 读入'other'://证明不是状态q3:结尾'*' state = q2; 

q4(结束等待EOF)

读入'EOF': state = accept; 读入'other': state = error; 

例3:去除C语言注释