2013年《形式语言与自动机》期末考试题目解析

本资源是一份2013年的清华大学本科生《形式语言与自动机》考试试卷，分为判断题、选择题和简答题三部分。以下是各个部分的主要知识点： 1. 判别题(16分): - 问题1测试的是正规语言的交集性质：若L1和L2的交集是正规语言，但并不保证原语言本身必须是正规语言，因此是**False**。 - 问题2考查正规语言的并集：两个正规语言的并集不一定保持正规性，可能不正规，所以是**False**。 - 问题3涉及非正规语言的否定：一个语言的非正规性并不能推断其组成部分的非正规性，所以是**False**。 - 问题4确认了判定串不可接受算法的存在性，这是正确的，**True**。 - 问题5涉及正规表达式的判定问题，确实存在算法比较两个表达式是否表示相同的语言，**True**。 - 问题6探讨了递归可枚举语言和其补集的关系，两者不可能同时是递归语言，**True**。 - 问题7指出非确定图灵机处理的问题与NP问题相关，但这部分具体细节未在题目中提供。 - 问题8涉及多带和多道图灵机的关系，多带图灵机可以被多道图灵机模拟，**True**。 2. 选择题(12分): - 第1题涉及到的是字符串模式，该语言可以通过有限自动机和某些DPDA接受，选项A正确。 - 第2题描述了一个有限条件下的字符串组合，可以由有限自动机识别，选项**E**正确。 - 第3题同样涉及字符串长度限制，适合用DPDA接受，但不是所有DPDA都能，选项C正确。 - 第4题和第6题涉及字符串反转，可以通过某些特定的PDA接受，而第4题是自反串，第6题是反向自反串，选项**B**和**D**可能是正确答案，但具体题目中没有明确指出。 - 第5题描述的可能是幂等性，选项F表明不是任何PDA的语言，符合题意。 3. 简答题(32分): - 第1小题是关于上下文无关文法G的简化，要求消去ε-产生式，得到新的产生式集合P1。根据题目给出的文法，P1将去除S→ABCε的ε产生式，具体转换结果未提供。 - 第2小题要求消除P1中的单位产生式，这通常意味着删除那些只产生单一符号的规则，但题目中没有列出P1，无法给出具体操作。 总结来说，这份试卷主要考察学生对形式语言、自动机理论（如正规语言、有限自动机、推导器、图灵机）、以及上下文无关文法的理解和应用能力，涉及理论概念的判断、选择和实际操作。