离散数学(形式语言与自动机).ppt

1、1，11.2有限自动机，确定性有限自动机(DFA)，具有转移NFA(-NFA)的非确定性有限自动机(NFA)，2确定性有限自动机，3，DFA所接受的语言，它被扩展到Q* *:Q*Q，被递归地定义为qQ，a和w* *(.如果*(q0，w) f，那么所有被w. M接受的字符串都被称为被M接受的语言，被表示为L(M)，也就是说，L (m)=w * | * (Q0，w)F，4，被DFA接受的语言(续)，例如1: M=Q0，Q1，a，不确定有限自动机被定义为NFA (m=q，q0，F)，其中Q，Q0，F与DFA相同，而： Q P(Q)，6，例，例2，NFA，7，NFA接受的语言，* :q *。)=q *

2、(q，wa)=定义w*，如果*(q0，w)F，则M接受的整个字符串被w. M称为M接受的语言，表示为L(M)，即L(M)=w*| *(q0，w)F，8，示例2(续)q0，F模拟m=q，q0，f q=p (q)，Q0=Q0 f=AQ | afaq和一个定理，对于每个NFA M，DFA M生成L(M)=模拟示例不可达状态：从初始状态中删除所有永远无法达到的不可达状态，并且不改变FA接受的语言。 例如，q1，q2，q0，q2，q1，q2和所有处于M的都是不可达状态，删除这些状态给出M，12，一个带有转移的不确定有限自动机，并且转移3360不读取符号如何。自动状态转换。-NFA:Q()P(Q)定理对于

3、每一个-NFA M都有DFA M，所以L(M)=L(M) DFA，NFA和-NFA接受相同的语言类，13，用DFA模拟-NFA，让-NFA m=q，(2)如果pE(q)，那么(P)，E(q)。例3 -NFA M，14，用DFA模拟-NFA(续)，模拟方法基本上与用DFA模拟没有它的NFA相同，只是用E(q)代替Q，DFA M=Q，Q0。Q0=E(q0) F=AQ | AF AQ和A，当构造DFA M时，不需要计算不可达状态。方法如下：从q0=E(q0)开始，计算每个A的值，然后重复每个新子集的值，直到没有新子集出现。15，模拟示例3。L (m)=l (m)=(01) n | n0，-NFA m

4、，DFA m，16，11.3有限自动机与正则文法的等价性，用-NFA模拟右线性文法，用右线性文法模拟DFA，17，有限自动机与正则文法的等价性，定理G为右线性文法。假设M是密度泛函分析，那么有一个右线性文法G，它使L(G)=L(M)。定理下列命题是等价的： (1) L是正则语言；(2)语言L可以由右线性语法生成；(3)左线性语法可以生成左语言；(4)第一语言可以被外交部接受；(5)NFA可以接受L语言；(6)NFA可以接受第一语言。18。使用-NFA来模拟右线性语法。让右线性文法G=V，T，S，P-NFA M=Q，Q0，F构造如下：Q=VQF，Q0=S，F=QF，=T *-。如果是接入点，(a)，包含qf；(qf)，=，19，模拟示例，l(G)=(l(M)=(11)m0n | m1，n0，g=v，T，S，p v=a，s t=0，1p3360s11s1a0aa，-NFA m=Q .让DFA M=Q，q0，F右线性语法G=V，T，S，P构造如下： V=Q，t=，S=q0 qQ，如果(Q，a)=p，则s=q0p : q00 q1q 01 q0q 1