编译原理听课笔记_1.pdf

《编译原理听课笔记_1.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、编译原理听课笔记_1帐户维唯为为_126博客正规方法、正规集、正规式定理1：1.α+β=β+α2.α+(β+γ)=α+β+γα(βγ)=(αβ)γ3.α(β+γ)=(αβ)+(αγ)(α+β)γ=(αγ)+(βγ)4.εα=αε+α***5.(α)=α*+6.α=α+εα+=αα*=α*α*******7.(α+β)=(α+β)=(αβ)定理2：若αβγ是字母表A上的正规式，且ε∈L(γ)，则α=β

2、αγ，当且仅当α=βγ*α=β

3、γα，当且仅当α=γ*β例：已知正规方法G1的产生式，求出它所定义的正规式。产生式为：S—>aS

4、

5、aBB—>bB

6、bAA—>cA

7、c解：由产生式写出对应的联立方程组：S=aS

8、aB(1)B=bB

9、bA(2)A=cA

10、c(3)(3)+由(1)式，S(α)=aS(γα)

11、aB(β)得：S=a*aB(α=γ*β)=aB+同理(2)B=bB

12、bA=>B=bA(=b*bA)+同理(3)A=cA

13、c=>A=c*c=c+++所以，S=abc有限自动机(FAfiniteautomata)1.确定有限自动机DFA(DeterminisicFA)①它是一个五元式，M(S,Σ,f,S0,Z)其中S：有限状态集Σ：有限字母表f：S×Σ—>S上的单值

14、映射，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

15、)。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.正规式与有限自动机之间的关系