计算理论课后习题整理

1.1描述DNF的状态图

下面的没有规定有多少个状态 

这个介绍看另一个文章 

证明：下面的DFA识别Cn：(正向读)

M=( Q, {0,1} , d , q0 , F ), 其中Q＝{0,1,2,…，n-1},

d( i,1)=2i+1 mod n, d( i,0 )=( 2i mod n), i=0,1,2,…，n-1,

起始状态为0, F＝{0}.

这里i表示当前数mod n余i.

下面的DFA识别CnR：(反向读)

M=( Q, {0,1} , d , q0 , F ), 其中Q＝{(i,j)|i,j=0,1,2,…，n-1},

d((i,j),1)=( 2i mod n, (2i+j)mod n ), d((i,j),0)=( 2i mod n, j ), i,j=0,1,2,…，n-1

起始状态为(1,0), F＝{ (i,0) | i=0,1,…，n-1}.

这里(i,j)表示当前数mod n余j, 而下一位所表示单位数mod n余i(例如，若读下一位将达到k位，则下一位所表示单位数为10k-1).

说明语言是上下文无关文法如果可以构造出CFG那么就可以证明它是上下文无关文法。

可以看理论知识里的通过泵引理证明A交B不是无关的 

利用上下文无关语言在并运算下封闭和上下文无关语言在交运算下不封闭且上下文无关语言的补集也是CFL制造出矛盾。

（也可以像上面一个题一样证明ww形式  由于非ww形式可以CFL但是ww形式是非CFL 可以用泵引理证明在补运算不封闭 ）

2.7（课后题）

用CFG简单点

2.10的非形式描述 

2.23 （作业题）

比如q1 0000 也就是q1指的右边的0

周围为  空格0000空格

1、 上面为q1指向的0，无论向左还是向右移动，指针都是指的右边的，移动的是q，并且相应的更新状态。

2、当指向没有输入时，要补上空格，比如000q0，向右移动后变为0000q空格

3、当指向没有相应的路径后，直接拒绝

 图灵机的一个要求是一步只能做有限的工作

 因为图灵机的一个要求是一步只能做有限的工作。  

只需设计出图灵机来识别此种语言

下面具体的看课后题，背过 

2、a.判断DFA和正则表达式是否等价

          将正则表达式B转化为等价的DFA C，检测A与C是否等价，如果等价则接受，否则拒绝

     b.设ALLDFA={ | A是一个识别S*的DFA}。证明ALLDFA可判定 

          构造DFA B，使得L(B)= S*，检测检测是否等价，如果等价则接受，否则拒绝

   上下文无关文法派生问题（右侧是标准答题模板）

设ALLDFA={ | A是一个识别S*的DFA}。

方法一：设计一个使用标记算法的TM M,（标记）

M=“对于输入,其中A是一个DFA:

方法二：构造DFA B，使得L(B)= S*。（利用EQDFA可判定）

M＝“对于输入,其中A是一个DFA:

图灵可识别只是要能找到一个就接收，至于停机不停机不用管，下面证明它的补是图灵可识别的

 设B是{0,1}上所有无限序列的集合，用对角化方法证明B是不可数的（不懂！！）

上面第四步如果是回路的话将不会被标记

下面两个属于判断A接受问题，主要是看DFA是否接受指定的串，下面主要是构造DFA N，然后L(N)是特定的串，这个串一般是给定串的反例，然后根据这个求其交集，看是否为空

4.13判断正则表达式

正则表达式同理

 上面那个没理解

背过下面过程

利用已知进行规约 

5.6 证明是传递关系 

5.28

5.34  

 可满足性：对变量的某个 0,1 赋值使得一个公式的值等于1