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