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

[ju22 (分享)]

前幾天看到一個介紹Regular Expression的網站

內容有提到一個範例

說像是

ab
aabb
aaabbb
aaaabbbb
.....
(有多少個a後面就要有多少個b)

這種字串是RE所無法表達的...

說數學上已經證明為不可行?

我也想不出來要怎麼用RE來表達..

有辦法寫出這種字串的re嗎?

thanks!!


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 61.228.96.174
→ janyfor:請問原PO有數學上的證明嗎?
推 LyinZ:用 pumping lemma 證 http://tinyurl.com/2ly3gx 範例就是
→ LyinZ:但現在常用的 regex lib 和數學上的 regex 並不完全一樣.
→ LyinZ:不過你寫的例子我還是想不出寫法 XD
推 LPH66:就我查資料是表示現行的 lib 裡的語法和數學上的 regex 差別
→ LPH66:僅有 back reference (即 \1 \2 那些東西)
→ LPH66:不過這個例子似乎也找不出有重覆的字串可以用 \1 \2 等表示
→ LPH66:這好像印證了我前幾篇的猜測說加上 back reference 之後
→ LPH66:能表示的東西落在 regular language 和 context-free 之間
→ LPH66:(因為這東西是可以用 context-free 表示出來的)
→ ju22:sorry,我這邊沒證明耶...我在這頁看到的http://0rz.tw/5e5p1
推 springman:前面的 pumping lemma 就是證明了....
推 nowar100:RE是CFG的子集，(01)^n已經在數學上證明不可能用re表示了
→ nowar100:所以才會有turing machine來吃CFG用的
推 LPH66:(偶然爬回來看到這個推文)樓上錯了...吃CFG的是pushdown
推 nowar100:謝謝樓上指正  我記錯了 Orz||   (也是偶然爬回來XD)