您所在位置：网站首页 > 资格认证/考试 > 自考编译原理第2章习地训练题目课

编译原理第2章习地训练题目课

34页

卖家[上传人]：公****

文档编号：475182358

上传时间：2022-09-04

文档格式：DOC

文档大小：684KB

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

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

20 金贝

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

文本预览

下载提示

常见问题

1、1.构造正规式的 DFA 。NFA 化为 DFA :状态转换表：Q10XAABCBABCBBCDCBCDBCDCBCDCBCEEBCDBCDCBCDBCEEBCDYYBCDBCDYYBCDCBCEE1初态10ABBCDCCEDCDEYDYCE化简后得：0(2) (a|b)*(aa|bb)(a|b)*aNFA 化为 DFA :QabX 1 21 2 31 2 41 2 31 2 3 5 Y1 2 4 1 2 41 2 31 2 4 5 Y1 2 3 5 Y1 2 3 5 Y1 2 4 Y1 2 4 5 Y1 2 3 Y1 2 4 5 Y1 2 4 Y1 2 3 Y1 2 4 5 Y1 2 3 Y1 2 3 5 Y1 2 4 Y所以，DFA为:a化简得:011 .NFA 至U DFA :Q10X A YXB C DAA YBB C DAC DYA YBA YBB C DAA YBC DYC DYA YB精彩文档A1010B化简后得;2. 将下图确定化和最小化解：首先取A= &CLOSURE(0)=0, NFA确定化后的状态矩阵为QabA00,11B0,10,11C100NFA确定化后的DF

2、A为:C将A,B合并得:3. 构造一个DFA，它接受刀二0 , 1上所有满足如下条件的字符串, 每个1都有0直接跟在后边。解：按题意相应的正规表达式是0*(0 | 10)*0*构造相应的DFA，首先构造NFA为k用子集法确定化IIoIiS01X,0,1,3,Y0,1,3,Y21230,1,3,Y0,1,3,Y222321,3,Y/341,3,Y1,3,Y2443DFA为二* 1 0 24. 给出NFA等价的正规式R。消去0, 1(0|1 ) *11NFA等价的正规式为（叩）*11方法二：NFA 右线性文法正规式A0A|1A|1BB 1CA=0A+1A+1BB=1A=0A+1A+11A=(0+1) *11 (0|1) *115. 试证明正规式（a|b ） *与正规式（a*|b*） *是等价的证明:正规式 (a|b)abX, i,yi,yi,yi,yi,yi,y其最简DFA为正规式(a*|b*bNFA 为:其最简化DFA为:abx,1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y1,2,3,y由于这两个正规式的最小DFA相同，所以正规式(a|b)*等价于正规式(a*|

3、b*)*。6设字母表刀=a,b,给出刀上的正规式R=b *ab(b|ab) *。(1 )试构造状态最小化的 DFA M，使得L (M ) =L (R)(2)求右线性文法G,使L (G) =L (M )。解：(1)构造NFA:b324,5,Y41,23321,234,5,Y4655,Y66505,Y65,Y6655,Y6再将其最小化得：2XWabb(2)对应的右线性文法 G= (X,W,Y,a,b,P ,X)P: XaW|bX WbY|by aW|b Y|b3.8文法G单词为：单词-标识符|整数标识符-标识符字母|标识符数字|字母整数-数字|整数数字字母-A|B|C数字卜1|2|3(1 )改写文法G为G 使L(G )=L(G)。(2 )给出相应的有穷自动机。解：(1 )令D代表单词，I代表标识符，Z代表整数，有G( D):D I | ZIA | B | C | IA | IB | IC | I1 | I2 | I3Z1 | 2 | 3 | Z1 | Z2 | Z3(2) 左线性文法G所对应的有穷自动机为：M=(S,D,I,Z,1,2,3,A,B,C,f,S,D)f： f(S,A)=I,

5、 (S,a)=S,f(S,b)=A,f(S,b)=D,其NFA图为:a1 F精彩文档DNFA确定化后的状态矩阵为Qab1SS A,D2A,D S0NFA确定化后的DFA为:1愛23.5给出下述文法所对应的正规式:S-aAA-bA+aB+bB-aA解：将文法改为：S=aAA=bA+aB+bB=aA将代入，得A=bA+aaA+b 将用求解规则，得A= (b|aa) *b，带入得，S= a(b|aa) *b,故文法所对应的正规式为R= a(b|aa) *b。3.6给出与下图等价的正规文法G答：该有穷自动机为M=(A,B,C,D,a,b,f,A,C,D)其中 f(A,a)=B,f(A,b)=D,f(B,a)=$,f(B,b)=C,f(C,a)=A,f(C,b)=D, f(D,a)=B, f(D,b)=D根据其转换规则，与其等价的正规文法G为G= (A,B,C,D,a,b,P ,A)，其中P : A t aB|bD B bC C aA|bD| D aB|bD| 3.12.解释下列术语和概念：(1)确定有穷自动机答：一个确定有穷自动机 M是一个五元组M= (Q,，f, S, Z),其中：Q是一个有穷状态集合，每一个元素称为一个状态；工是一个有穷输入字母表，每个元素称为一个输入字符；f是一个从Q*工到Q的单值映射； f (qi,a) =q j (qi,qj Q,a 习表示当前状态为qi，输入字符为a时，自动机将转换到下一个状态qj,qj 称为qi的一个后继状态。我们说状态转换函数是单值函数，是指f(qi,a) 惟一地确定了下一个要转移的状态，即每个状态的所有输出边上标记的输入字符不同。S Q，是惟一的一个初态；Z真包含于Q , 是一 -个终态集(2)非确定有穷自动机一个非确定有穷自动机 M 是一个五元组 M= (Q,，f,

《编译原理第2章习地训练题目课》由会员公****分享，可在线阅读，更多相关《编译原理第2章习地训练题目课》请在金锄头文库上搜索。

点击阅读更多内容

TA的资源