赞
踩
必考题4-文法分析题
文法定义:0型(无限制文法)、1型(上下文有关文法)、2型(上下文无关文法)、3型(正规文法)(分值1分)
例1:下图所示为一个有限自动机(其中S0是初态,S2是终态),该自动机可识别
A. 1001
B. 1100
C. 1010
D. 0101
答案是:B
解题技巧:
这种题型一般是将选项代入到图中进行验证,前提记得必须是从初态到终态的过程。
分析上图得从S0入度为0,到S1必须经过1,S1到S2必须为1,然后终态入度为0/1。文法可写为:(1|01)*1(0|1)*,所以根据排除法,选择B
例2:下图所示为一个有限自动机(其中,A是初态、C是终态),该自动机所识别的字符串的特点是()。
A. 必须以11结尾的0、1串
B. 必须以00结尾的0、1串
C. 必须以01结尾的0、1串
D. 必须以10结尾的0、1串
答案是:C
解题:
分析上图,A为初态,C为终态,则从初态到终态必须经过B;A的入度为1,B的入度为0,C的入度为1。所以文法表示为1*0(0|10)*1,所以答案是C。
这里讲讲这个文法是如何推倒的,首先对初态进行分析A的出度为1到自身,组成循环对应为1*,而A下一个节点单项只能到B,对应为0;对于B来说出度为0到自身组成循环,且出度为1到C,C又入度到B组成循环,所以对于B来说出度为0|10的循环,对应为0|10;而B要达到终态C必须再有出度1,对应为1。组合起来就是1*0(0|10)*1,因为C又到A,使得整体又进入循环,所以最终文法表示为(1*0(0|10)*1)*,仅是个人理解,其实文法表示应该有多种形式,可以达到相同的目的,还是需要理解原理。
注:对于确定的有限自动化和非确定的有限自动机的区别是。
确定的有限自动机:对每一个可能的输入都只有一个状态的转移
非确定有限自动机:对每一个可能的输入可以有多个状态的转移,接受到输入时,从这多个转移转移中非确定选择一个。
例2:算数表达式 a*(b+c/d)-e的后缀式是()
答案:abcd/+*e-
解题技巧:
首先对于中缀式来说,符号(/*+-)的左右应为其左右子树,对于后缀式第一个字母为左子树,每多一个符号(/*+-),其字母中顺序选择一个字母作为此符号树的右子树。
我们来实际演示一下,比如将中缀式a*(b+c/d)-e画成树结构为:
*符号为父节点,a作为左子树,(b+c/d)作为右子树;
(b+c/d) 中 + 作为父节点,b为左子树,c/d 作为右子树;c/d 中 /作为父节点,c作为左子树,d作为右子树;
对于 - 作为父节点,a*(b+c/d)作为左子树,e作为右子树。
。
那如果给出后缀式,怎么推倒中缀式呢,我们还是以上述例题举例
将后缀式abcd/+*e-画成树结构为:
首先注意一点后缀式最后一位肯定为根节点。
那 - 作为父节点,e就是右子树,abcd/+*就是左子树;
然后对于abcd/+*,*作为父节点,前面有多个符号位,因为构成左右子树,所以左子树为a,右子树为bcd/+;
然后对于bcd/+,+作为父节点,b作为左子树,cd/作为右子树;
对于cd/,/作为父节点,c作为左子树,d作为右子树。
同样画成树如下图所示:
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。