Re: [閒聊] Pumping lemma
※ 引述《ILoveElsa (酷拉皮卡買醬油)》之銘言：
: explain like i'm five
pumping lemma的確是剛開始範圍裡比較難的東西
主要是他是說RL必滿足這個lemma，
但在證明非RL使用上，是企圖找到非regular language不滿足這個lemma
很多人上大學還不太會用反證法，這可能跟工程科系學生的微積分不太重視證明有關
回到正題
pumping lemma主要是說一個RL A裡面any一個長度至少為p的string s "may" 被拆成三部分, s=xyz,
且滿足所有以下三個條件:
1. for each 非負整數i， x(y^i)z仍在A裡面
2. y的長度>0
3. xy的長度不超過p
反證法是使用其逆否命題:若language A裡面能找到"至少一個"長度至少為p的s使
所有被拆成s=xyz的組合"都"違反以上三條件中"至少一個"條件，
則A不是RL
麻煩的是要分類列舉出s中的所有xyz組合"都"無法同時滿足三個條件
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.72.74.238
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1490557315.A.4D8.html
→
03/27 03:45, , 1F
03/27 03:45, 1F
推
03/27 03:46, , 2F
03/27 03:46, 2F
推
03/27 03:47, , 3F
03/27 03:47, 3F
推
03/27 03:47, , 4F
03/27 03:47, 4F
→
03/27 03:48, , 5F
03/27 03:48, 5F
那需要一點intuition,主要是想辦法針對y設計，話說pumping lemma在context free language那一章又會重返榮耀，讀到後面來看會覺得很簡單，我覺得真正難開始是recursive theorem之後的內容
※ 編輯: ExHentai (114.137.248.213), 03/27/2017 04:09:19
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：