[理工] 離散_語言與文法

看板Grad-ProbAsk作者 (fmtshk)時間6年前 (2019/10/08 00:19), 編輯推噓2(2推 0噓 16→)
留言18則, 2人參與, 6年前最新討論串1/2 (看更多)
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://www.ptt.cc/bbs/Grad-ProbAsk/M.1570465171.A.7B0.html
推
10/08 01:22, 6年前 , 1F
不是, A是一種語言，這個語言收集空字串，以及所有符合i
10/08 01:22, 1F
→
10/08 01:22, 6年前 , 2F
nductive case的字串, 意思是，如果x, y屬於A，則1x0, 0
10/08 01:22, 2F
→
10/08 01:22, 6年前 , 3F
x1, xy也都屬於A
10/08 01:22, 3F
→
10/08 01:22, 6年前 , 4F
舉例：令x = 10, 根據a小題，x屬於A，那1100也屬於A，01
10/08 01:22, 4F
→
10/08 01:22, 6年前 , 5F
01也屬於A，之類的
10/08 01:22, 5F
→
10/08 01:22, 6年前 , 6F
f_0(x) = f_1(x)只是在說A的所有字串的0跟1的bit數是一
10/08 01:22, 6F
→
10/08 01:22, 6年前 , 7F
樣的 根據inductive case不難想像 證明b也寫的很清楚了
10/08 01:22, 7F
→
10/08 01:22, 6年前 , 8F
c小題我覺得他講的有點不清楚，根據題目的要求，z應該
10/08 01:22, 8F
→
10/08 01:22, 6年前 , 9F
有個constraint就是我們已經假設z的0跟1的bits數一定一
10/08 01:22, 9F
→
10/08 01:22, 6年前 , 10F
樣了，在這個前提下才能說明一定存在非空s,t符合他證明
10/08 01:22, 10F
→
10/08 01:22, 6年前 , 11F
的情況(用反證法可以說明，這裡不贅述了)
10/08 01:22, 11F
推
10/08 07:36, 6年前 , 12F
抱歉 早上起來想想，好像不用反證，直觀說明就行了
10/08 07:36, 12F
→
10/08 07:36, 6年前 , 13F
不失一般性設頭尾為0，則中間必定有n個1，n-2個0
10/08 07:36, 13F
→
10/08 07:37, 6年前 , 14F
從左掃到右，當0個數=1個數時停下來，這段就是s，剩下
10/08 07:37, 14F
→
10/08 07:37, 6年前 , 15F
為t
10/08 07:37, 15F
→
10/08 07:37, 6年前 , 16F
因為中間1的個數多於0，所以這個情況一定會發生，而且會
10/08 07:37, 16F
→
10/08 07:37, 6年前 , 17F
在掃到倒數第二個數前發生(t至少會有2 bits)
10/08 07:37, 17F
→
10/08 12:07, 6年前 , 18F
瞭解，感謝大佬
10/08 12:07, 18F
‣ 更多 fmtshk 的文章
文章代碼(AID): #1TcsMJUm (Grad-ProbAsk)
‣ 更多 fmtshk 的文章
文章代碼(AID): #1TcsMJUm (Grad-ProbAsk)