自动机应用实例.ppt

* 711 有限自动机实例 有限状态自动机 有限状态自动机是最简单的一类语言识别器，也是有限状态系统的一种模型。 有限状态自动机 确定型（DFA） 不确定型（NFA） 确定型有限状态自动机（DFA） 定义： 确定的有限自动机（DFA）是一个五元组 M=（Q, Σ, δ,q0,F） 其中 Q:有限状态集, Σ:字母表,q0∈Q是初始状态,F? Q是终止状态集, δ: Q × E?Q 称为状态转换函数。 DFA——实例 例. 某公共汽车始发站，在始发站有乘客的条件下，每隔一固定时间段发出一班车。车站发出一班车后 , 如果在下一发车时刻车站没有乘客 , 则停一班次 , 当再等到下一发车时刻时 , 不管始发站有没有乘客 , 则车站必发出一班车 。 用有限自动机刻画这一过程 ：设 x0 , x1 分别表示始发站没有乘客和有乘客 ,为自动机的输入信息 ；自动机的状态有两个 , 分别为上一发车时刻没有发车和发车两个状态 , 我们分别用 q0 , q1 表示这两个状态 ，设 q0为初始状态。 此有限自动机M=（Q, Σ, δ,q0,F）可表述: Q={ q0,q1}, Σ={x0,x1}, F? Q δ=Q × Σ →Q 其中 δ(q0,x0)=q1, δ(q0,x1)=q1, δ(q1,x0)=q0, δ(q1,x1)=q1 DFA——实例 q1 q0 q1 q1 q1 q0 x1 x0 \ 状态转换表： 状态转换图： q1 x0 x1 q1 q0 q1 q1 q1 q0 x1 x0 \ q0 q1 q0 q1 q1 q1 q0 x1 x0 \ q1 q0 q1 q1 q1 q0 x1 x0 \ q1 q0 q1 q1 q1 q0 x1 x0 \ start x0/x1 检测字符串s1、s2 对于如下有限自动机，待检测字符串s1、s2 a0 a1 a4 a3 a2 a5 a6 青 岛 春 风 期 景 区 S1= 青 岛 风 景 区 S2= 青 岛 大 学 不确定型有限状态自动机（NFA） 定义： 不确定型的有限自动机（NFA）是一个五元组 M=（Q, Σ, δ,q0,F） 其中 Q:有限状态集, Σ:字母表,q0∈Q是初始状态,F? Q是终止状态集, 状态转换函数： NFA——实例 例. 为了搞清基因表达之间的相互制约关系，科学家采用了其有正（positive）、负（negative）控制的基因网络的一个形式化模型-有限状态自动机。具体地讲，基因被激活后，将在一段时间后出现产生物蛋白质；基因被抑制后，在一段时间后停止出现蛋白质。如果把单个基因的状态看成on和off，产生物（例如蛋白质）的状态表示成absent和present，就得了一个基因的逻辑模型。进一步地，把单个基因X的状态on和off以及X的产生物状态present和absent看作自动机的输入，并分别用符号α、γ、β和λ表示，可进一步构造其对应的有限状态自动机。 NFA——实例 一个基因X 及其产生物蛋白质组成的非确定型有限状态自动机G=（Q,Σ,Δ,q,F），其中状态集Q={0,1,2,3,4 }，其中4为异常状态；输入字符集合Σ={α,γ,β,λ}；初始状态q={0}；终止状态集合F={Ф}。其所对应的不确定有限状态自动机 711 Thanks! *