资源描述
,711,有限自动机实例,有限状态自动机,有限状态自动机是最简单的一类语言识别器，也是有限状态系统的一种模型。,有限状态自动机,确定型（DFA）,不确定型（NFA）,确定型有限状态自动机（DFA）,定义：确定的有限自动机（DFA）是一个五元组M=（Q,q0,F）其中Q:有限状态集,:字母表,q0Q是初始状态,FQ是终止状态集,:QEQ称为状态转换函数。,DFA实例,例.某公共汽车始发站，在始发站有乘客的条件下，每隔一固定时间段发出一班车。车站发出一班车后,如果在下一发车时刻车站没有乘客,则停一班次,当再等到下一发车时刻时,不管始发站有没有乘客,则车站必发出一班车。,用有限自动机刻画这一过程：设x0,x1分别表示始发站没有乘客和有乘客,为自动机的输入信息；自动机的状态有两个,分别为上一发车时刻没有发车和发车两个状态,我们分别用q0,q1表示这两个状态，设q0为初始状态。,此有限自动机M=（Q,q0,F）可表述:Q=q0,q1,=x0,x1,FQ=QQ其中(q0,x0)=q1,(q0,x1)=q1,(q1,x0)=q0,(q1,x1)=q1,DFA实例,状态转换表：,状态转换图：,q1,x0,x1,q0,start,x0/x1,检测字符串s1、s2,对于如下有限自动机，待检测字符串s1、s2,a0,a1,a4,a3,a2,a5,a6,青,岛,春,风,期,景,区,S1=,青,岛,风,景,区,S2=,青,岛,大,学,不确定型有限状态自动机（NFA）,定义：不确定型的有限自动机（NFA）是一个五元组M=（Q,q0,F）其中Q:有限状态集,:字母表,q0Q是初始状态,FQ是终止状态集,状态转换函数：,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!,
展开阅读全文