计算理论基础（第二版）清华的课后习题自我总结版..doc

If x?{a,b}*, xa=ax, for some n, show x=an, n?N. 证明： 假设xa=ax，而x含字母b。可将x写成x=anbu。则， anbua=aanbu=an+1bu，于是 bua=abu，矛盾。 得证。 Show that there are not strings x?{a,b}* which make ax=xb. 证明： 如果x?{a,b}*，且|x|=n，则ax?xb，需证明对于所有的n?N都是成立的。假设要证明对于所有的mk（k是给定的）它都成立，并且证明对于k它成立。用反证法。 假设|x|=k且ax=xb，该等式蕴涵a是x中的第一个符号，b是x中的最后一个符号，所以，可以记成x=aub。于是 aaub=aubb 即， au=ub 但|u||x|，由归纳假设au?ub。与假设矛盾。 得证。 Show is an irrational. (reduction to absurdity). 证明： 每个自然数或是偶数（对于某个n?N，等于2n）或是奇数（对于某个n?N，等于2n＋1）。因而，如果m是偶数，m＝2n，则m2=4n2=2?2n2是偶数。 而如果m=2n＋1，则m2=4n2＋4n＋1=2(2n2＋2n)＋1是奇数。 现证明对于m，n?N，方程2＝(m/n)2没有解（即，不是“有理”数）。 用反证法，假设方程2＝(m/n)2有解，则它必有m和n不都是偶数的解，因为如果m和n都是偶数，可以重复地从分子和分母中“约去”2，直到至少其中之一为奇数。另一方面，如果证明该方程的每一个解，m和n一定都是偶数，这个就矛盾表明了上面的假设是错误的，即方程2＝(m/n)2没有解。剩下的问题是证明在方程的每个解中，m和n都是偶数。将2＝(m/n)2改写为m2=2n2，表明m2是偶数，故m是偶数。如m＝2k，这样m2=4k2=2n2，或n2=2k2，于是n2偶数，从而是n偶数。 得证。 1.5.6 ①:如果有1个人没有一个熟人，熟人个数情况有0 ~ n-2 共n-1种 ①:如果每个人至少有一个熟人，熟人个数情况有1 ~ n-1 共n-1种 根据鸽巢原理，n个人中必有两个人熟人个人情况是一样的 1.7.2： a: ①: if |w|=0 then w=e , ( wR)R=( eR)R=eR=e=w ②: suppose |w|=n ( wR)R=w when |w|=n+1, suppose w=ua then |u|=n get (uR)R =u (wR)R =((ua)R)R =(aRuR)R =(uR)R (aR)R=ua=w b: suppose w=xvy then wR =(xvy)R =(vy)RxR =yRvRxR so vR is the substring of wR c: ①: if i=0, (wi )R = (wR)i =e ②: suppose I=n , (wn )R = (wR)n when I=n+1 (wi )R = (wn+1 )R = wR (wn )R = wR (wR)n =(wR)n+1=(wR)I 1.7.4: a: 任意个e的连接都是e ,根据定义得 {e}*={e} b: 显然 L* (L*)* 如果 字符串w∈ (L*)* 根据定义 w=w1 w2 w3 w4……wk wi ∈L* 同理 wi 由L*中的字符串链接而成，w也可以写成L*中的字符串链接而成 所以w∈L* ，(L*)*L* 所以L* =(L*)* c: 根据定义易的 {a}*({b}{a}*)*{a,b}* {a,b}*={a}*{b}*{a}*{b}* 而{a}*({b}{a}*)*= {a}*({b}{a}*)*({b}{a}*)*({b}{a}*)* {a}*({b}{a}*)*, {b}*({b}{a}*)* 所以 {a}*{b}*{a}*{b}*{a}*({b}{a}*)*({b}{a}*)*({b}{a}*)* 所以 {a,b}*{a}*({b}{a}*)* 所以 {a,b}*={a}*({b}{a}*)* d: 取L1=e, L2=e 则 (L1Σ* L2)*= (Σ* ) * =Σ* 所以 Σ* (L1Σ* L2)* 根据定义可得(L1Σ* L2)* Σ* 所以 (L1Σ* L2)* =Σ* e: 题目有误 1.8.1： b只出现一次，并且出现在结尾的字符串 即 (a*) b 1.8.2: (a)