北京航空航天大学2002编译原理年考研试题研究生入学考试试题考研真题
● 摘要
北京航空航天大学数理逻辑与编译原理试题
(2002年)
一、(6’x2)
在谓词逻辑中将下列命题符号化。
1. 存在最小的自然数。
2. 对于每个实数都存在比它大的有理数。
二、(6’x2)
以下公式是永真式、永假式吗？为什么？
1. (p →r ) (q →r ) →(p q →r )
2. ( xF (x ) ↔ xG (x )) → x (F (x ) ↔G (x ))
三、(10’)
用归结法证明以下推理的正确性。
张三的每个朋友都是李四的朋友。因此，每个认识李四的所有朋友的人也认识张三的所有朋友。
四、(6’)
对于任意谓词逻辑语句集Γ和任意谓词逻辑公式A ，若Γ xA ，则存在常元a 使得Γ A [x /a ]。
五、判断题(1’x5)
1. 含有优化部分的编译程序的执行效率高。
2. 用高级语言书写的源程序都必须通过翻译，产生目标代码后才能投入运行。
3. 乔姆斯基(Chomsky)把文法分为四种类型，即0型、1型、2型和3型。3型文法也称为正则文法，2型文法是短语文法。
4. 对于文法G[Z]=(Vn ，V t ，P ，Z) ，V=Vn ΥV t ，x 是文法G[Z]的句型当且仅当Z ⇒x ，且x ∈V*；x 是文法G[Z]的句子当且仅当Z ⇒x ，且x ∈V t *。
5. 对于文法G[A]:
A →aABe|Ba B→dB|ε
由于FIRST(aABe)ΙFOLLOW(A)≠∅，并且FIRST(Ba)ΙFOLLOW(A) ≠∅，所以文法G[A]不是LL(1)文法。
六、选择题(1’x5)
1. 设有文法G[S]：S →S1|S0|Sa|Sc|a|b|c，下列符号串中是该文法的句子有__________
(1)ab0 (2)a0c01 (3)aaa (4)bc10
2. 若一个文法是递归的，则它所产生语言的句子个数__________
(1)必定是无穷的 (2)是有限个的 (3)根据具体情况而定
3. 对每一个左线性文法G1，__________一个右线性文法G2，使得L(G1)=L(G2)。
(1)一定存在 (2)不存在 (3)不一定存在 (4)无法判定
4. 正则文法__________二义性的。
(1)可以是 (2)一定不是 (3)一定是