形式语言和自动机初步.ppt

《形式语言和自动机初步.ppt》由会员上传分享，免费在线阅读，更多相关内容在PPT专区-天天文库。

1、形式语言和自动机初步1第11章形式语言和自动机初步11.1形式语言和形式文法11.2有穷自动机11.3有穷自动机和正则文法的等价性11.4图灵机2字符串和形式语言形式文法形式文法的分类0型文法1型文法或上下文有关文法2型文法或上下文无关文法3型文法或正则文法11.1形式语言与形式文法3语言的基本要素汉语字符:汉字和标点符号字符集:合法字符的全体句子:一串汉字和标点符号语法:形成句子的规则形式语言字符字母表字符串形式文法4字符串字母表Σ:非空的有穷集合字符串:Σ中符号的有穷序列如Σ={a,b}a,b,aab,babb字符串ω的长度

2、ω

3、:ω中的字符个数如

4、a

5、=1,

6、aab

7、=3空

8、字符串ε:长度为0,即不含任何符号的字符串an:n个a组成的字符串Σ*:Σ上字符串的全体5子字符串(子串):字符串中若干连续符号组成的字符串前缀:最左端的子串后缀:最右端的子串例如ω=abbaaba,ab,abb是ω的前缀aab,ab,b是ω的后缀ba是ω的子串,但既不是前缀,也不是后缀ω本身也是ω的子串,且既是前缀,也是后缀ε也是ω的子串,且既是前缀,也是后缀6字符串的连接运算设α=a1a2…an,β=b1b2…bm,αβ=a1a2…anb1b2…bm称作α与β作的连接如α=ab,β=baa,αβ=abbaa,βα=baaab对任意的字符串α,β,γ(1)(αβ)γ=α(βγ)即

9、,连接运算满足结合律(2)εα=αε=α即,空串ε是连接运算的单位元n个α的连接记作αn如(ab)3=ababab,α0=ε7形式语言定义:Σ*的子集称作字母表Σ上的形式语言,简称语言例如Σ={a,b}A={a,b,aa,bb}B={an

10、n∈N}C={anbm

11、n,m≥1}D={ε}空语言Ø8形式文法一个例子——标识符<标识符>:<字母>

12、<下划线>

13、<标识符><字母>

14、<标识符><下划线>

15、<标识符><数字><字母>:a

16、b

17、…

18、z

19、A

20、B

21、…

22、Z<下划线>:_<数字>:0

23、1

24、…

25、99形式文法的定义定义形式文法是一个有序4元组G=,其中(1)V是非空有穷集合

26、,V的元素称作变元或非终极符(2)T是非空有穷集合且V∩T=Ø,T的元素称作终极符(3)S∈V称作起始符(4)P是非空有穷集合,P的元素称作产生式或改写规则,形如α→β,其中α,β∈(V∪T)*且α≠ε.10文法生成的语言设文法G=,ω,λ∈(V∪T)*,ωλ:存在α→β∈P和ξ,η∈(V∪T)*,使得ω=ξαη,λ=ξβη称ω直接派生出λ.ωλ:存在ω1,ω2,…,ωm,使得ω=ω1ω2…ωm=λ称ω派生出λ.恒有ωω(当m=1时)是的自反传递闭包11文法生成的语言定义设文法G=,G生成的语言L(G)={ω∈T*∣Sω}L(G)由所有

27、满足下述条件的字符串组成:(1)仅含终结符;(2)可由起始符派生出来.定义如果L(G1)=L(G2),则称文法G1与G2等价.12举例例1文法G1=,其中V={S},T={a,b},P:S→aSb

28、abL(G1)={anbn

29、n>0}例2文法G2=,其中V={A,B,S},T={0,1},P:S→1A,A→0A

30、1A

31、0B,B→0L(G2)={1x00

32、x{0,1}*}例3文法G3=,其中V={A,B,S},T={0,1},P:S→B0,B→A0,A→A1

33、A0,A→1L(G3)=L(G2),G3与G2等价13例4G=

34、,S,P>,其中V={S,A,B,C,D,E},T={a},P:(1)S→ACaB(2)Ca→aaC(3)CB→DB(4)CB→E(5)aD→Da(6)AD→AC(7)aE→Ea(8)AE→ε试证明:i1,S证:a2和a4的派生过程SACaB(1)AaaCB(2)AaaE(4)AEaa2次(7)a2(8)举例(续)14例4(续)SAaaCBAaaDB(3)ADaaB2次(5)ACaaB(6)AaaaaCB2次(2)AaaaaE(4)AEaaaa4次(7)a4(8)15例4(续)先用归纳法证明i1,当i=1时结论成立,假设对i结论成立,(3)2i次(5)(6)

35、2i次(2)得证对i+1结论成立,故对所有的i成立.16例4(续)于是,i1,(4)2i次(7)(8)可以证明:L(G)={

36、i1}17形式文法的分类—Chomsky谱系0型文法(短语结构文法,无限制文法)1型文法(上下文有关文法):所有产生式α→β,满足

37、α

38、

39、β

40、另一个等价的定义:所有的产生式形如ξAη→ξαη其中AV,ξ,η,α(V∪T)*,且αε2型文法(上下文无关文法):所有的产生式形如A→α其中AV,α(V∪T)*,18形式文法的分类(续