第二三章习题讲.ppt

2008-10-28;2.1 考虑下面的上下文无关文法：S → SS+ | SS* |a;2.2 下面的文法产生什么语言？;S→a|S+S|SS|S*|(S) 以a为数据元素，具有合并、连接、闭包和括号操作符的表达式。a是表达式，若S是表达式则S+S（表达式的合并）、SS（表达式的串联）、S*（表达式的闭包运算）都是表达式。 ;注意事项;2.3 练习2.2中哪些文法具有二义性？;*;*; 3.3 识别下面的各段程序中构成记号的词素，并给出每个记号的合理属性值： 程序： int max（i，j）int i，j； /*返回整数i和j的最大者*/ { return ij? i:j； }；;词素;注意事项;*;*;注意事项;3.7 试写出下列语言的正规定义：;;*;*;*;(00 | 11)? ( (01 | 10) (00 | 11) ? (01 | 10) (00 | 11) ? ) ?;写出语言“由偶数个0和奇数个1构成的所有0和1的串”的正规定义。;注意事项;3.16 用算法3.3 构造非确定有穷自动机，给出处理输入串ababbab的状态转换序列：;ababbab的状态转换序列;c) ((?|a)b*)*;ababbab的状态转换序列;3.17 用算法3.2把练习3.16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。;;3.17 用算法3.2把练习3.16中的NFA转换成DFA。给出它们处理串ababbab的状态转换序列。;;画状态图注意事项;3.22 如果两个正规表达式的最少状态DFA除状态名以外完全相同，则这两个正规表达式等价。;;注意事项;3.23 对于下列正规表达式构造最小状态的DFA.;3.23 对于下列正规表达式构造最小状态的DFA.;(b) (a|b)*a(a|b)(a|b) 解法一;b) (a | b)? a (a | b) (a | b) 解法二;c) (a | b)? a (a | b) (a | b) (a | b);;第二步;状态;第三步：;给出奇数个0奇数个1的正规表达式;给出偶数个0和偶数个1的字符串的正规表达式;消除状态1：;消除状态2：;消除状态3：