作者fmtshk (fmtshk)
看板Grad-ProbAsk
标题[理工] 离散_语言与文法
时间Tue Oct 8 00:19:29 2019
https://i.imgur.com/kmmkvF1.jpg
关於这题目的Inductive case意思
是说x,y∈A 那麽可能会是0x1,1x0或xy?
不是很懂为什麽f0(z)=f1(z)
看了(b)的证明好像有点半懂,所以代表x,y一定是相同数量的0和1组成的？
另外(c)解答最後3行,为何必存在s,t使z=st?
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 39.12.101.82 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1570465171.A.7B0.html
1F：推 mi981027: 不是, A是一种语言，这个语言收集空字串，以及所有符合i 10/08 01:22
2F：→ mi981027: nductive case的字串, 意思是，如果x, y属於A，则1x0, 0 10/08 01:22
3F：→ mi981027: x1, xy也都属於A 10/08 01:22
4F：→ mi981027: 举例：令x = 10, 根据a小题，x属於A，那1100也属於A，01 10/08 01:22
5F：→ mi981027: 01也属於A，之类的 10/08 01:22
6F：→ mi981027: f_0(x) = f_1(x)只是在说A的所有字串的0跟1的bit数是一 10/08 01:22
7F：→ mi981027: 样的 根据inductive case不难想像 证明b也写的很清楚了 10/08 01:22
8F：→ mi981027: c小题我觉得他讲的有点不清楚，根据题目的要求，z应该 10/08 01:22
9F：→ mi981027: 有个constraint就是我们已经假设z的0跟1的bits数一定一 10/08 01:22
10F：→ mi981027: 样了，在这个前提下才能说明一定存在非空s,t符合他证明 10/08 01:22
11F：→ mi981027: 的情况(用反证法可以说明，这里不赘述了) 10/08 01:22
12F：推 mi981027: 抱歉 早上起来想想，好像不用反证，直观说明就行了 10/08 07:36
13F：→ mi981027: 不失一般性设头尾为0，则中间必定有n个1，n-2个0 10/08 07:36
14F：→ mi981027: 从左扫到右，当0个数=1个数时停下来，这段就是s，剩下 10/08 07:37
15F：→ mi981027: 为t 10/08 07:37
16F：→ mi981027: 因为中间1的个数多於0，所以这个情况一定会发生，而且会 10/08 07:37
17F：→ mi981027: 在扫到倒数第二个数前发生(t至少会有2 bits) 10/08 07:37
18F：→ fmtshk: 了解，感谢大佬 10/08 12:07