您所在位置：网站首页 > 办公文档 > 工作范文07879离散数学-屈婉玲(形式语言与自动机)111

07879离散数学-屈婉玲(形式语言与自动机)111

23页

卖家[上传人]：繁星

文档编号：88150627

上传时间：2019-04-20

文档格式：PPT

文档大小：282.50KB

文档加载中……请稍候！
如果长时间未打开，您也可以点击刷新试试。

下载文档到电脑，查找使用更方便

15 金贝

/ 23 举报版权申诉马上下载

文本预览

下载提示

常见问题

1、1,形式语言和自动机初步,2,第11章形式语言和自动机初步,11.1 形式语言和形式文法 11.2 有穷自动机 11.3 有穷自动机和正则文法的等价性 11.4 图灵机,3,字符串和形式语言形式文法形式文法的分类 0型文法 1型文法或上下文有关文法 2型文法或上下文无关文法 3型文法或正则文法,11.1 形式语言与形式文法,4,语言的基本要素,汉语字符:汉字和标点符号字符集:合法字符的全体句子:一串汉字和标点符号语法:形成句子的规则,形式语言字符字母表字符串形式文法,5,字符串,字母表: 非空的有穷集合字符串: 中符号的有穷序列如 =a,b a, b, aab, babb 字符串的长度|: 中的字符个数如 |a|=1, |aab|=3 空字符串: 长度为0, 即不含任何符号的字符串 an : n个a组成的字符串 *: 上字符串的全体,6,子字符串(子串): 字符串中若干连续符号组成的字符串前缀: 最左端的子串后缀: 最右端的子串例如 =abbaab a,ab,abb是的前缀 aab,ab,b是的后缀 ba是的子串, 但既不是前缀, 也不是后缀

2、本身也是的子串, 且既是前缀, 也是后缀也是的子串, 且既是前缀, 也是后缀,7,字符串的连接运算,设=a1a2 an, = b1b2 bm, =a1a2 anb1b2 bm称作与作的连接如 =ab, =baa, =abbaa, =baaab 对任意的字符串, , (1) ()=() 即, 连接运算满足结合律 (2) = 即, 空串是连接运算的单位元 n个的连接记作n 如 (ab)3= ababab, 0=,8,形式语言,定义: *的子集称作字母表上的形式语言, 简称语言例如 =a,b A=a,b,aa,bb B=an | nN C=anbm | n,m1 D= 空语言,9,形式文法,一个例子标识符 : | | | | : a | b | | z | A | B | | Z : _ : 0 | 1 | | 9,10,形式文法的定义,定义形式文法是一个有序4元组G=, 其中 (1) V是非空有穷集合, V 的元素称作变元或非终极符 (2) T是非空有穷集合且VT =, T 的元素称作终极符 (3) SV 称作起始符 (4) P是非空有穷集合, P的元素称作产生式或改写规则, 形

3、如, 其中,(VT)*且.,11,文法生成的语言,设文法 G = , , (VT)*, : 存在P和,(VT)*, 使得 = , = 称直接派生出. : 存在1, 2, , m, 使得 = 1 2 m= 称派生出. 恒有 (当m=1时) 是的自反传递闭包,12,文法生成的语言,定义设文法G= , G生成的语言 L(G)=T* S L(G)由所有满足下述条件的字符串组成: (1) 仅含终结符; (2) 可由起始符派生出来. 定义如果L(G1)= L(G2), 则称文法G1与G2等价.,13,举例,例1 文法G1= ,其中V=S, T=a,b, P: SaSb | ab L(G1)=anbn | n0 例2 文法G2= ,其中V=A,B,S, T=0,1, P: S1A, A0A | 1A | 0B, B0 L(G2)=1x00 | x0, 1* 例3 文法G3= ,其中V=A,B,S, T=0,1, P: SB0, BA0, AA1 | A0, A1 L(G3)= L(G2), G3与G2等价,14,例4 G= ,其中V=S,A,B,C,D,E, T=a, P: (1) SACaB

4、 (2) CaaaC (3) CBDB (4) CBE (5) aDDa (6) ADAC (7) aEEa (8) AE 试证明: i 1, S 证: a2 和 a4 的派生过程 S ACaB (1) AaaCB (2) AaaE (4) AEaa 2次 (7) a2 (8),举例 (续),15,例4 (续),S AaaCB AaaDB (3) ADaaB 2次(5) ACaaB (6) AaaaaCB 2次(2) AaaaaE (4) AEaaaa 4次(7) a4 (8),16,例4(续),先用归纳法证明 i 1, 当 i=1 时结论成立, 假设对i 结论成立, (3) 2i 次(5) (6) 2i 次(2) 得证对 i +1 结论成立, 故对所有的 i 成立.,17,例4 (续),于是, i 1, (4) 2i 次(7) (8) 可以证明: L(G) = | i 1,18,形式文法的分类 Chomsky谱系,0型文法(短语结构文法,无限制文法) 1型文法(上下文有关文法): 所有产生式, 满足 | 另一个等价的定义: 所有的产生式形如 A 其中AV, ,(VT)*,且 2型文法

5、(上下文无关文法): 所有的产生式形如 A 其中AV,(VT)*,19,形式文法的分类 (续),3型文法(正则文法): 右线性文法和左线性文法的统称右线性文法: 所有的产生式形如 AB 或 A 左线性文法: 所有的产生式形如 AB 或 A 其中A,BV,T* 例1是上下文无关文法例2是右线性文法,例3是左线性文法,都是正则文法例4是0型文法,20,Chomsky谱系,0型语言: 0 型文法生成的语言 1型语言(上下文有关语言): 如果L-可由1型文法生成, 则称 L 是1型语言 2型语言(上下文无关语言) : 2 型文法生成的语言 3型语言(正则语言): 3 型文法生成的语言如 1x00 | x0, 1* 是正则语言 (例1) anbn | n0 是上下文无关语言 (例2,3) | i 1 是 0 型语言 (例4) 定理 0型语言1型语言2型语言3型语言,21,描述算术表达式的文法,G=E,T,F,a,+.-.*,/,(,),E,P 其中E:算术表达式, T:项, F:因子, a:数或变量 P: E E+T | E-T | T T T*F | T/F | F F (E) | a 这是上下文无关文法,22,左、右线性文法的等价性,定理设G是右(左)线性文法,则存在左(右)线性文法G 使得L(G )=L(G). 证明: G用模拟G,G= G= P: AB P: BA A SA S,23,一个实例模拟例2中的G2,可删去G2中的S, 这实际上就是G3,G2= G2 = V=A,B,S V =A,B,S,S T=0,1 T =0,1 P: S1A P: AS1 A0A AA0 A1A AA1 A0B BA0 B0 SB0 S,

《07879离散数学-屈婉玲(形式语言与自动机)111》由会员繁星分享，可在线阅读，更多相关《07879离散数学-屈婉玲(形式语言与自动机)111》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源