作者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/m.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