跳到主要内容

2025-2026学年下学期期末

2025-2026学年下学期期末试卷​

一、问答题​

  1. 确定性图灵机与非确定性图灵机有什么区别，它们为什么等价？
  2. 给出至少3种方法判断一个语言是否是上下文无关语言。
  3. 二义性的概念。固有二义性的概念。
  4. 简述图灵机的整型运算过程。

二、设计题​

  1. 一个语言的字母表中只有 a 和 b，且这个语言中所有字符串都含有恰好一个 aa 子串。
    1. 设计一个正则表达式来生成这个语言。
    2. 将正则表达式转化为 ϵ\epsilon-NFA。
  2. 构造出识别 L={aibjck∣i,j,k≥0,i=j or j=k}L = \{a^ib^jc^k|i,j,k\geq 0, i = j\,\mathrm{or}\, j = k\} 的 PDA。
  3. 将下推自动机 P({p,q},{0,1},{X,Z},δ,p,Z)P(\{p,q\},\{0,1\},\{X,Z\},\delta,p,Z)转化为能被它识别的语言的一个上下文无关文法，并将它转化为 CNF 范式。其中 δ\delta 为。 （不能保证这个表格是无误的，总之考的就是这个样子）
    0,Z0,X1,Z1,Xϵ\epsilon,Zϵ\epsilon,X
    →\rightarrow pq,Xp,XZp,XXp,ϵ\epsilon
    qp,Zq,ϵ\epsilon

###　三、证明题

  1. 用泵引理证明 L={0i1j2k∣i<j<k}L = \{0^i1^j2^k|i<j<k\} 不是上下文无关语言。
  2. 给定文法 S→S+S∣SS∣S∗∣(S)∣0∣1S \rightarrow S+S|SS|S*|(S)|0|1
    1. 这个文法的语义是什么。
    2. 证明这个文法存在二义性。
    3. 给出一个等价的无二义性文法。