[問題] RE無法表達的字串!?

看板RegExp作者 (分享)時間15年前 (2009/01/17 09:53), 編輯推噓6(6推 0噓 10→)
留言16則, 6人參與, 最新討論串1/3 (看更多)
前幾天看到一個介紹Regular Expression的網站 內容有提到一個範例 說像是 ab aabb aaabbb aaaabbbb ..... (有多少個a後面就要有多少個b) 這種字串是RE所無法表達的... 說數學上已經證明為不可行? 我也想不出來要怎麼用RE來表達.. 有辦法寫出這種字串的re嗎? thanks!! -- ※ 發信站: 批踢踢實業坊(ptt.cc) ◆ From: 61.228.96.174
→
01/17 18:38, , 1F
請問原PO有數學上的證明嗎?
01/17 18:38, 1F
推
01/17 19:38, , 2F
用 pumping lemma 證 http://tinyurl.com/2ly3gx 範例就是
01/17 19:38, 2F
→
01/17 19:39, , 3F
但現在常用的 regex lib 和數學上的 regex 並不完全一樣.
01/17 19:39, 3F
→
01/17 19:40, , 4F
不過你寫的例子我還是想不出寫法 XD
01/17 19:40, 4F
推
01/18 02:03, , 5F
就我查資料是表示現行的 lib 裡的語法和數學上的 regex 差別
01/18 02:03, 5F
→
01/18 02:03, , 6F
僅有 back reference (即 \1 \2 那些東西)
01/18 02:03, 6F
→
01/18 02:03, , 7F
不過這個例子似乎也找不出有重覆的字串可以用 \1 \2 等表示
01/18 02:03, 7F
→
01/18 02:04, , 8F
這好像印證了我前幾篇的猜測說加上 back reference 之後
01/18 02:04, 8F
→
01/18 02:04, , 9F
能表示的東西落在 regular language 和 context-free 之間
01/18 02:04, 9F
→
01/18 02:05, , 10F
(因為這東西是可以用 context-free 表示出來的)
01/18 02:05, 10F
→
01/18 07:46, , 11F
sorry,我這邊沒證明耶...我在這頁看到的http://0rz.tw/5e5p1
01/18 07:46, 11F
推
01/19 12:18, , 12F
前面的 pumping lemma 就是證明了....
01/19 12:18, 12F
推
08/17 01:08, , 13F
RE是CFG的子集，(01)^n已經在數學上證明不可能用re表示了
08/17 01:08, 13F
→
08/17 01:08, , 14F
所以才會有turing machine來吃CFG用的
08/17 01:08, 14F
推
10/09 03:38, , 15F
(偶然爬回來看到這個推文)樓上錯了...吃CFG的是pushdown
10/09 03:38, 15F
推
10/13 16:39, , 16F
謝謝樓上指正 我記錯了 Orz|| (也是偶然爬回來XD)
10/13 16:39, 16F
‣ 更多 ju22 的文章
文章代碼(AID): #19SJeAPF (RegExp)
‣ 更多 ju22 的文章
文章代碼(AID): #19SJeAPF (RegExp)