有穷自动机
有穷自动机（Finite Automata ,FA） 由两位神经物理学家 MeCuloch 和 Pitts 在1948年首先提出 ，是对一类处理系统建立的数学模型
这类系统具有 一系列 离散的输入输出信息和 有穷数目的内部状态 （状态：包括了对过去输入信息处理的状况）
系统只需要根据当前所处的状态 和面临的输入信息 就可以决定系统的后继行为。每当系统处理了当前的输入后，系统的内部状态也将发生改变
FA的典型例子
image.png
FA 模型
image.png
输入带 ：用来存放输入符号串
读头 ：从左向右逐个读取输入符号 ，不能修改（不能往返移动）
有穷控制器 : 具有有穷个状态数，根据当前的状态 和当前输入符号 控制转入 下一个状态
FA的表示
转换图
image.png
FA定义(接收)的语言
给定输入串X 如果存在一个对应于串x的从初始状态到某个终止状态的转换序列 则称串 x 被该FA 接收
由一个有穷自动机M 接收的所有串构成的集合称为是该 FA 定义（或接收）的语言,记为 L(M)
image.png
最长子串匹配原则 （Longest String Matching Principle）
当输入串的多个前缀 与 一个 或者多个模式匹配时，总是选择最长的前缀进行匹配
image.png
网友评论