编译原理听课笔记_1帐户维唯为为博客_126正规方法、正规集、正规式定理1：1.α+β=β+α2.α+(β+γ)=α+β+γα(βγ)=(αβ)γ3.α(β+γ)=(αβ)+(αγ)(α+β)γ=(αγ)+(βγ)4.εα=αε+α5.(α*)*=α*6.α*=α++εα+=αα*=α*α7.(α+β)*=(α*+β*)*=(α*β*)*定理2：若αβγ是字母表A上的正规式，且ε∈L(γ)，则α=β|αγ，当且仅当α=βγ*α=β|γα，当且仅当α=γ*β例：已知正规方法G1的产生式，求出它所定义的正规式。产生式为：S—>aS|aBB—>bB|bAA—>cA|c解：由产生式写出对应的联立方程组：S=aS|aB(1)B=bB|bA(2)A=cA|c(3)(3)+由(1)式，S(α)=aS(γα)|aB(β)得：S=a*aB(α=γ*β)=aB+同理(2)B=bB|bA=>B=bA(=b*bA)+同理(3)A=cA|c=>A=c*c=c+++所以，S=abc有限自动机(FAfiniteautomata)1.确定有限自动机DFA(DeterminisicFA)①它是一个五元式，M(S,Σ,f,S0,Z)其中S：有限状态集Σ：有限字母表f：S×Σ—>S上的单值映射，f(S,a)=S’S0：唯一的初态，S0∈SZ：终止状态，Z⊆S②状态转换关系表示：1.状态转换图矩阵：DFA的映射关系由一个矩阵来表示。2.状态转换图：③一步动作每读入一个字符，状态就向前进至下一状态；记为：“⊦”⊦k表示自动机做了k步动作。⊦*表示自动机做了0步动作或0步以上动作。⊦+表示自动机做了1步动作或1步以上动作。④DFA对字符串的识别**定义：串α∈Σ为DFAM=(S,Σ,f,S0,Z)所识别，当且仅当(S,α)⊦(S0,ε),且s∈z能够被DFAM所接受的字符串的集合，称为自动机M所能识别的语言，记为L(M)。2.不确定的有限自动机NFA(Non-deterministicFA)①定义：不确定有限自动机是一个五元式,M(S,Σ,f,S0,Z)其中S：有限状态集Σ：有限字母表Sf：S×Σ—>2(S的子集)上的单值映射，f(S,a)=S’S0：非空的初态集，S0⫋S(S0是S的真子集)Z：终止状态，Z⊆S，可为空集②两自动机等价：对于每个NFAM，存在一个DFAM’，使得L(M)=L(M’)，即，设L是一NFA接受的正规集，则存在一个DFA接受L。③NFA确定化3.正规式与有限自动机之间的关系