计算理论模拟试题(4)

计算理论模拟试题

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,

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库计算理论模拟试题(4)在线全文阅读。