计算理论模拟试题
7、设语言A={w | w至少含有3个1}，字母表为{0，1}
a. 给出产生语言A的上下文无关文法。
b. 给出产生语言A的下推自动机的非形式描述和状态图。
解: a. S→A1A1A1A
A→0A|1A|
读输入中的符号。每读一个1，把一个1推入栈，每读1个0，不读栈也不写栈。同时非确定性地转移，并把1个1弹出栈。如果能转移三次，共弹出三个1，则接受这个输入，并继续读输入符号直至结束。否则拒绝这个输入。
8、检查图灵机的形式定义，回答下列问题并解释你的推理：
a. 图灵机能在它的带子上写下空白字符吗？
b. 图灵机能只包含一个状态吗？
解：a. ；
B. 不能。因为qaccept qreject，至少应有两个状态。
9、证明正则语言类在并运算下封闭。
10、设INFINITEDFA={<A>|A是一个DFA，且L(A)是一个无限语言}。证明INFINITEDFA是可判定的。
证明：设计一个判定INFINITEDFA的TM M即可。
M=“对于输入<A>，其中A是一个DFA：
1) 按照引理2.32 证明中的构造方法，把DFA A转换成等价的正则表达式。
2) 扫描正则表达式，如果包含星号运算符*，则接受；否则拒绝。”。
11、设B是{0，1}上所有无限序列的集合，用对角化方法证明B是不可数的。
证明：为证明B是不可数的，必须证明在B和N之间不存在对应。下面用反证法证之。假设在B和N之间存在对应f，现在的任务是证明它没有应有的性质。因为它是一个对应，必须能将N的所有元素与B的所有元素进行配对。如果能找到B中的一个x，它和N中的任何元素都不能配对，则找到了矛盾。
0, 0,